%I #43 Apr 28 2020 14:49:01
%S 1,1,1,3,3,1,9,15,6,1,39,75,45,10,1,189,459,330,105,15,1,1107,3087,
%T 2709,1050,210,21,1,7281,23535,23814,11109,2730,378,28,1,54351,197235,
%U 228285,122850,36099,6174,630,36,1
%N Forests of k increasing plane unary-binary trees on n nodes. Generalized Stirling numbers of the second kind associated with A185415.
%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.
%C 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.
%C 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).
%C 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.
%C The Bell transform of A080635(n+1). For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 18 2016
%D 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.
%H G. C. Greubel, <a href="/A185422/b185422.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>
%H T. Copeland, <a href="http://tcjpn.files.wordpress.com/2008/06/mathemagicalforestswp.pdf">Mathemagical Forests</a>
%F TABLE ENTRIES
%F (1)... T(n,k) = (1/k!)*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*P(n,j),
%F where P(n,x) are the polynomials described in A185415.
%F Compare (1) with the formula for the Stirling numbers of the second kind
%F (2)... Stirling2(n,k) = 1/k!*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*j^n.
%F RECURRENCE RELATION
%F (3)... T(n+1,k) = T(n,k-1) + k*T(n,k) + k*(k+1)*T(n,k+1).
%F GENERATING FUNCTION
%F Let E(t) = 1/2 + sqrt(3)/2*tan(sqrt(3)/2*t + Pi/6) be the e.g.f. for A080635.
%F The e.g.f. for the present triangle is
%F (4)... exp{x*(E(t)-1)} = Sum_{n>=0} R(n,x)*t^n/n!
%F = 1 + x*t + (x+x^2)*t^2/2! + (3*x+3*x^2+x^3)*t^3/3! + ....
%F ROW POLYNOMIALS
%F The row generating polynomials R(n,x) satisfy the recurrence
%F (5)... R(n+1,x) = x*{R(n,x)+R'(n,x)+R''(n,x)},
%F where the prime ' indicates differentiation with respect to x.
%F RELATIONS WITH OTHER SEQUENCES
%F Column 1 is A080635.
%F k!*T(n,k) counts ordered forests A185423(n,k).
%F 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
%e Triangle begins
%e n\k|....1......2......3......4......5......6......7
%e ===================================================
%e ..1|....1
%e ..2|....1......1
%e ..3|....3......3......1
%e ..4|....9.....15......6......1
%e ..5|...39.....75.....45.....10......1
%e ..6|..189....459....330....105.....15......1
%e ..7|.1107...3087...2709...1050....210.....21......1
%e ..
%e Examples of the recurrence:
%e T(5,1) = 39 = T(4,0)+1*T(4,1)+2*T(4,2) = 1*9+2*15;
%e T(6,3) = 330 = T(5,2)+3*T(5,3)+3*4*T(5,4) = 75+3*45+12*10.
%e Examples of forests:
%e T(4,1) = 9. The 9 plane increasing unary-binary trees on 4 nodes are shown in the example section of A080635.
%e T(4,2) = 15. The 15 forests consisting of two plane increasing unary-binary trees on 4 nodes consist of the 12 forests
%e ......... ......... ...3.....
%e .2...3... .3...2... ...|.....
%e ..\./.... ..\./.... ...2.....
%e ...1...4. ...1...4. ...|.....
%e ......... ......... ...1...4.
%e .
%e ......... ......... ...4.....
%e .2...4... .4...2... ...|.....
%e ..\./.... ..\./.... ...2.....
%e ...1...3. ...1...3. ...|.....
%e ......... ......... ...1...3.
%e .
%e ......... ......... ...4.....
%e .3...4... .4...3... ...|.....
%e ..\./.... ..\./.... ...3.....
%e ...1...2. ...1...2. ...|.....
%e ......... ......... ...1...2.
%e ......... ......... ...4.....
%e .3...4... .4...3... ...|.....
%e ..\./.... ..\./.... ...3.....
%e ...2...1. ...2...1. ...|.....
%e ......... ......... ...2...1.
%e .
%e and the three remaining forests
%e ......... ......... ..........
%e ..2..4... ..3..4... ..4...3...
%e ..|..|... ..|..|... ..|...|...
%e ..1..3... ..1..2... ..1...2...
%e ......... ......... ..........
%p #A185422
%p P := proc(n,x)
%p description 'polynomial sequence P(n,x) A185415'
%p if n = 0
%p return 1
%p else
%p return x*(P(n-1,x-1)-P(n-1,x)+P(n-1,x+1))
%p end proc:
%p with combinat:
%p T:= (n,k) -> 1/k!*add ((-1)^(k-j)*binomial(k,j)*P(n,j),j = 0..k):
%p for n from 1 to 10 do
%p seq(T(n,k),k = 1..n);
%p end do;
%t 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 *)
%o (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)))}
%o (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))}
%o (Sage) # uses[bell_matrix from A264428]
%o # Adds a column 1,0,0,0, ... at the left side of the triangle.
%o bell_matrix(lambda n: A080635(n+1), 10) # _Peter Luschny_, Jan 18 2016
%Y Cf. A080635, A008277, A185415, A147315, A185423.
%K nonn,easy,tabl
%O 1,4
%A _Peter Bala_, Jan 28 2011