login
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
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
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
J. F. Barbero G., J. Salas, and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013.
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3) (2015), #P3.37.
Tian-Xiao He, The mth-order Eulerian Numbers, arXiv:2312.17153 [math.CO], 2023.
S. Janson, M. Kuba and A. Panholzer, Generalized Stirling permutations, families of increasing trees and urn models arXiv:0805.4084v1 [math.CO], 2008.
S. K. Park, Inverse descents of r-multipermutations, Discrete Mathematics 132, 1-3, 215-229, 1994.
Grzegorz Rzadkowski and M. Urlinska, A Generalization of the Eulerian Numbers, arXiv preprint arXiv:1612.06635 [math.CO], 2016-2017.
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;
Table[T[n, k], {n, 1, 9}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Nov 12 2019 *)
CROSSREFS
Cf. A001147 (main diagonal), A007559 (row sums), A008292, A008517.
Sequence in context: A089434 A268298 A291418 * A186695 A210587 A019232
KEYWORD
nonn,easy,tabl
AUTHOR
Peter Bala, Dec 11 2012
STATUS
approved