Если повторения запрещены, то каждое число – размещение из соответствующего количества цифр, следовательно, количество разных трех-, четырех-, пятизначных чисел равно
= .
Если повторения разрешены, воспользуемся принципом умножения, каждое действие (задание очередной цифры) можно выполнить пятью способами.
Трехзначных чисел всего 5 × 5 × 5 = 125; четырехзначных чисел всего 5 × 5 × 5 ×5 = 625; пятизначных чисел всего 5 × 5 × 5 × 5× 5 = 3125.
Итого 3875 разных чисел.
Рассмотрим второй набор чисел.
Ноль не может стоять первой цифрой в числе, поэтому, если повторения запрещены, то разных трехзначных чисел всего 4 × 4 × 3 = 48;
разных четырехзначных чисел – 4 × 4 × 3 × 2 = 96; разных пятизначных чисел – 4 × 4 × 3 × 2 × 1 = 96. Всего 240 чисел.
Если повторения разрешены, трехзначных чисел всего 4 × 5 × 5 = =100; четырехзначных чисел - 4 × 5 × 5 × 5 = 500; пятизначных чисел - 4 ×
´ 5 × 5 × 5 × 5 = 2500. Всего 3100 чисел.
Определение. Сочетанием, содержащих k различных элементов, выбранных из n имеющихся разных элементов, называется любой неупорядоченный набор, содержащий k различных элементов, отобранных из n данных разных элементов.
В неупорядоченном наборе порядок перечисления элементов не важен.
Пример 1. Из букв A, B, C, D, E можно составить 10 разных сочетаний по три буквы: {A,B,C}; {A,B,D}; {A,B,E}; {A,C,D}; {A,C,E}; {A,D,E}; {B,C,D}; {B,C,E}; {B,D,E}; {C,D,E}.
Подчеркнем, что сочетание {A, B ,C} тождественно сочетанию {B, C, А}. Но перестановкиАВС и ВСА – различны.
Число разных сочетаний из п элементов по k элементов обозначается символом . Выведем формулу подсчета .
Любому неупорядоченному набору (сочетанию), содержащему k разных элементов, можно поставить в соответствие k упорядоченных наборов (перестановок) этих элементов.
Таким образом,
= (3)
Числа называются биномиальными коэффициентами.
1. = = 1.
2. = = 1.
3. = = n.
4. = = .
5. = = .
6. = + = = = = = .
Пример 2. Сколькими способами 8 человек можно распределить по двум комнатам, если в каждой должно быть не менее трех человек?
Решение. Варианты распределения людей по комнатам таковы.
Вариант 1: в первой комнате – 3 человека; во второй – 5 человек.
Вариант 2: в первой комнате – 4 человека; во второй – 4 человека.
Вариант 3: в первой комнате – 5 человек; во второй – 3 человека.
Чтобы задать распределение, необходимо (и достаточно) назвать людей, которые остаются в первой комнате, остальные перейдут во вторую. При этом порядок перечисления не важен.
Выбрать трех человек для первой комнаты можно n1 = = = 56 способами. Выбрать четырех человек для первой комнаты можно n2 = = = 70 способами. Выбрать пять человек для первой комнаты можно n3 = = = = 56 способами. Число всех способов разместить людей равно n1 + n2 + n3= 56 + 70 + 56 = 182.
Пример 3.
Сколько всего существует различных последовательностей, состоящих из нулей и единиц, в каждой из которых m нулей и n единиц.
Решение. Чтобы задать такую последовательность, надо выполнить одно действие – выбрать из (n + m) позиций для цифр m позиций для нулей (n позиций для единиц). Число способов выполнить это действие равно .
Например, если m = 2, n = 3, то =10. Эти последовательности таковы: 01101, 00111, 10011, 11100, 10101 и т.д.