This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A185422 Forests of k increasing plane unary-binary trees on n nodes. Generalized Stirling numbers of the second kind associated with A185415. 7
 1, 1, 1, 3, 3, 1, 9, 15, 6, 1, 39, 75, 45, 10, 1, 189, 459, 330, 105, 15, 1, 1107, 3087, 2709, 1050, 210, 21, 1, 7281, 23535, 23814, 11109, 2730, 378, 28, 1, 54351, 197235, 228285, 122850, 36099, 6174, 630, 36, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 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. A080635 enumerates increasing plane (ordered) unary-binary trees with n nodes labeled from the set {1,2,...n}. The entry T(n,k) of the present table counts forests of k increasing plane unary-binary trees having n nodes in total. See below for an example. The Stirling number of the second kind Stirling2(n,k) counts the partitions of the set [n] set into k blocks. Arranging the elements in each block in ascending numerical order provides an alternative combinatorial interpretation for Stirling2(n,k) as counting forests of k increasing unary trees on n nodes. Thus we may view the present array as generalized Stirling numbers of the second kind (associated with A080635 or with the polynomials P(n,x) of A185415 - see formulas (1) and (2) below). For a table of ordered forests of increasing plane unary-binary trees see A185423. For the enumeration of forests and ordered forests in the non-plane case see A147315 and A185421. The Bell transform of A080635(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016 REFERENCES F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48. 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 T. Copeland, Mathemagical Forests FORMULA TABLE ENTRIES (1)... T(n,k) = (1/k!)*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*P(n,j), where P(n,x) are the polynomials described in A185415. Compare (1) with the formula for the Stirling numbers of the second kind (2)... Stirling2(n,k) = 1/k!*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*j^n. RECURRENCE RELATION (3)... T(n+1,k) = T(n,k-1) + k*T(n,k) + k*(k+1)*T(n,k+1). GENERATING FUNCTION Let E(t) = 1/2 + sqrt(3)/2*tan(sqrt(3)/2*t + Pi/6) be the e.g.f. for A080635. The e.g.f. for the present triangle is (4)... exp{x*(E(t)-1)} = Sum_{n>=0} R(n,x)*t^n/n! = 1 + x*t + (x+x^2)*t^2/2! + (3*x+3*x^2+x^3)*t^3/3! + .... ROW POLYNOMIALS The row generating polynomials R(n,x) satisfy the recurrence (5)... R(n+1,x) = x*{R(n,x)+R'(n,x)+R''(n,x)}, where the prime ' indicates differentiation with respect to x. RELATIONS WITH OTHER SEQUENCES Column 1 is A080635. k!*T(n,k) counts ordered forests A185423(n,k). The row polynomials R(n,x) are given by D^n(exp(x*t)) evaluated at t = 0, where D is the operator (1+t+t^2)*d/dt. Cf. A147315 and A008297. - Peter Bala, Nov 25 2011 EXAMPLE Triangle begins n\k|....1......2......3......4......5......6......7 =================================================== ..1|....1 ..2|....1......1 ..3|....3......3......1 ..4|....9.....15......6......1 ..5|...39.....75.....45.....10......1 ..6|..189....459....330....105.....15......1 ..7|.1107...3087...2709...1050....210.....21......1 .. Examples of the recurrence: T(5,1) = 39 = T(4,0)+1*T(4,1)+2*T(4,2) = 1*9+2*15; T(6,3) = 330 = T(5,2)+3*T(5,3)+3*4*T(5,4) = 75+3*45+12*10. Examples of forests: T(4,1) = 9. The 9 plane increasing unary-binary trees on 4 nodes are shown in the example section of A080635. T(4,2) = 15. The 15 forests consisting of two plane increasing unary-binary trees on 4 nodes consist of the 12 forests ......... ......... ...3..... .2...3... .3...2... ...|..... ..\./.... ..\./.... ...2..... ...1...4. ...1...4. ...|..... ......... ......... ...1...4. . ......... ......... ...4..... .2...4... .4...2... ...|..... ..\./.... ..\./.... ...2..... ...1...3. ...1...3. ...|..... ......... ......... ...1...3. . ......... ......... ...4..... .3...4... .4...3... ...|..... ..\./.... ..\./.... ...3..... ...1...2. ...1...2. ...|..... ......... ......... ...1...2. ......... ......... ...4..... .3...4... .4...3... ...|..... ..\./.... ..\./.... ...3..... ...2...1. ...2...1. ...|..... ......... ......... ...2...1. . and the three remaining forests ......... ......... .......... ..2..4... ..3..4... ..4...3... ..|..|... ..|..|... ..|...|... ..1..3... ..1..2... ..1...2... ......... ......... .......... MAPLE P := proc(n, x) description 'polynomial sequence P(n, x) A185415' if n = 0 return 1 else return x*(P(n-1, x-1)-P(n-1, x)+P(n-1, x+1)) end proc: with combinat: T:= (n, k) -> 1/k!*add ((-1)^(k-j)*binomial(k, j)*P(n, j), j = 0..k): for n from 1 to 10 do seq(T(n, k), k = 1..n); end do; MATHEMATICA t[n_, k_] := t[n, k] = t[n-1, k-1] + k*t[n-1, k] + k*(k+1)*t[n-1, k+1]; t[n_, n_] = 1; t[n_, k_] /; Not[1 <= k <= n] = 0; Table[t[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 22 2012, from given recurrence *) PROG (PARI) {T(n, k)=if(n<1|k<1|k>n, 0, if(n==k, 1, T(n-1, k-1)+k*T(n-1, k)+k*(k+1)*T(n-1, k+1)))} (PARI) {T(n, k)=round(n!*polcoeff(polcoeff(exp(y*(-1/2+sqrt(3)/2*tan(sqrt(3)/2*x+Pi/6+x*O(x^n)))+y*O(y^k)), n, x), k, y))} (Sage) # The function bell_matrix is defined in A264428. # Adds a column 1, 0, 0, 0, ... at the left side of the triangle. bell_matrix(lambda n: A080635(n+1), 10) # Peter Luschny, Jan 18 2016 CROSSREFS Cf. A080635, A008277, A185415, A147315, A185423. Sequence in context: A216916 A157401 A143911 * A131889 A292386 A174287 Adjacent sequences:  A185419 A185420 A185421 * A185423 A185424 A185425 KEYWORD nonn,easy,tabl AUTHOR Peter Bala, Jan 28 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 22 03:39 EDT 2018. Contains 313964 sequences. (Running on oeis4.)