Размещения с повторениями

Сочетания без повторений

Перестановки без повторений

Если размещения из элементов взяты по (такие размещения будут различаться только порядком элементов), то такие размещения называются перестановками и обозначается.

Таким образом:

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

Другими словами, если две выборки, отличающиеся только порядком записи символов, считают совпадающими, то говорят о сочетании из m элементов по k.

Например, из четырёх элементов сочетания по 3 будут:

.

Если в каждом из этих соединений сделаем всевозможные перестановки, то получим всевозможные размещения из четырёх элементов по 3:

Число таких размещений равно, очевидно,.

Таким образом, число всех размещений из элементов по равно числу всех сочетаний из элементов по, умноженному на число всех перестановок, какие можно сделать из элементов, т.е.. Отсюда

Формулу числа сочетаний можно привести к другому виду, если умножим числитель и знаменатель её на произведение

.

Заметим, что, следовательно. Принято

«Опять восьмёрка!» - горестно воскликнул председатель клуба велосипедистов, взглянув на погнутое колесо своего велосипеда. «А всё почему? Да потому, что при вступлении в клуб мне выдали билет за номером 008. И теперь месяца не проходит, чтобы то на одном, то на другом колесе не появилась восьмёрка. Надо менять номер билета. А чтобы меня не обвиняли в суеверии, проведука я перерегистрацию всех членов клуба и буду выдавать только билеты с номерами, в которые ни восьмёрка, ни нуль не входят».

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

Для решения этой задачи определим сначала, сколько будет однозначных номеров. Ясно, что таких номеров будет восемь: 1 2 3 4 5 6 7 9.

А теперь найдём все двузначные номера, для чего возьмём любой из найденных однозначных номеров и припишем к нему любую из восьми цифр:

11 12 13 14 15 16 17 19

21 22 23 24 25 26 27 29

31 32 33 34 35 36 37 39

41 42 43 44 45 46 47 49

51 52 53 54 55 56 57 59

61 62 63 64 65 66 67 69

71 72 73 74 75 76 77 79

91 92 93 94 95 96 97 99

Очевидно, двузначных номеров будет. Но за каждым из них снова можно поставить любую из восьми допустимых цифр. В результате получим трёхзначных номеров. Значит, в клубе было 512 велосипедистов.

Задача о велосипедистах относится к следующему типу задач. Даны предметы, относящиеся к различным видам. Из них составляют всевозможные расстановки по предметов в каждой, при этом в расстановки могут входить и предметы одного вида, а две расстановки считаются различными, если они отличаются друг от друга или видом входящих в них предметов, или порядком этих предметов. Надо найти общее число таких расстановок.

Расстановки описанного типа называются k - размещениями с повторениями из элементов видов и обозначается.

Естественно предположить, что если число видов равно, а в каждое размещение входит элементов, то можно составить размещений с повторениями. Итак,

Дата добавления: 2014-01-04