login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A094503 Triangle read by rows: coefficients d(n,k) of Andre polynomials D(x,n) = Sum_{k>0} d(n,k)*x^k. 4
1, 1, 1, 1, 1, 4, 1, 11, 4, 1, 26, 34, 1, 57, 180, 34, 1, 120, 768, 496, 1, 247, 2904, 4288, 496, 1, 502, 10194, 28768, 11056, 1, 1013, 34096, 166042, 141584, 11056, 1, 2036, 110392, 868744, 1372088, 349504, 1, 4083, 349500, 4247720, 11204160, 6213288 (list; graph; refs; listen; history; text; internal format)
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

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

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 & 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.

Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.

Shi-Mei Ma, 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) = int {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.

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

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

(End)

There is a second family of polynomials which also match 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

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

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);

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).coeff(x, n+2)

def A094503_row(n) : return [p(n).coeff(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

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

Sequence in context: A242351 A124324 A178519 * A113897 A158753 A183884

Adjacent sequences:  A094500 A094501 A094502 * A094504 A094505 A094506

KEYWORD

nonn,tabf

AUTHOR

Philippe Deléham, Jun 09 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 00:32 EST 2018. Contains 299388 sequences. (Running on oeis4.)