A185421 Ordered forests of k increasing unordered trees on the vertex set {1,2,...,n} in which all outdegrees are <= 2.
1, 1, 2, 2, 6, 6, 5, 22, 36, 24, 16, 90, 210, 240, 120, 61, 422, 1260, 2040, 1800, 720, 272, 2226, 8106, 16800, 21000, 15120, 5040, 1385, 13102, 56196, 141624, 226800, 231840, 141120, 40320, 7936, 85170, 420330, 1244880, 2421720, 3175200, 2751840, 1451520, 362880
Offset: 1
Examples
Triangle begins
n\k|....1......2......3......4......5......6......7
===================================================
..1|....1
..2|....1......2
..3|....2......6......6
..4|....5.....22.....36.....24
..5|...16.....90....210....240....120
..6|...61....422...1260...2040...1800....720
..7|..272...2226...8106..16800..21000..15120...5040
..
Examples of recurrence relation for table entries:
T(5,2) = 2*{T(4,1)+T(4,2)+1/2*T(4,3)} = 2*(5+22+18) = 90;
T(6,1) = 1*{T(5,0)+T(5,1)+1/2*T(5,2)} = 16 + 1/2*90 = 61.
Examples of forests:
T(4,2) = 22. The 11 unordered forests consisting of 2 trees on 4 nodes are shown in the example section of A147315. Putting an order on the trees in a forest produces 2!*11 = 22 ordered forests.
Links
- G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
- 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.
Programs
-
Maple
#A185421 E := t -> sec(t)+tan(t)-1: F := (x,t) -> 1/(1-x*E(t)) - 1: Fser := series(F(x,t),t=0,12): for n from 1 to 7 do seq(coeff(n!*coeff(Fser,t,n),x,i),i=1..n) od;
-
Mathematica
nmax = 9; t[n_ /; n > 0, k_ /; k > 0] := t[n, k] = k*(t[n-1, k-1] + t[n-1, k] + 1/2*t[n-1, k+1]); t[1, 1] = 1; t[0, ] = 0; t[, 0] = 0; Flatten[Table[t[n, k], {n, 1, nmax}, {k, 1, n}]] (* Jean-François Alcover, Jun 22 2011, after recurrence *)
-
PARI
{T(n,k)=if(n<1||k<1||k>n,0,if(n==1,1,k*(T(n-1,k-1)+T(n-1,k)+T(n-1,k+1)/2)))} -
PARI
{T(n,k)=local(X=x+x*O(x^n));n!*polcoeff(polcoeff(1/(1-y*((1+sin(X))/cos(X)-1))-1,n,x),k,y)}
Formula
TABLE ENTRIES
(1)... T(n,k) = k!*A147315(n-1,k-1).
(2)... T(n,k) = Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*Z(n,j), where Z(n,x) denotes the zigzag polynomials as described in A147309.
Recurrence relation
(3)... T(n+1,k) = k*{T(n,k-1)+T(n,k)+1/2*T(n,k+1)}.
GENERATING FUNCTION
Let E(t) = sec(t)+tan(t)-1. E(t) is the egf for the enumeration of increasing unordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <=2 (plane unary binary trees in the notation of [Bergeron et al.]).
The egf of the present array is
(4)... 1/(1-x*E(t)) - 1 = Sum_{n >= 1} R(n,x)*t^n/n! = x*t + x*(1+2*x)*t^2/2! + x*(2+6*x+6*x^2)*t^3/3! + ...
ROW POLYNOMIALS
The row generating polynomials R(n,x) begin.
... R(1,x) = x
... R(2,x) = x*(1+2*x)
... R(3,x) = x*(2+6*x+6*x^2)
... R(4,x) = x*(5+22*x+36*x^2+24*x^3).
The ordered Bell polynomials OB(n,x) are the row polynomials of A019538 given by the formula
(5)... OB(n,x) = Sum_{k = 1..n} k!*Stirling2(n,k)*x^k.
By comparing the e.g.f.s for A019538 and the present table we obtain the surprising identity
(6)... (-i)^(n-1)*OB(n,x)/x = R(n,y)/y, where i = sqrt(-1) and x = i*y + (-1/2+i/2). It follows that the zeros of the polynomial R(n,y)/y lie on the vertical line Re(y) = -1/2 in the complex plane.
RELATIONS WITH OTHER SEQUENCES
(7)... T(n,1) = A000111(n).
Setting y = 0 in (6) yields
(8)... A000111(n) = i^(n+1)*Sum_{k=1..n} (-1)^k*k!*Stirling2(n,k) *((1+i)/2)^(k-1).
Extensions
Maple program corrected by Peter Luschny, Aug 02 2011
Comments