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
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
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees
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) # uses[bell_matrix from 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
Sequence in context: A216916 A157401 A143911 * A131889 A292386 A174287
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:47 EDT 2024. Contains 370953 sequences. (Running on oeis4.)