Uzasadnienia wzoru na liczbę kombinacji bez powtórzeń

[qws]

Witam!

Chciałbym prosić o wyjaśnienie mi uzasadnienia wzoru na liczbę kombinacji bez powtórzeń.

Wzór jest następujący: \(\displaystyle{ C={n \choose k}= \frac{n!}{k! \cdot (n-k)!}}\)

Weźmy taki przykład:
Spotykało się czterech przyjaciół i każdy witał się z każdym. Ile było powitań?

Oznaczmy każdego witającego się człowieka kolejną liczbą, tzn. np. człowieka pierwszego oznaczymy jako 1, drugiego jako 2, itd. W wyniku czego otrzymamy poniższy zbiór wszystkich możliwości:

(1,2) (1,3) (1,4)
(2,1) (2,3) (2,4)
(3,1) (3,2) (3,4)
(4,1) (4,2) (4,3)

Przy czym, podkreślone elementy zostają odrzucone (np. element (4,1) ulega odrzuceniu), ponieważ w kombinacjach bez powtórzeń nie rozróżniamy kolejności elementów, tzn. że np. elementy (1,2) i (2,1) traktujemy jako takie same (identyczne). A skoro tak przykładowy element (4,1) odrzucamy) ponieważ u nas już jest element (4,1) w pierwszym wierszu. A ponieważ elementy mają się nie powtarzać, a my elementy zawierające te same liczby ze zmienioną tylko kolejnością traktujemy jako identyczne / takie same, wobec czego jeden z nich musimy usunąć / odrzucić. Oczywiście element (1,2) oznacza, że pierwszy człowiek wita się z drugim i odwrotnie element (2,1) oznacza, że drugi człowiek wita się z pierwszym.

No dobrze. To jakie jest teraz uzasadnienie podanego wcześniej wzoru w odniesieniu do podanego przykładu?
Tzn. chciałbym zobaczyć jak ten wzór powstał.

Można by to też przedstawić za pomocą ilustracji "drzewka" reguły mnożenia :

I jak widać w każdym wierszu (zbioru podanego wcześniej) i w każdym przypadku mnożenia w "drzewku" odrzucamy zawsze parę dwóch identycznych liczb (np. para (1,1), (2,2), itd). I w każdym kolejnym wierszu w zbiorze i w każdej kolejnej czarnej gałęzi "drzewka" odrzucamy zawsze o jeden element (o jedną parę więcej) niż w poprzedniej gałęzi), przy czym w pierwszej odrzucamy zawsze 0 par/elementów. Czyli w pierwszej czarnej gałęzi odrzucamy zawsze 0 par/elementów, w drugim o jeden więcej czyli 1 parę (będzie nią (2,1) ), w trzecim już 2 pary (będą to (3,1), (3,2) ), zaś w czwartym 3 pary, a więc wszystko odrzucamy.

Podsumowując w każdej gałęzi czarnej odrzucamy zawsze jeden element/parę i o jeden dodatkowy element więcej niż w poprzednim (przy czym w pierwszym zawsze odrzucamy 0 takich par). Wiec mamy ilość elementów/par w każdej czarnej gałęzi to: \(\displaystyle{ (n-1)-a}\), gdzie \(\displaystyle{ n}\) oznacza ilość elementów na czarnej gałęzi, natomiast \(\displaystyle{ a}\) oznacza ilość dodatkowo odrzucanych elementów i początkowo przyjmuje wartość 0, a następnie rośnie o 1.

Tylko jak to ma się do tego wzoru?

[matmatmm]

Chciałbym prosić o wyjaśnienie mi uzasadnienia wzoru na liczbę kombinacji bez powtórzeń.

Wzór jest następujący: \(\displaystyle{ C={n \choose k}= \frac{n!}{k! \cdot (n-k)!}}\)

Wzór bierze się stąd:
Bierzemy liczbę wariacji bez powtórzeń \(\displaystyle{ \frac{n!}{(n-k)!}}\) i dzielimy przez liczbę permutacji \(\displaystyle{ k!}\)