This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/EulerianStirling
Contents
A consistent choice of
some classic numbers.
Sometimes OEIS can be confusing: there are variants of important numbers and, clearly, not every variant fits together with some other variant. This is especially true for the Eulerian numbers and the Stirling numbers. Therefore I put together a selection which I think is the most useful and systematic one among this family of numbers.
Typically these are not the main entries for these numbers in the database as the usage shifted in recent years away from the usage which was predominant in the second half of the 20 century and which is still predominant in OEIS; this usage is often described as the 'classic' one in the comments, a classification with dubious value.
To see that selection is consistent you have to observe the definitions of the sequences (here given in Maple parlance) which are based on the second-order Eulerian numbers.
What the numbers have in common:
- All numbers are defined for n ≥ 0 and k ≥ 0.
- All numbers are nonnegative.
- Derived sequences (like row sums) fit better the combinatorial interpretations.
Eulerian numbers.
1 | 1 | ||||||||||||
1 | 0 | 1 | |||||||||||
1 | 1 | 0 | 2 | ||||||||||
1 | 4 | 1 | 0 | 6 | |||||||||
1 | 11 | 11 | 1 | 0 | 24 | ||||||||
1 | 26 | 66 | 26 | 15 | 0 | 120 | |||||||
1 | 57 | 302 | 302 | 57 | 1 | 0 | 720 |
'New' A173018 as opposed to the 'old' A008292. Row sums are the number of permutations of n letters, A000142.
A173018 := proc(n, k) option remember; `if`(n=0,`if`(k=0,1,0), (k+1)*A173018(n-1, k)+(n-k)*A173018(n-1,k-1)) end: Note that newer versions of Maple provide this function as eulerian1(n,k) in the combinat package.
Why the new definition is better:
- Euler used the definition.
- Graham, Knuth, Patashnik used the definition in Concrete Mathematics.
- Digital Library of Mathematical Functions uses the definition.
- The combinatorial interpretation of the Eulerian polynomials is simpler.
Second-order Eulerian numbers.
1 | 1 | ||||||||||||
1 | 0 | 1 | |||||||||||
1 | 2 | 0 | 3 | ||||||||||
1 | 8 | 6 | 0 | 15 | |||||||||
1 | 22 | 58 | 24 | 0 | 105 | ||||||||
1 | 52 | 328 | 444 | 120 | 0 | 945 | |||||||
1 | 114 | 1452 | 4400 | 3708 | 720 | 0 | 10395 |
'New' A201637 as opposed to the 'old' A008517. Row sums are the number of fixed-point-free involutions in the symmetric group S2n, A001147.
A201637 := proc(n,k) option remember; `if`(n=0,`if`(k=0,1,0), (k+1)*A201637(n-1,k)+(2*n-k-1)*A201637(n-1,k-1)) end: Note that newer versions of Maple provide this function as eulerian2(n,k) in the combinat package.
Stirling cycle numbers.
1 | 1 | ||||||||||||
0 | 1 | 1 | |||||||||||
0 | 1 | 1 | 2 | ||||||||||
0 | 2 | 3 | 1 | 6 | |||||||||
0 | 6 | 11 | 6 | 1 | 24 | ||||||||
0 | 24 | 50 | 35 | 10 | 1 | 120 | |||||||
0 | 120 | 274 | 225 | 85 | 15 | 1 | 720 |
'New' A132393 as opposed to the 'old' Stirling numbers of first kind A008275. Row sums are the number of permutations of n letters A000142.
A132393 := proc(n, k) local j; add(binomial(n+j,2*(n-k))*eulerian2(n-k, j),j=0..n) end:
Second-order Stirling cycle numbers.
1 | 1 | ||||||||||||
0 | 0 | 0 | |||||||||||
0 | 1 | 0 | 1 | ||||||||||
0 | 2 | 0 | 0 | 2 | |||||||||
0 | 6 | 3 | 0 | 0 | 9 | ||||||||
0 | 24 | 20 | 0 | 0 | 0 | 44 | |||||||
0 | 120 | 130 | 15 | 0 | 0 | 0 | 265 |
'New' A106828 as opposed to the 'old' associated Stirling numbers of first kind A008306. Row sums are the derangements of n elements A000166.
A106828 := proc(n, k) local j; add(binomial(j,n-2*k)*eulerian2(n-k, j),j=0..n-k) end:
Stirling set numbers.
1 | 1 | ||||||||||||
0 | 1 | 1 | |||||||||||
0 | 1 | 1 | 2 | ||||||||||
0 | 1 | 3 | 1 | 5 | |||||||||
0 | 1 | 7 | 6 | 1 | 15 | ||||||||
0 | 1 | 15 | 25 | 10 | 1 | 52 | |||||||
0 | 1 | 31 | 90 | 65 | 15 | 1 | 203 |
'New' A048993 as opposed to the 'old' Stirling numbers of second kind A008277. Row sums are the number of partitions of an n-set, A000110.
A048993 := proc(n, k) local j; add(binomial(2*n-k-1-j,2*(n-k))*eulerian2(n-k, j),j=0..n) end:
Second-order Stirling set numbers.
1 | 1 | ||||||||||||
0 | 0 | 0 | |||||||||||
0 | 1 | 0 | 1 | ||||||||||
0 | 1 | 0 | 0 | 1 | |||||||||
0 | 1 | 3 | 0 | 0 | 4 | ||||||||
0 | 1 | 10 | 0 | 0 | 0 | 11 | |||||||
0 | 1 | 25 | 15 | 0 | 0 | 0 | 41 |
The absolute values of A137375 as opposed to the 'old' associated Stirling numbers of second kind A008299. Row sums are the number of multiton partitions of an n-set, A000296.
absA137375 := proc(n, k) local j; `if`(n=0,1, add(binomial(j,n-2*k)*eulerian2(n-k,n-k-j-1),j=0..n-k-1)) end:
The section below is unrelated to the Euler-Stirling family of numbers. However the notation of Donald E. Knuth used above, {n, k} and { {n, k} }, [n, k] and [ [n, k] ], lead me to ask: If (n, k) denotes the Pascal numbers, what is ((n, k))?
The Pascal triangle.
1 | 1 | ||||||||||||
1 | 1 | 2 | |||||||||||
1 | 2 | 1 | 4 | ||||||||||
1 | 3 | 3 | 1 | 8 | |||||||||
1 | 4 | 6 | 4 | 1 | 16 | ||||||||
1 | 5 | 10 | 10 | 5 | 1 | 32 | |||||||
1 | 6 | 15 | 20 | 15 | 6 | 1 | 64 |
These are the number of lattice paths from (0,0) to (n,k) using steps (1,0) and (1,1). Row sums are the number of subsets of an n-set, A000079.
A007318 := proc(n, k) binomial(n, k) end: binomial := proc(n, k) factorial(n)/(factorial(k)*factorial(n-k)) end:
The second-order Pascal triangle.
1 | 1 | ||||||||||||
1 | 1 | 2 | |||||||||||
1 | 2 | 1 | 4 | ||||||||||
1 | 6 | 6 | 1 | 14 | |||||||||
1 | 24 | 72 | 24 | 1 | 122 | ||||||||
1 | 120 | 1440 | 1440 | 120 | 1 | 31222 | |||||||
1 | 720 | 43200 | 172800 | 43200 | 720 | 1 | 260642 |
These are the number of ..?... Row sums are the number of ..?.. , A193520. Related sequences are A000178, A055209, A079478.
A009963 := proc(n, k) superbinomial(n,k) end: superbinomial := proc(n, k) superfactorial(n)/(superfactorial(k)*superfactorial(n-k)) end: