46.4 Stirling1

Stirling1( n, k )

Stirling1 returns the Stirling number of the first kind S_1(n,k) of the integers n and k. Stirling numbers of the first kind are defined by S_1(0,0) = 1, S_1(n,0) = S_1(0,k) = 0 if n, k <> 0 and the recurrence S_1(n,k) = (n-1) S_1(n-1,k) + S_1(n-1,k-1).

S_1(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 choose n} = sum_{k=0}^{n}{S_1(n,k) x^k} which is the generating function for Stirling numbers of the first kind. Note the similarity to x^n = sum_{k=0}^{n}{S_2(n,k) k! {x choose k}} (see Stirling2). Also the definition of S_1 implies S_1(n,k) = S_2(-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 numbers.

    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 

Previous Up Top Next
Index

GAP 3.4.4
April 1997