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

Задача 34. Сколько способов поставить по порядку 7 шаров, среди которых есть 3 красных, 2 белых, 1 жёлтый и 1 синий?

Решение. Здесь перестановка состава (3,2,1,1).

Вычисляем по формуле  ,

 =  =  = 420. Ответ. 420.

Заметим, что 24 = 4! < 420 < 7! = 5040.   

Если все шары одного и того же цвета были соединены, то фактически 4 объекта и 4! способов их расположить.

 

Задача 35. Сколько различных последовательностей длины 3 можно составить из цифр от 0 до 9 (цифры могут повторяться)?

Решение. Размещение с повторениями, считаем по формуле ,    . Ответ .
(Это и есть все числа от 000 до 999).

 

Задача 35-А. Сколько различных «слов» длины 4 можно составить из 33 букв?     Ответ  = 1.185.921 

 

 

Задача 36. Сколько есть способов составить новогодние наборы из 6 объектов, если есть 2 типа объектов: конфета, фрукт?  

 

Решение. Вычисляем по формуле сочетаний с повторениями , .

. 

| ФФФФФФ   К | ФФФФФ КК | ФФФФ  

ККК | ФФФ  КККК | ФФ    ККККК | Ф  КККККК |    

Задача 37. Сколько есть способов составить новогодние наборы из 7 объектов, если есть 3 типа объектов: конфета, фрукт, печенье?  

 

Решение. Вычисляем по формуле сочетаний с повторениями , .

. 

КК | ФФФ | ПП   (черта на местах 3,7)  

ККККККК | | (черта на местах 8,9).  

ПРАКТИКА 7. 04.03.2021.

Задача 38. В фирме было 7 человек, занимающих разные 7 должностей. Сколько способов реорганизации может быть, чтобы каждый получил какую-то другую должность?  

Решение. Вычисляем по формуле числа беспорядков, т.е. ищем количество перестановок порядка 7, не оставляющих на месте ни одно число.   

 =  =

 =

 = 1854.

Заметим, что , то есть перестановок, сохраняющих хотя бы один номер, гораздо больше.

2-й способ - по рекуррентной формуле:

Доказывали, что: d(n) = (n-1) (d(n-1)+d(n-2)).

2	3	4	5	6	7
1	2	9	44	265	1854

Ответ. 1854.

Задача 39. Сколько существует квадратных матриц порядка 6, содержащих 6 единиц (остальные элементы нули), ровно по одной единице в каждой строке и в каждом столбце, причём на диагонали нет ни одной единицы?  

Решение.  Это то же самое, что число перестановок, не сохраняющих ни одного элемента,  = 

 =  =

 = 265. 

Ответ. 265.

Задача 40. Взаимосвязь числа размещений с повторениями  и сочетаний с повторениями .  

1) Выбирают наборы из 4 объектов двух сортов. 

2)  Выбирают наборы из 4 объектов двух сортов и располагают по порядку.

Написать все варианты и сравнить.

n=2 n-1 =1 m=4  

1) Число вариантов

| 2222 1 | 222 11 | 22 111 | 2 1111 |

2) Число вариантов . 

 

 

1111 1112 1121 1122

2111 2112 2121 2122

1211 1212 1221 1222

2211 2212 2221 2222

Сочетаний 5, размещений  = 1+4+6+4+1

(нет 2)  (одна 2)  (две 2)  (три 2)  (четыре 2)

1111 111 2 11 22 1 222  2222

1111 1112 1121 1122 2111 2112 2121 2122 1211 1212 1221 1222 2211 2212 2221 2222

В сумме 16 случаев , но 5 вариантов   

- количество чисел в строке треугольника Паскаля,  

 - сумма чисел в той же строке треугольника Паскаля.

Задача 41.  (число Стирлинга 2 рода). Перечислить все 15 разбиений множества из 5 элементов на 2 подмножества.

Решение.   Разложения в сумму двух натуральных чисел: 1+4 и 2+3.

Заметим, что  =  = . 

Способов выбрать одно из 5 чисел, а 4 оставить в другом подмножестве, 5 штук:

1 2345

2 1345

3 1245

4 1235

5 1234

 Способов выбрать два числа, оставив 3 в другом подмножестве, 10:

12 345	13 245	14 235	15 234
	23 145	24 135	25 134
		34 125	35 124
			45 123

 

 

  Задача 42. . Вычислить это же число Стирлинга с помощью числа сочетаний.

Решение. Сначала рассмотрим, все разложения числа 7 в сумму 4 натуральных чисел.     1+1+1+4, 1+1+2+3, 1+2+2+2.  

Число Стирлинга  можно найти и так:

1) Способов выбрать 4 элемента из 7 (оставшиеся 3 образуют одноэлементные подмножества) .

2) Способов выбрать 3 элемента из 7, затем 2 из 4 оставшихся (после чего прочие 2 образуют одноэлементные подмножества) .

3) Способов выбрать 2 элемента из 7, затем 2 из 5 оставшихся и после 2 из 3 оставшихся , но здесь 3 множества по 2 элемента равнозначны, нужно поделить на 3!.

Итак, общее число случаев  (проверим, что оно окажется = 350).

 =

 =  = 

=  = 350. 

 

Перерыв

Задача 43.  Доказать рекуррентную формулу для чисел Белла:  

.

Решение.   В задаче 33 мы выводили ещё одну формулу для чисел Стирлинга 2 рода: . 

Формулу можно написать и в таком виде: , подразумевая, что  при .  

Вспомним, что по определению, число Белла есть сумма всех чисел Стирлинга в строке, то есть при всех  при одном и том же , т.е.  = = .

Тогда  =  = . Вынесем за знак внутренней суммы то, что не зависит от :  = .

Во внутренней сумме остались именно числа Белла для меньшего номера, так как там сумма чисел Стирлинга в количестве, меньше или равном  .   

 записана отдельно для удобства вычислений, так как для неё нет предшествующего столбца. Получили .