OFFSET
1,6
COMMENTS
a(n,k) is the number of increasing 0-1-2 trees on [n] with k leaves. An increasing 0-1-2 tree on [n] is an unordered tree on [n], rooted at 1, in which each vertex has <= 2 children and the labels increase along each path from the root. Example: a(4,2)=4 counts the trees with edges as follows, {1->2->3,1->4}, {1->2->4,1->3}, {1->2->4,2->3}, {1->3->4,1->2}. - David Callan, Oct 24 2004
LINKS
Alois P. Heinz, Rows n = 1..200, flattened
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
F. Bergeron, Ph. Flajolet, and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
David Callan, A note on downup permutations and increasing 0-1-2 trees
Chak-On Chow and Wai Chee Shiu, Counting Simsun Permutations by Descents, Ann. Comb. 15, 625-635 (2011). See p. 627 and comments section in A113897.
Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 35.
Filippo Disanto and Thomas Wiehe, Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012, see Y(x,z).
Filippo Disanto and Thomas Wiehe, Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model, Math. Biosci. 242 (2013), no. 2, 195-200.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
Dominique Foata and Guoniu Han, Arbres minimax et polynomes d'André .
D. Foata and Guo-Niu Han, Arbres minimax et polynomes d'André, Adv. in Appl. Math., 27 (2001), no.2-3, 367-389.
Guo-Niu Han and Shi-Mei Ma, Derivatives, Eulerian polynomials and the g-indexes of Young tableaux, arXiv:2006.14064 [math.CO], 2020.
Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.
Shi-Mei Ma, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, Alternating Eulerian polynomials and left peak polynomials, arXiv:2104.09374, 2021
Shi-Mei Ma and Yeong-Nan Yeh, The Peak Statistics on Simsun Permutations, Elect. J. Combin., 23 (2016), P2.14; arXiv preprint, arXiv:1601.06505 [math.CO], 2016.
E. Norton, Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions, arXiv preprint arXiv:1302.5411 [math.RA], 2013.
FORMULA
D(1, n) = A000111(n), Euler or up/down numbers. D(1/2, n) = A000142(n)*(1/2)^n. D(1/4, n) = A080795(n)*(1/4)^n.
From Peter Bala, Jun 26 2012: (Start):
Recurrence equation: T(n,k) = k*T(n-1,k) + (n+2-2*k)*T(n-1,k-1) for n >= 1 and 1 <= k <= floor((n+1)/2).
Let r(t) = sqrt(1-2*t) and w(t) = (1-r(t))/(1+r(t)). The e.g.f. is F(t,z) = r(t)*(1 + w(t)*exp(r(t)*z))/(1 - w(t)*exp(r(t)*z)) = 1 + t*z + t*z^2/2! + (t+t^2)*z^3/3! + (t+4*t^2)*z^4/4! + ... (Foata and Han, 2001, section 7).
Note that (F(2*t,z) - 1)/(2*t) is the e.g.f. for A101280.
The modified e.g.f. A(t,z) := (F(t,z) - 1)/t = z + z^2/2! + (1+t)*z^3/3! + (1+4*t)*z^4/4! + ... satisfies the autonomous partial differential equation dA/dz = 1 + A + 1/2*t*A^2 with A(t,0) = 1. It follows that the inverse function A(t,z)^(-1) may be expressed as an integral: A(t,z)^(-1) = Integral_{x = 0..z} 1/(1+x+1/2*t*x^2) dx.
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the row polynomials R(n,t) of the table: let f(t,x) = 1+x+1/2*t*x^2 and let D be the operator f(t,x)*d/dx. Then R(n+1,t) = t*D^n(f(t,x)) evaluated at x = 0.
By Bergeron et al., Theorem 1, the shifted row polynomial 1/t*R(n,t) is the generating function for rooted non-plane increasing 0-1-2 trees on n vertices, where the vertices of outdegree 2 have weight t and all other vertices have weight 1. An example is given below.
1/(2*t)*(1+t)^(n+1)*R(n,2*t/(1+t)^2) = the n-th Eulerian polynomial of A008292. For example, n = 5 gives 1/(2*t)*(1+t)^6*R(5,2*t/(1+t)^2) = 1 + 26*t + 66*t^2 + 26*t^3 + t^4.
(End)
There is a second family of polynomials which also matches the data and is different from the André polynomials as defined by Foata and Han (2001), formula 3.5. Let u = sqrt(s^2-2) and F(s,x) = u*x-2*log((exp(u*x)*(1-s/u)+s/u+1)/2), then for n>=0 the sequence of polynomials p_{n}(s) = (n+2)!*[x^(n+2)]F(s,x) starts 1, s, s^2+1, s^3+4*s, s^4+11*s^2+4, s^5+26*s^3+34*s, s^6+57*s^4+180*s^2+34, ... and the nonzero coefficients of these polynomials in descending order coincide with the sequence a(n). p_{n}(0) is an aerated version of the reduced tangent numbers, p_{2*n}(0) = A002105(n+1) for n>=0. In contrast, the André polynomials vanish at t=0 except for n=0. - Peter Luschny, Jul 01 2012
T(n,k) = A008303(n,k)/2^(n-k). - Ammar Khatab, Aug 17 2024
EXAMPLE
Triangle begins:
1
1
1 1
1 4
1 11 4
1 26 34
1 57 180 34
...
From Peter Bala, Jun 26 2012: (Start)
Recurrence equation: T(6,3) = 3*T(5,3) + 2*T(5,2) = 3*4 + 2*11 = 34.
n = 4: the 5 weighted non-plane increasing 0-1-2 trees on 4 vertices are
.........................................................
..4......................................................
..|......................................................
..3............4............4.............3.......3...4..
..|.........../............/............./.........\./...
..2......2...3........3...2.........4...2........(t)2....
..|.......\./..........\./...........\./............|....
..1.....(t)1.........(t)1..........(t)1.............1....
.........................................................
Hence row polynomial R(4,t) = (1 + 4*t)*t.
(End)
MAPLE
MATHEMATICA
t[1, 1] = 1; t[n_, k_] /; Not[1 <= k <= (n+1)/2] = 0; t[n_, k_] := t[n, k] = k*t[n-1, k] + (n+2-2*k)*t[n-1, k-1]; Table[t[n, k], {n, 0, 13}, {k, 1, (n + 1)/2}] // Flatten (* Jean-François Alcover, Nov 22 2012, after Maple *)
PROG
(Sage)
def p(n) :
s = var('s'); u = sqrt(s^2-2)
egf = u*x-2*ln((exp(u*x)*(1-s/u)+s/u+1)/2)
return factorial(n+2)*egf.series(x, n+4).coefficient(x, n+2)
def A094503_row(n) : return [p(n).coefficient(s, n-2*i) for i in (0..n//2)]
for n in (0..6): print(A094503_row(n)) # Peter Luschny, Jul 01 2012
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Philippe Deléham, Jun 09 2004
STATUS
approved