Сочетания. Если есть N предметов, то из них можно выбрать k предметов C(N,k) способами (читается "цэ из эн по ка"). Порядок предметов нам не важен. Мы можем  эти k предметов расставить по порядку k! способами, поэтому из каждого сочетания по k можно получить k! размещений по k. Значит, C(N,k)·k! = N^k. Поэтому число сочетаний из N по k  
C(N,k) = N(N-1)(N-2)...(N-k+1) / k!
(в числителе и знаменателе по k сомножителей).

Упражнения

1. Вычислите a) 10²   b) C(10,2).  

2. Вычислите a) 9³   b) C(9,3)     c) 9³ / C(9,3)

3. Есть 9 предметов на выбор. Сколькими способами можно 
а) составить список из трех предметов по порядку? 
b) выбрать набор из трех предметов (порядок не важен)? 

4. В команде 10 человек.  Сколькими способами можно 
а) выбрать из них капитана и заместителя? 
b) выбрать из них двух дежурных? 

5. В команде 10 человек.  Сколькими способами можно выбрать из них 8 игроков на ближайшую игру?

6. Вычислите C(9,6). Объясните, почему ответ совпадает с одним из ответов выше.

7. В карточке лотереи "4 из 12" надо заполнить 4 пронумерованные клеточки из 12. При розыгрыше наугад вынимаются 4 номера из 12. Главный приз выигрывает тот, кто угадает все номера. Сколько карточек надо заполнить, чтоб наверняка получить главный приз? 

Задачи

8. Вычислите С(1001,3) / С(1001,2) 

9. В карточке надо отметить 4 лошадей из 12 участниц забега. Приз "Миллион" выигрывает тот, у кого все 4 отмеченные лошади придут среди первых четырех. Пете подсказали двух лошадей, которые точно не окажутся в первой четверке.  Сколько карточек ему надо заполнить, чтоб наверняка получить приз "Миллион"? 

10. В команде 15 человек, включая Петю. На ближайшую игру надо выбрать 11 человек. Сколькими способами это можно сделать так, чтобы
а) взять Петю?
b) не взять Петю?
(ответ можно давать в виде C(...,...), не доводя до числа.

11. Не вычисляя, докажите что 
а) C(14,11)+C(14,10) = C(15,10)
b) C(N-1,k)+C(N-1,k-1) = C(N,k)

12 а) Среди 9 шаров три радиоактивных. Можно проверять на радиоактивность кучку из любых шаров. Объясните, почему не существует способа за 6 проверок гарантированно найти все три радиоактивных шара. (Измеритель радиоактивности не показывает уровня радиации, а только выдает ответ «в данной кучке шаров нет радиоактивных» или «в данной кучке шаров есть радиоактивные»)
b) Среди 9 монет – три фальшивых (легче настоящих). Объясните, почему не существует способа за 4 проверки гарантированно найти все три фальшивых монеты.

13.  Сколько есть 10-значных чисел, составленных из трех цифр 5 и семи цифр 6?

14* Шахматной ладье разрешили ходить только на одну клетку вверх или на одну клетку вправо. Сколькими способами она может добраться из правого нижнего угла угла в левый верхний на доске размером
a) 3x3    b) 4x4  c) 8x8    d)NxN  e) MxN  ?