User:Peter Luschny/EulerianStirling

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.

$\left\langle {n \atop m}\right\rangle$

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:

• 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.

$\left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle$

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 S_2n, 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.

$\left[{n \atop m}\right]$

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.

$\left[\!\left[{n \atop m}\right]\!\right]$

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.

$\left\{{n \atop m}\right\}$

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.

$\left\{\!\!\left\{{n \atop m}\right\}\!\!\right\}$

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.

$\left({n \atop m}\right)$

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.

$\left(\!\!\left({n \atop m}\right)\!\!\right)$

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: