Factorial( n ) F
returns the factorial n! of the positive integer n, which is defined as the product 1 \* 2 \* 3 \* .. \* n.
n! is the number of permutations of a set of n elements. 1/n! is the coefficient of xn in the formal series ex, which is the generating function for factorial.
gap> List( [0..10], Factorial ); [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ] gap> Factorial( 30 ); 265252859812191058636308480000000
PermutationsList (see PermutationsList) computes the set of all
permutations of a list.
Binomial( n, k ) F
returns the binomial coefficient ((n) || ( k)) of integers n and k, which is defined as n! / (k! (n-k)!) (see Factorial). We define (0 || 0) = 1, ((n) || ( k)) = 0 if k < 0 or n < k, and ((n) || ( k)) = (-1)k ((-n+k-1) || ( k)) if n < 0, which is consistent with the equivalent definition ((n) || ( k)) = ((n-1) || ( k)) + ((n-1) || ( k-1)).
((n) || ( 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) || ( k)) is the coefficient of the term xk of the polynomial (x + 1)n, which is the generating function for ((n) || \*), 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
NrCombinations (see Combinations) is the generalization of Binomial
for multisets. Combinations (see Combinations) computes the set of
all combinations of a multiset.
Bell( n ) F
returns the Bell number B(n). The Bell numbers are defined by B(0) = 1 and the recurrence B(n+1) = åk = 0n((n) || ( k))B(k).
B(n) is the number of ways to partition a set of n elements into pairwise disjoint nonempty subsets (see PartitionsSet). This implies of course that B(n) = åk = 0nS2(n,k) (see Stirling2). B(n)/n! is the coefficient of xn in the formal series eex-1, which is the generating function for B(n).
gap> List( [0..6], n -> Bell( n ) ); [ 1, 1, 2, 5, 15, 52, 203 ] gap> Bell( 14 ); 190899322
Bernoulli( n ) F
returns the n-th Bernoulli number Bn, which is defined by B0 = 1 and Bn = -åk = 0n-1((n+1) || ( k)) Bk/(n+1).
Bn/n! is the coefficient of xn in the power series of x/ex-1. Except for B1 = -1/2 the Bernoulli numbers for odd indices are zero.
gap> Bernoulli( 4 ); -1/30 gap> Bernoulli( 10 ); 5/66 gap> Bernoulli( 12 ); -691/2730 # there is no simple pattern in Bernoulli numbers gap> Bernoulli( 50 ); 495057205241079648212477525/66 # and they grow fairly fast
Stirling1( n, k ) F
returns the Stirling number of the first kind S1(n,k) of the integers n and k. Stirling numbers of the first kind are defined by S1(0,0) = 1, S1(n,0) = S1(0,k) = 0 if n, k < > 0 and the recurrence S1(n,k) = (n-1) S1(n-1,k) + S1(n-1,k-1).
S1(n,k) is the number of permutations of n points with k cycles. Stirling numbers of the first kind appear as coefficients in the series n! ((x) || ( n)) = åk = 0nS1(n,k) xk which is the generating function for Stirling numbers of the first kind. Note the similarity to xn = åk = 0nS2(n,k) k! ((x) || ( k)) (see Stirling2). Also the definition of S1 implies S1(n,k) = S2(-k,-n) if n,k < 0. There are many formulae relating Stirling numbers of the first kind to Stirling numbers of the second kind, Bell numbers, and Binomial coefficients.
gap> List( [0..4], k -> Stirling1( 4, k ) ); [ 0, 6, 11, 6, 1 ] # Knuth calls this the trademark of S_1 gap> List( [0..6], n->List( [0..6], k->Stirling1( n, k ) ) );; gap> PrintArray( last ); [ [ 1, 0, 0, 0, 0, 0, 0 ], # Note the similarity [ 0, 1, 0, 0, 0, 0, 0 ], # with Pascal's [ 0, 1, 1, 0, 0, 0, 0 ], # triangle for the [ 0, 2, 3, 1, 0, 0, 0 ], # Binomial numbers [ 0, 6, 11, 6, 1, 0, 0 ], [ 0, 24, 50, 35, 10, 1, 0 ], [ 0, 120, 274, 225, 85, 15, 1 ] ] gap> Stirling1(50,10); 101623020926367490059043797119309944043405505380503665627365376
Stirling2( n, k ) F
returns the Stirling number of the second kind S2(n,k) of the integers n and k. Stirling numbers of the second kind are defined by S2(0,0) = 1, S2(n,0) = S2(0,k) = 0 if n, k < > 0 and the recurrence S2(n,k) = k S2(n-1,k) + S2(n-1,k-1).
S2(n,k) is the number of ways to partition a set of n elements into k pairwise disjoint nonempty subsets (see PartitionsSet). Stirling numbers of the second kind appear as coefficients in the expansion of xn = åk = 0nS2(n,k) k! ((x) || ( k)). Note the similarity to n! ((x) || ( n)) = åk = 0nS1(n,k) xk (see Stirling1). Also the definition of S2 implies S2(n,k) = S1(-k,-n) if n,k < 0. There are many formulae relating Stirling numbers of the second kind to Stirling numbers of the first kind, Bell numbers, and Binomial coefficients.
gap> List( [0..4], k->Stirling2( 4, k ) ); [ 0, 1, 7, 6, 1 ] # Knuth calls this the trademark of S_2 gap> List( [0..6], n->List( [0..6], k->Stirling2( n, k ) ) );; gap> PrintArray( last ); [ [ 1, 0, 0, 0, 0, 0, 0 ], # Note the similarity with [ 0, 1, 0, 0, 0, 0, 0 ], # Pascal's triangle for [ 0, 1, 1, 0, 0, 0, 0 ], # the Binomial numbers [ 0, 1, 3, 1, 0, 0, 0 ], [ 0, 1, 7, 6, 1, 0, 0 ], [ 0, 1, 15, 25, 10, 1, 0 ], [ 0, 1, 31, 90, 65, 15, 1 ] ] gap> Stirling2( 50, 10 ); 26154716515862881292012777396577993781727011
GAP 4 manual