login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)