Die wichtigsten Formeln der Binominialkoeefizienten

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