Joachim Mohr   Mathematik Musik Delphi

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
Beispiel: In der Menge M={a b c d e} mit 5 Elementen gibt es die 10 Teilmengen mit 3 Elementen
{a b c} {a b d} {a b e}   {a c d} {a c e}   {a d e}
{b c d} {b c e} {b d e}
{c d e}
 5
( )=10
 3
Es gilt:

 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                      16   16  16*15
( ) = (   )  (Symmetrie) z.B. (  )=(  )=—————=120 (kurze Rechnung)
 k     m-k                     14    2   1*2



 m+1      m      m
(   ) = (   ) + ( )
 k+1     k+1     k



 n     n·(n-1)·(n-1)·...·(n-k+1)       n!
( ) = ——————————————————————————  = —————————
 k     1 · 2  ·  3  · ... ·k        k!·(n-k)!


 n                     n    n  n-1
( ) = 1 für k = 0 und ( ) = -·(   ) sonst. (Rekursionsformel)
 k                     k    k  k-1

Weitere Formeln

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 ( ) = Σ ( ) = ( ) + ( ) + ( ) + ... + ( ) 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 ( ) = Σ ( ) = ( ) + ( ) + ( ) + ... + ( ) 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 = Σ ( ) = ( ) + ( ) + ( ) + ... + ( ) + ( ) + ( ) 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 = Σ ( ) = Σ ( ) j=0 2j j=0 2j+1 Beispiel: 4 4 9 9 9 9 9 9 4 = Σ ( ) = ( ) + ( ) + ( ) + ( ) + ( ) j=0 2j 0 2 4 6 8 256 = 1 + 36 + 126 + 84 + 9