This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A185421 Ordered forests of k increasing unordered trees on the vertex set {1,2,...,n} in which all outdegrees are <= 2. 6
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS 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.]). 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. 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. 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). EXAMPLE 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. 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 *) PROG (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)} CROSSREFS Cf. A147315, A147309, A185423. Sequence in context: A173869 A247377 A167909 * A219976 A063944 A086447 Adjacent sequences:  A185418 A185419 A185420 * A185422 A185423 A185424 KEYWORD nonn,easy,tabl AUTHOR Peter Bala, Jan 31 2011 EXTENSIONS Maple program corrected by Peter Luschny, Aug 02 2011 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 15 15:44 EST 2018. Contains 318150 sequences. (Running on oeis4.)