Комбинаторика

1. Събиране: групите нямат общи елементи, затова при броенето на всички възможности никой избор не се брои два пъти – просто преброяваме първата група и продължаваме с втората.
2. Умножение: подреждаме двойките избори в таблица с $m$ реда (първия избор) и $n$ колони (втория). Всяка двойка е точно една клетка, а клетките са $m \cdot n$.
3. За повече стъпки прилагаме правилото многократно: двойките от първите два избора са $m \cdot n$, след всяка от тях третият избор е по $p$ начина и т.н.

∎

1. Пермутации: на първото място можем да сложим всеки от $n$-те елемента, на второто – всеки от останалите $n - 1$, … , на последното – единствения останал. По правилото за умножение подредбите са $n \cdot (n - 1) \cdot \ldots \cdot 1 = n!$.
2. Вариации: същото разсъждение, но спираме след $k$ места: $n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1)$. Ако допишем и множителите от $n - k$ до 1 и разделим на тях, получаваме $\frac{n!}{(n - k)!}$.
3. Вариации с повторение: на всяко от $k$-те места можем да сложим всеки от $n$-те елемента – $n \cdot n \cdot \ldots \cdot n = n^k$.
4. Защо $0! = 1$: така формулата $V(n,\ n) = \frac{n!}{0!}$ дава точно $n!$ – броя на пермутациите. Подредбите на 0 елемента са една – празната.
5. Пермутации с повторение: временно номерираме еднаквите елементи (например $\text{А}_1, \text{А}_2, \text{А}_3$), така че всички да са различни – подредбите стават $n!$. Всяка „истинска“ подредба се получава от точно $k_1! \cdot k_2! \cdot \ldots$ номерирани – колкото са начините да разместим номерата в всяка група. Затова делим на това произведение.

∎

1. Всяка вариация от $k$ елемента е комбинация (избраните елементи), подредена по някакъв начин. Всяка комбинация от $k$ елемента може да се подреди по $k!$ начина, затова $V(n,\ k) = C(n,\ k) \cdot k!$ и $$C(n,\ k) = \frac{V(n,\ k)}{k!} = \frac{n!}{k!\,(n - k)!}$$
2. $C(n,\ k) = C(n,\ n - k)$: да изберем $k$ елемента, които взимаме, е същото като да изберем $n - k$ елемента, които оставяме – двата избора си съответстват едно към едно. (Вижда се и от формулата: в знаменателя $k!$ и $(n - k)!$ просто си разменят местата.)
3. Правилото на Паскал: фиксираме един елемент $x$. Изборите на $k$ елемента са два вида: с $x$ – тогава избираме още $k - 1$ от останалите $n - 1$, т.е. $C(n - 1,\ k - 1)$ начина; и без $x$ – избираме всичките $k$ от останалите $n - 1$, т.е. $C(n - 1,\ k)$ начина. По правилото за събиране $C(n,\ k) = C(n - 1,\ k - 1) + C(n - 1,\ k)$.
4. Затова в триъгълника на Паскал всяко число е сбор на двете над него.

∎

1. $(a + b)^n = (a + b)(a + b) \cdot \ldots \cdot (a + b)$ – $n$ скоби. Когато разкриваме скобите, от всяка скоба взимаме или $a$, или $b$ и умножаваме взетото.
2. Ако сме взели $b$ от точно $k$ скоби, получаваме $a^{n-k}b^k$. Скобите, от които взимаме $b$, могат да се изберат по $C(n,\ k)$ начина – затова събираемото $a^{n-k}b^k$ се появява точно $C(n,\ k)$ пъти.
3. Събираме по всички $k$ от 0 до $n$ и получаваме формулата.
4. Следствие: при $a = b = 1$ получаваме $C(n,\ 0) + C(n,\ 1) + \ldots + C(n,\ n) = 2^n$ – сборът на всеки ред в триъгълника на Паскал е степен на 2. Комбинаторно: всяко подмножество на $n$ елемента се получава, като за всеки елемент решим „вътре“ или „вън“ – $2^n$ начина.

∎

1. Допускаме противното: във всяко чекмедже има най-много един предмет. Тогава в $n$ чекмеджета има най-много $n$ предмета – а те са $n + 1$. Противоречие.
2. Общият случай: ако във всяко чекмедже има най-много $k$ предмета, общо те са най-много $k \cdot n < kn + 1$. Отново противоречие, значи в някое чекмедже има поне $k + 1$.

∎