This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/EulerianStirling

From OeisWiki
Jump to: navigation, search

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.

The Euler triangle A173018
             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:

Second-order Eulerian numbers.

The second-order Euler triangle A201637
             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.

The Stirling cycle A132393
             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.

The second-order Stirling cycle A106828
             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.

The Stirling set triangle A048993
             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.

The second-order Stirling set triangle |A137375|
             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.

The Pascal triangle A007318
             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.

The second order Pascal triangle A009963
             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: