cp's OEIS Frontend

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

%I A094503 #103 Sep 02 2024 17:53:59
%S A094503 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 A094503 496,1,502,10194,28768,11056,1,1013,34096,166042,141584,11056,1,2036,
%U A094503 110392,868744,1372088,349504,1,4083,349500,4247720,11204160,6213288
%N A094503 Triangle read by rows: coefficients d(n,k) of Andre polynomials D(x,n) = Sum_{k>0} d(n,k)*x^k.
%C A094503 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 A094503 Alois P. Heinz, <a href="/A094503/b094503.txt">Rows n = 1..200, flattened</a>
%H A094503 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 A094503 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 A094503 David Callan, <a href="http://www.stat.wisc.edu/~callan/notes/">A note on downup permutations and increasing 0-1-2 trees</a>
%H A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 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 A094503 From _Peter Bala_, Jun 26 2012: (Start):
%F A094503 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 A094503 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 A094503 Note that (F(2*t,z) - 1)/(2*t) is the e.g.f. for A101280.
%F A094503 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 A094503 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 A094503 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 A094503 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 A094503 A000142(n) = 2^n*R(n,1/2); A080795(n) = 4^n*R(n,1/4);
%F A094503 A000670(n) = 3/4*3^n*R(n,4/9); A004123(n+1) = 5/6*5^n*R(n,12/25).
%F A094503 (End)
%F A094503 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 A094503 T(n,k) = A008303(n,k)/2^(n-k). - _Ammar Khatab_, Aug 17 2024
%e A094503 Triangle begins:
%e A094503   1
%e A094503   1
%e A094503   1  1
%e A094503   1  4
%e A094503   1 11   4
%e A094503   1 26  34
%e A094503   1 57 180 34
%e A094503   ...
%e A094503 From _Peter Bala_, Jun 26 2012: (Start)
%e A094503 Recurrence equation: T(6,3) = 3*T(5,3) + 2*T(5,2) = 3*4 + 2*11 = 34.
%e A094503 n = 4: the 5 weighted non-plane increasing 0-1-2 trees on 4 vertices are
%e A094503 .........................................................
%e A094503 ..4......................................................
%e A094503 ..|......................................................
%e A094503 ..3............4............4.............3.......3...4..
%e A094503 ..|.........../............/............./.........\./...
%e A094503 ..2......2...3........3...2.........4...2........(t)2....
%e A094503 ..|.......\./..........\./...........\./............|....
%e A094503 ..1.....(t)1.........(t)1..........(t)1.............1....
%e A094503 .........................................................
%e A094503 Hence row polynomial R(4,t) = (1 + 4*t)*t.
%e A094503 (End)
%p A094503 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 A094503 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 A094503 (Sage)
%o A094503 def p(n) :
%o A094503     s = var('s'); u = sqrt(s^2-2)
%o A094503     egf = u*x-2*ln((exp(u*x)*(1-s/u)+s/u+1)/2)
%o A094503     return factorial(n+2)*egf.series(x,n+4).coefficient(x,n+2)
%o A094503 def A094503_row(n) : return [p(n).coefficient(s,n-2*i) for i in (0..n//2)]
%o A094503 for n in (0..6): print(A094503_row(n)) # _Peter Luschny_, Jul 01 2012
%Y A094503 Cf. A000012, A000295, A008292, A101280, A113897.
%K A094503 nonn,tabf
%O A094503 1,6
%A A094503 _Philippe Deléham_, Jun 09 2004