русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

В2.3. Перестановки и сочетания с повторениями


Дата добавления: 2013-12-23; просмотров: 3414; Нарушение авторских прав


Определение. Перестановка с повторениями, состоящая из n элементов, содержит n1 одинаковых элементов 1-го вида, n2 – одинаковых элементов 2-го вида, … , nk одинаковых элементов k-го вида, n = n1 + n2+ +…+ nk.

Пример 1. Последовательность 112314123 – это перестановка с повторениями, содержащая n1 = 4 единицы; n2 = 2 двойки; n3 = 3 тройки и n4 = 1 четверку, n1 + n2 + n3 + n4 = 10.

Пример другой перестановки этих же цифр – последовательность 231141231. Но если в перестановке с повторениями переставить одинаковые элементы, она не изменится, одинаковые элементы неразличимы между собой.

Число различных перестановок с повторениями обозначим символом . Построим расчетную формулу..

Чтобы задать перестановку с повторениями, нужно выполнить одно за другим и независимо одно от других k действий:

· выбрать n1 мест из n имеющихся для элементов 1-го вида (способов);

· выбрать n2 мест из n - имеющихся для элементов 2-го вида (способов);

………………………………………………………………………………..

· выбрать nk мест из n п1 - … - = nk оставшихся для элементов k-го вида (= 1 способ).

По принципу умножения

==. (4)

Пример 2.Сколько чисел, больших 3000000, можно составить изцифр 3, 2, 2, 1, 1, 1, 0.

Решение. На первом месте обязательно должна стоять тройка. Оставшиеся 6 цифр образуют перестановку, в которой повторяются n1 = 2 двойки; n2 = 3 единицы и n3 = 1 ноль. Всего таких перестановок

P2,3,1 = = 60.

Определение. Сочетанием с повторениями из n элементов по k называется неупорядоченный набор, содержащий k элементов, каждый из которых может быть одного из n типов.

Пример 1. Располагая тремя цифрами, 1, 2, 3, составить из них всевозможные сочетания с повторениями, содержащие по 2 элемента.

Решение. Перечислим все такие сочетания: (1, 1); (1, 2); (1, 3); (2, 2); (2, 3); (3, 3). Подчеркнем, что (1, 2) и (2, 1) – это одно и то же сочетание, но 12 и 21 – два разных размещения.



Количество различных сочетаний с повторениями обозначим . Выведем формулу для определения .

Чтобы задать сочетание с повторениями, нужно знать, сколько элементов каждого типа оно содержит.

Пусть оно содержит m1 элементов 1-го типа; m2 – 2-го типа; … mnn-го типа, m1 + m2 +...+ mn = k.

Закодируем каждое сочетание с повторениями последовательностью из нулей и единиц, устроенной так. Сначала запишем m1 единиц, потом запишем 0. Затем запишем m2 единиц и 0, …. Наконец, запишем mn единиц.

Всего последовательность содержит m1 + m2 +...+ mn = k единиц и (n - 1) нулей.

В случае примера 1 k = 2, n = 3 и каждая последовательность содержит 2 единицы и 2 нуля.

Запишем последовательности, соответствующие каждому из 6 сочетаний с повторениями: (1, 1) - 1100; (1, 2) - 1010; (1, 3) - 1001; (2, 2) - 0110; (2, 3) - 0101; (3, 3) - 0011.

Таким образом, каждому сочетанию с повторениями соответствует своя последовательность из нулей и единиц, и по каждой такой последовательности однозначно восстанавливается соответствующие ей сочетание с повторениями. Следовательно, число равно числу разных последовательностей из нулей и единиц, содержащих n + k – 1 цифру, причем единиц всего k, а нулей – (n - 1) штук. Всего таких последовательностей .

Для примера 1: = = 6. Итак,

= (5)



<== предыдущая лекция | следующая лекция ==>
Некоторые свойства биномиальных коэффициентов | Понятие компоненты связности


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.