cp's OEIS Frontend

A185422 Forests of k increasing plane unary-binary trees on n nodes. Generalized Stirling numbers of the second kind associated with A185415.

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