|
|
A219512
|
|
Triangle of third-order Eulerian numbers: 3-Stirling permutations enumerated by ascents.
|
|
0
|
|
|
1, 1, 3, 1, 12, 15, 1, 33, 141, 105, 1, 78, 786, 1830, 945, 1, 171, 3450, 17538, 26685, 10395, 1, 360, 13257, 125352, 396495, 435960, 135135, 1, 741, 46971, 753291, 4238811, 9356175, 7921305, 2027025, 1, 1506, 157956, 4046526, 37013166, 140913270, 233216460, 158799690, 34459425
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
See A008292 for the triangle of Eulerian numbers and A008517 for the triangle of second-order Eulerian numbers (2-Stirling permutations).
A 3-Stirling permutation of order n is a permutation of the multiset {1,1,1,2,2,2,...,n,n,n} such that for each i, 1 <= i <= n, the elements occurring between two occurrences of i are at least i. This triangle enumerates 3-Stirling permutations by ascents. Examples are given below.
|
|
LINKS
|
|
|
FORMULA
|
Recurrence equation: T(n+1,k) = (k + 1)*T(n,k) + (3*n - k + 1)*T(n,k-1).
Let B(x,t) = Integral_{x' = 0..x} 1/((1 + x')*( 1+ t*x')^3) dx' = x - (1 + 3*t)*x^2/2 + (1 + 3*t + 6*t^2)*x^3/3 - (1 + 3*t + 6*t^2 + 10*t^3)*x^4/4 + ....
The e.g.f. A(x,t) appears to be the series reversion (with respect to x) B(x,t)^<-1> = x + (1 + 3*t)*x^2/2! + (1 + 12*t + 15*t^2)*x^3/3! + .... If true, then the e.g.f. A(x,t) satisfies the autonomous differential equation dA/dx = (1 + A)*(1 + t*A)^3, A(0,t) = 0. Also if we let D be the operator (1 + x)*(1 + t*x)^3*d/dx then the (n+1)-th row polynomial R(n+1,t) = D^n(x) evaluated at x = 0.
|
|
EXAMPLE
|
Triangle begins
.n\k.|..0....1......2.......3......4........5.......6
= = = = = = = = = = = = = = = = = = = = = = = = = = =
..1..|..1
..2..|..1....3
..3..|..1...12.....15
..4..|..1...33....141.....105
..5..|..1...78....786....1830....945
..6..|..1..171...3450...17538..26685....10395
..7..|..1..360..13257..125352.396495...435960..135135
...
Example of recurrence: T(5,2) = 3*141 + 11*33 = 786.
Row 2 = [1,3]. The 3-Stirling permutations of order 2 are obtained by inserting the string 222 into one of the four available positions in the string 111, giving 222111, 122211, 112221 and 111222. The first permutation has no ascents while the remaining three permutations each have 1 ascent.
|
|
MATHEMATICA
|
T[n_, k_] /; 1 <= k <= n-1 := T[n, k] = (k+1) T[n-1, k] + (3n-k-2) T[n-1, k-1]; T[_, 0] = 1; T[_, _] = 0;
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|