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
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
KEYWORD
AUTHOR
Peter Bala, Jan 28 2011
STATUS
approved