|
%I #35 Mar 19 2018 04:09:13
%S 1,1,2,2,6,6,5,22,36,24,16,90,210,240,120,61,422,1260,2040,1800,720,
%T 272,2226,8106,16800,21000,15120,5040,1385,13102,56196,141624,226800,
%U 231840,141120,40320,7936,85170,420330,1244880,2421720,3175200,2751840,1451520,362880
%N Ordered forests of k increasing unordered trees on the vertex set {1,2,...,n} in which all outdegrees are <= 2.
%C An increasing tree is a labeled rooted tree with the property that the sequence of labels along any path starting from the root is increasing. A000111(n) for n >= 0 enumerates 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.]).
%C The entry T(n,k) of the present table counts ordered forests of k such trees having n nodes in total. See below for an example. For unordered forests see A147315. For a table of ordered forests of increasing ordered trees in which all outdegrees are <=2 see A185423.
%H G. C. Greubel, <a href="/A185421/b185421.txt">Table of n, a(n) for the first 50 rows, flattened</a>
%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.
%F TABLE ENTRIES
%F (1)... T(n,k) = k!*A147315(n-1,k-1).
%F (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.
%F Recurrence relation
%F (3)... T(n+1,k) = k*{T(n,k-1)+T(n,k)+1/2*T(n,k+1)}.
%F GENERATING FUNCTION
%F 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.]).
%F The egf of the present array is
%F (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! + ...
%F ROW POLYNOMIALS
%F The row generating polynomials R(n,x) begin.
%F ... R(1,x) = x
%F ... R(2,x) = x*(1+2*x)
%F ... R(3,x) = x*(2+6*x+6*x^2)
%F ... R(4,x) = x*(5+22*x+36*x^2+24*x^3).
%F The ordered Bell polynomials OB(n,x) are the row polynomials of A019538 given by the formula
%F (5)... OB(n,x) = Sum_{k = 1..n} k!*Stirling2(n,k)*x^k.
%F By comparing the e.g.f.s for A019538 and the present table we obtain the surprising identity
%F (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.
%F RELATIONS WITH OTHER SEQUENCES
%F (7)... T(n,1) = A000111(n).
%F Setting y = 0 in (6) yields
%F (8)... A000111(n) = i^(n+1)*Sum_{k=1..n} (-1)^k*k!*Stirling2(n,k) *((1+i)/2)^(k-1).
%e Triangle begins
%e n\k|....1......2......3......4......5......6......7
%e ===================================================
%e ..1|....1
%e ..2|....1......2
%e ..3|....2......6......6
%e ..4|....5.....22.....36.....24
%e ..5|...16.....90....210....240....120
%e ..6|...61....422...1260...2040...1800....720
%e ..7|..272...2226...8106..16800..21000..15120...5040
%e ..
%e Examples of recurrence relation for table entries:
%e T(5,2) = 2*{T(4,1)+T(4,2)+1/2*T(4,3)} = 2*(5+22+18) = 90;
%e T(6,1) = 1*{T(5,0)+T(5,1)+1/2*T(5,2)} = 16 + 1/2*90 = 61.
%e Examples of forests:
%e 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.
%p #A185421 E := t -> sec(t)+tan(t)-1:
%p F := (x,t) -> 1/(1-x*E(t)) - 1:
%p Fser := series(F(x,t),t=0,12):
%p for n from 1 to 7 do
%p seq(coeff(n!*coeff(Fser,t,n),x,i),i=1..n) od;
%t 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 t[1, 1] = 1; t[0, _] = 0; t[_, 0] = 0; Flatten[Table[t[n, k], {n, 1, nmax}, {k, 1, n}]]
%t (* _Jean-François Alcover_, Jun 22 2011, after recurrence *)
%o (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)))}
%o (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)}
%Y Cf. A147315, A147309, A185423.
%K nonn,easy,tabl
%O 1,3
%A _Peter Bala_, Jan 31 2011
%E Maple program corrected by _Peter Luschny_, Aug 02 2011
|
