46.2 Binomial

Binomial( n, k )

Binomial returns the binomial coefficient {n choose k} of integers n and k, which is defined as n! / (k! (n-k)!) (see Factorial). We define {0 choose 0} = 1, {n choose k} = 0 if k<0 or n, and {n choose k} = (-1)^k {-n+k-1 choose k} if n < 0, which is consistent with {n choose k} = {n-1 choose k} + {n-1 choose k-1}.

{n choose k} is the number of combinations with k elements, i.e., the number of subsets with k elements, of a set with n elements. {n choose k} is the coefficient of the term x^k of the polynomial (x + 1)^n, which is the generating function for {n choose *}, hence the name.

    gap> List( [0..4], k->Binomial( 4, k ) );
    [ 1, 4, 6, 4, 1 ]    # Knuth calls this the trademark of Binomial
    gap> List( [0..6], n->List( [0..6], k->Binomial( n, k ) ) );;
    gap> PrintArray( last );
    [ [   1,   0,   0,   0,   0,   0,   0 ],    # the lower triangle is
      [   1,   1,   0,   0,   0,   0,   0 ],    # called Pascal\'s triangle
      [   1,   2,   1,   0,   0,   0,   0 ],
      [   1,   3,   3,   1,   0,   0,   0 ],
      [   1,   4,   6,   4,   1,   0,   0 ],
      [   1,   5,  10,  10,   5,   1,   0 ],
      [   1,   6,  15,  20,  15,   6,   1 ] ]
    gap> Binomial( 50, 10 );
    10272278170