J o a c h i m M o h r Mathematik Musik Programmieren
Die wichtigsten Formeln der Binominialkoeefizienten
Quelle: Peter Dembrowski "Kombinatorik" BI-Hochschultaschenbuch 741/741a
Definition: Die Anzahl der Teilmengen mit k Eelementen einer Menge mit n Elementen
bezeichnet man mit
n
( ) ("n über k")
k
n
Bemerkung: ( ) = 1 ist das neutrale Element der Multiplikation.
0
Es gilt dann:
n n·(n-1)·(n-1)·...·(n-k+1)
( ) = —————————————————————————— (kεN , nεR) [Zähler und Nenner haben k Faktoren)
k 1 · 2 · 3 · ... ·k 0
Man kann mit dieser Formel "n über k" erweitern zu einer Definition mit kε
N und nε
R.
Zum Beispiel:
-1/2 (-1/2)·(-3/2)·(-5/2)·(-7/2) 1·3·5·7 35
( ) = —————————————————————————— = —————————— = ———
4 1 · 2 · 3 · 4 1·2·3·4·16 128
Das Pascalsche Dreieck ist:
0
( )
0
1 1
( ) ( )
0 1
2 2 2
( ) ( ) ( )
0 1 2
3 3 3 3
( ) ( ) ( ) ( )
0 1 2 3
...
Mit den Werten:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
...
wichtige Formeln
m m
( ) = ( ) (Symmetrie)
k m-k
m+1 m m
( ) = ( ) + ( )
k+1 k+1 k
n n·(n-1)·(n-1)·...·(n-k+1) m!
( ) = —————————————————————————— = —————————
k 1 · 2 · 3 · ... ·k k!·(m-k)!
n n n n-1
( ) = 1 für k = 0 und ( ) = -·( ) sonst. (Rekursionsformel)
k k k k-1
n 15
ggT(n,k) = 1 =» ( ) ist ein Vielfachen von n, z.B. ( )=1365=15·91.
k 4
n+1 k n-i n n-1 n-2 n-k
( ) = sum ( ) = ( ) + ( ) + ( ) + ... + ( )
k i=0 k-i k k-1 k-2 0
Beispiel:
10 9 8 7 6 5 4
( ) = ( ) + ( ) + ( ) + ( ) + ( ) + ( )
5 5 4 3 2 1 0
252 = 126 + 70 + 35 + 15 + 5 + 1
n n-k n-j n-1 n-2 n-3 k
( ) = sum ( ) = ( ) + ( ) + ( ) + ... + ( )
k+1 j=1 k k k k k
Beispiel:
10 9 8 7 6 5 4
( ) = ( ) + ( ) + ( ) + ( ) + ( ) + ( )
5 4 4 4 4 4 4
252 = 126 + 70 + 35 + 15 + 5 + 1
n n n n n n n n n
2 = sum( ) = ( ) + ( ) + ( ) + ... + ( ) + ( ) + ( )
k=0 k 0 1 2 n-2 n-1 n
n k n n-m
( )·( ) = ( )·( ) für m ≤ k ≤ n
k m m n-k
n n 2n+1 n 2n+1
4 = sum ( ) = sum ( )
j=0 2j j=0 2j+1
Beispiel:
4 4 9 9 9 9 9 9
4 = sum( ) = ( ) + ( ) + ( ) + ( ) + ( )
j=0 2j 0 2 4 6 8
256 = 1 + 36 + 126 + 84 + 9