%I #103 Sep 02 2024 17:53:59

%S 1,1,1,1,1,4,1,11,4,1,26,34,1,57,180,34,1,120,768,496,1,247,2904,4288,

%T 496,1,502,10194,28768,11056,1,1013,34096,166042,141584,11056,1,2036,

%U 110392,868744,1372088,349504,1,4083,349500,4247720,11204160,6213288

%N Triangle read by rows: coefficients d(n,k) of Andre polynomials D(x,n) = Sum_{k>0} d(n,k)*x^k.

%C 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

%H Alois P. Heinz, <a href="/A094503/b094503.txt">Rows n = 1..200, flattened</a>

%H Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.

%H F. Bergeron, Ph. Flajolet, and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

%H David Callan, <a href="http://www.stat.wisc.edu/~callan/notes/">A note on downup permutations and increasing 0-1-2 trees</a>

%H Chak-On Chow and Wai Chee Shiu, <a href="https://doi.org/10.1007/s00026-011-0113-6">Counting Simsun Permutations by Descents</a>, Ann. Comb. 15, 625-635 (2011). See p. 627 and comments section in A113897.

%H Ming-Jian Ding and Bao-Xuan Zhu, <a href="https://doi.org/10.1016/j.aam.2023.102591">Some results related to Hurwitz stability of combinatorial polynomials</a>, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 35.

%H Filippo Disanto and Thomas Wiehe, <a href="http://arxiv.org/abs/1112.1295">Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model</a>, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012, see Y(x,z).

%H Filippo Disanto and Thomas Wiehe, <a href="http://dx.doi.org/10.1016/j.mbs.2013.01.010">Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model</a>, Math. Biosci. 242 (2013), no. 2, 195-200.

%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions</a>. arXiv:math/0501052v2 [math.CA], 2005.

%H Dominique Foata and Guoniu Han, <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub86minimax.html">Arbres minimax et polynomes d'André </a>.

%H D. Foata and Guo-Niu Han, <a href="http://dx.doi.org/10.1006/aama.2001.0740">Arbres minimax et polynomes d'André</a>, Adv. in Appl. Math., 27 (2001), no.2-3, 367-389.

%H Guo-Niu Han and Shi-Mei Ma, <a href="https://arxiv.org/abs/2006.14064">Derivatives, Eulerian polynomials and the g-indexes of Young tableaux</a>, arXiv:2006.14064 [math.CO], 2020.

%H Shi-Mei Ma, <a href="http://dx.doi.org/10.1016/j.disc.2013.05.010">Enumeration of permutations by number of alternating runs</a>, Discrete Math., 313 (2013), 1816-1822.

%H Shi-Mei Ma, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/2104.09374">Alternating Eulerian polynomials and left peak polynomials</a>, arXiv:2104.09374, 2021

%H Shi-Mei Ma and Yeong-Nan Yeh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p14">The Peak Statistics on Simsun Permutations</a>, Elect. J. Combin., 23 (2016), P2.14; <a href="https://arxiv.org/abs/1601.06505">arXiv preprint</a>, arXiv:1601.06505 [math.CO], 2016.

%H E. Norton, <a href="http://arxiv.org/abs/1302.5411">Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions</a>, arXiv preprint arXiv:1302.5411 [math.RA], 2013.

%F 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.

%F From _Peter Bala_, Jun 26 2012: (Start):

%F 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).

%F 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).

%F Note that (F(2*t,z) - 1)/(2*t) is the e.g.f. for A101280.

%F 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.

%F 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.

%F 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.

%F 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.

%F A000142(n) = 2^n*R(n,1/2); A080795(n) = 4^n*R(n,1/4);

%F A000670(n) = 3/4*3^n*R(n,4/9); A004123(n+1) = 5/6*5^n*R(n,12/25).

%F (End)

%F 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

%F T(n,k) = A008303(n,k)/2^(n-k). - _Ammar Khatab_, Aug 17 2024

%e Triangle begins:

%e 1

%e 1

%e 1 1

%e 1 4

%e 1 11 4

%e 1 26 34

%e 1 57 180 34

%e ...

%e From _Peter Bala_, Jun 26 2012: (Start)

%e Recurrence equation: T(6,3) = 3*T(5,3) + 2*T(5,2) = 3*4 + 2*11 = 34.

%e n = 4: the 5 weighted non-plane increasing 0-1-2 trees on 4 vertices are

%e .........................................................

%e ..4......................................................

%e ..|......................................................

%e ..3............4............4.............3.......3...4..

%e ..|.........../............/............./.........\./...

%e ..2......2...3........3...2.........4...2........(t)2....

%e ..|.......\./..........\./...........\./............|....

%e ..1.....(t)1.........(t)1..........(t)1.............1....

%e .........................................................

%e Hence row polynomial R(4,t) = (1 + 4*t)*t.

%e (End)

%p A094503:=proc(n,k) options remember: if(n=1 and k=1) then RETURN(1) elif(1<=k and k<=floor((n+1)/2) and n>=1) then RETURN(k*A094503(n-1,k)+(n+2-2*k)*A094503(n-1,k-1)) else RETURN(0) fi: end; seq(seq(A094503(n,k),k=1..floor((n+1)/2)),n=1..14);

%t 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 *)

%o (Sage)

%o def p(n) :

%o s = var('s'); u = sqrt(s^2-2)

%o egf = u*x-2*ln((exp(u*x)*(1-s/u)+s/u+1)/2)

%o return factorial(n+2)*egf.series(x,n+4).coefficient(x,n+2)

%o def A094503_row(n) : return [p(n).coefficient(s,n-2*i) for i in (0..n//2)]

%o for n in (0..6): print(A094503_row(n)) # _Peter Luschny_, Jul 01 2012

%Y Cf. A000012, A000295, A008292, A101280, A113897.

%K nonn,tabf

%O 1,6

%A _Philippe Deléham_, Jun 09 2004