- •Комбінаторика
- •Правило суми
- •Задача про Вовочку маленького
- •Правило добутку
- •Задача про Вовочку великого
- •Задача про Вовочку піжона
- •Принцип Діріхле
- •Задача про Вовочку соню
- •Розміщення
- •Розміщення
- •Задача про збори
- •Перестановки
- •Перестановки
- •Задача про авто
- •Комбінації
- •Комбінації
- •Задача про морозиво
- •Доведення співвідношення
- •Доведення співвідношення
- •Кількість підмножин
- •Доведення співвідношення
- •Біном Ньютона
- •Доведення співвідношення
- •Розміщення з
- •Розміщення з повтореннями
- •Перестановки з повтореннями
- •4. Перестановки з повтореннями
- •Комбінації з повтореннями
- •Комбінації з повтореннями
- •Скільки розв’язків у цілих невід’ємних числах
- •5. Поліноміальна теорема
- •6. Поліноміальна теорема
4. Перестановки з повтореннями
|
ел.1-го типу |
n1 |
ел.1-го типу |
…………... |
|
|
{ел.1-го типу |
|
………….. |
|
ел.k-го типу |
nk |
ел.k-го типу |
…………… |
|
|
{ел.k-го типу |
1-й ел.1-го типу
2-й ел.1-го типу
…………...
n1-й ел.1-го типу
1-й ел.k-го типу
2-й ел.k-го типу
…………...
nk-й ел.k-го типу
}
}
n1!
nk!
Pn (n1, n2 ,...nk ) n1!n2! ... nk ! n!
Pn (n1, n2 ,...nk ) n!
n1!n2! ... nk ! 31
Комбінації з повтореннями
Кількість різних невпрорядкованих вибірок з повтореннями
об’єму k
з n-елементної множини
Cnk
32
Комбінації з повтореннями
11...1011..110...0111..11
1-й тип 2-й тип .... n-й тип
1 - k штук, 0 - n-1 штук, усього завжди k+n-1 символів з k+n-1 позицій - k для 1 Cnk k 1
Cnk Cnk k 1 Cnn k1 1
33
Скільки розв’язків у цілих невід’ємних числах
має рівняння
x1 x2 ..... xn k |
xi 0 |
xi - кількість елементів і-го типу
Cnk
34
5. Поліноміальна теорема
(x1 x2 .... xk )n
|
Pn (n1 , .... , nk ) x1n1 x2n2 .... xknk |
n1 |
0,...nk 0 |
n1 |
... nk n |
35
6. Поліноміальна теорема
(x1 ... xk )(x1 ... xk )...(x1 ... xk )
xi |
xi |
.....xi |
n |
1 ip |
k |
|
|
|
||||
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
xn1 xn2 |
....xnk , n n |
... n |
|
n, n 0 |
||||||||
1 |
2 |
|
k |
|
1 |
|
2 |
|
|
k |
i |
|
x1 взято з n1 |
дужок |
|
|
|
|
|
||||||
………………. |
|
|
|
|
|
|
|
|||||
xk взято з nk |
дужок |
|
...x |
x ...x |
||||||||
|
x x ...x x x |
...x |
||||||||||
|
1 |
1 |
1 2 2 |
|
2 |
|
k |
|
k k |
|||
|
|
|
n1 |
|
n2 |
|
|
|
|
|
nk |
Pn(n1,n2,….nk) перестановок 36
7. |
|
|
|
|
|
|
|
|
K=2 |
|
|
|
|
|
|
(x1 x2 )n |
Pn (n1, n2 ) x1n1 x2n2 |
|
||||
|
n1 |
0,n2 0 |
|
|
|
|
|
n1 |
n2 n |
|
|
|
|
n2 n n1 |
n |
|
x1n1 x2n n1 |
|||
|
Pn n1, n n1 |
|||||
Pn n1, n n1 |
|
n! |
Cnn1 |
|
|
|
n !(n n )! |
|
|
|
|||
1 |
1 |
|
|
|
|
|
|
|
n |
|
|
|
|
|
Cnn1 x1n1 x2n |
n1 |
|
|||
|
n1 0 |
|
|
37 |