cp's OEIS Frontend

A185421 Ordered forests of k increasing unordered trees on the vertex set {1,2,...,n} in which all outdegrees are <= 2.

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