login
This site is supported by donations 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

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

#A185422

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)

# The function bell_matrix is defined in 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

Cf. A080635, A008277, A185415, A147315, A185423.

Sequence in context: A216916 A157401 A143911 * A131889 A292386 A174287

Adjacent sequences:  A185419 A185420 A185421 * A185423 A185424 A185425

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 04:43 EDT 2018. Contains 304455 sequences. (Running on oeis4.)