Rekurencja Bolek: Mam takie pytanie odnośnie rekurencji. Mam n farb i k nierozróżnialnych kul. f(n,k) = f(n−1, k) + f(n, k−1) Skąd się to bierze? Skąd pomysł na ułożenie takiego równania?

jc: Szkoda, że nie na odwrót − k kolorów i n kul. Lepiej się kojarzy, ale trudno. {Wszystkie sposoby} = {ostatnia kula ostatniego koloru, wcześniejsze dowolne} U {wszystkie kule, ale nie używamy ostatniego koloru} Zbiory po prawej stronie są rozłączne, stąd Twój wzór.

Bolek: No tak, ale chodzi mi o genezę samego pomysłu. Jak to logicznie wytłumaczyć? Skąd wybór akurat tych zbiorów?

jc: Przyjrzyj się wzorowi rekurencyjnemu. Co masz po lewej stronie, co po prawej. Zbiory zostały podpowiedziane przez wzór.

Bolek: Dalej średnio to widzę. Od zawsze miałem na bakier z kombinatoryką, ale czas coś z tym zrobić. Więc: jak odróżnić. czy te zbiory są rozłączne? Rozrysowałem przykład dla k, n = 3 i od razu to widać, ale jak to stwierdzić na pierwszy rzut oka?

jc: W pierwszym zbiorze mamy wszystkie możliwości z co najmniej jedną kulą ostatniego koloru. W drugim zbiorze mamy wszystkie możliwości bez ostatniego koloru. Więc chyba jasne, że te zbiory są rozłączne.

Bolek: Okej, rozłączność pojmuję. Tylko jak zauważyć, że zbiory zostały podpowiedziane przez wzór?