Uzasadnienie wzoru na liczbę kombinacji Jeżeli rozważymy zbiór to każdą jego k-elementową kombinację (obojętne czy z powtórzeniami, czy bez powtórzeń) da się uporządkować tak, by jej elementy spełniały zależność:
co w liczbach naturalnych (wraz z zerem) równoważne jest kolejno
oraz, po zamianie symboli,
Liczba rozwiązań takiej nierówności dla jest równa liczbie k-elementowych kombinacji bez powtórzeń zbioru (n+k–1)-elementowego, czyli Donald Knuth, The Art of Computer Programming, tom I..
Ograniczenie górne Uwzględniając znane ograniczenie symbolu Newtona mamy
Zobacz też teoria zbiorów
Uwagi
Przypisy
Kategoria:Kombinatoryka