TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS11/Beispiel 147

Umwandlung

Als erstes vollziehen wir einen Indexshift: (Einfach überall n und k, -1 rechnen)

von

(n+1 über k+1) = (n über k+1) + (n über k)

zu

(n über k) = (n-1 über k) + (n-1 über k-1)

Anmerkung: Das Beispiel lässt sich auch ohne Indexshift lösen, die unten angewandte Methode ist dabei ident.

Analogie

Wir interpretieren eine Folge von Einsen und Nullen, als Teilmenge wobei gilt:
0 ... nicht in der Teilmenge von k
1 ... in der Teilmenge von k

Beispiel: 10011101011101 -> n = 14, k = 9

Nun betrachten wir zwei Fälle:

1. Fall: Die erste Stelle ist fix eine 0: 01011101011101 dh es bleibt für den Rest n-1 (13) nur k (9) übrig

2. Fall: Die erste Stelle ist fix eine 1: 10011101011101 dh es bleibt für den Rest n-1 (13) nur k-1 (8) übrig

k und n können sich natürlich - auf eine Teilmenge bezogen - nicht verändern -> (n über k) bleibt gleich.

Somit haben wir, wenn wir beide Fälle addieren: (n-1 über k) + (n-1 über k-1) = (n über k)