login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A185421 Ordered forests of k increasing unordered trees on the vertex set {1,2,...,n} in which all outdegrees are <= 2. 6
1, 1, 2, 2, 6, 6, 5, 22, 36, 24, 16, 90, 210, 240, 120, 61, 422, 1260, 2040, 1800, 720, 272, 2226, 8106, 16800, 21000, 15120, 5040, 1385, 13102, 56196, 141624, 226800, 231840, 141120, 40320, 7936, 85170, 420330, 1244880, 2421720, 3175200, 2751840, 1451520, 362880 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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. A000111(n) for n >= 0 enumerates increasing unordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2 (plane unary binary trees in the notation of [Bergeron et al.]).

The entry T(n,k) of the present table counts ordered forests of k such trees having n nodes in total. See below for an example. For unordered forests see A147315. For a table of ordered forests of increasing ordered trees in which all outdegrees are <=2 see A185423.

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, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

FORMULA

TABLE ENTRIES

(1)... T(n,k) = k!*A147315(n-1,k-1).

(2)... T(n,k) = Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*Z(n,j), where Z(n,x) denotes the zigzag polynomials as described in A147309.

Recurrence relation

(3)... T(n+1,k) = k*{T(n,k-1)+T(n,k)+1/2*T(n,k+1)}.

GENERATING FUNCTION

Let E(t) = sec(t)+tan(t)-1. E(t) is the egf for the enumeration of increasing unordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <=2 (plane unary binary trees in the notation of [Bergeron et al.]).

The egf of the present array is

(4)... 1/(1-x*E(t)) - 1 = Sum_{n >= 1} R(n,x)*t^n/n! = x*t + x*(1+2*x)*t^2/2! + x*(2+6*x+6*x^2)*t^3/3! + ...

ROW POLYNOMIALS

The row generating polynomials R(n,x) begin.

... R(1,x) = x

... R(2,x) = x*(1+2*x)

... R(3,x) = x*(2+6*x+6*x^2)

... R(4,x) = x*(5+22*x+36*x^2+24*x^3).

The ordered Bell polynomials OB(n,x) are the row polynomials of A019538 given by the formula

(5)... OB(n,x) = Sum_{k = 1..n} k!*Stirling2(n,k)*x^k.

By comparing the e.g.f.s for A019538 and the present table we obtain the surprising identity

(6)... (-i)^(n-1)*OB(n,x)/x = R(n,y)/y, where i = sqrt(-1) and x = i*y + (-1/2+i/2). It follows that the zeros of the polynomial R(n,y)/y lie on the vertical line Re(y) = -1/2 in the complex plane.

RELATIONS WITH OTHER SEQUENCES

(7)... T(n,1) = A000111(n).

Setting y = 0 in (6) yields

(8)... A000111(n) = i^(n+1)*Sum_{k=1..n} (-1)^k*k!*Stirling2(n,k) *((1+i)/2)^(k-1).

EXAMPLE

Triangle begins

n\k|....1......2......3......4......5......6......7

===================================================

..1|....1

..2|....1......2

..3|....2......6......6

..4|....5.....22.....36.....24

..5|...16.....90....210....240....120

..6|...61....422...1260...2040...1800....720

..7|..272...2226...8106..16800..21000..15120...5040

..

Examples of recurrence relation for table entries:

T(5,2) = 2*{T(4,1)+T(4,2)+1/2*T(4,3)} = 2*(5+22+18) = 90;

T(6,1) = 1*{T(5,0)+T(5,1)+1/2*T(5,2)} = 16 + 1/2*90 = 61.

Examples of forests:

T(4,2) = 22. The 11 unordered forests consisting of 2 trees on 4 nodes are shown in the example section of A147315. Putting an order on the trees in a forest produces 2!*11 = 22 ordered forests.

MAPLE

#A185421 E := t -> sec(t)+tan(t)-1:

F := (x, t) -> 1/(1-x*E(t)) - 1:

Fser := series(F(x, t), t=0, 12):

for n from 1 to 7 do

seq(coeff(n!*coeff(Fser, t, n), x, i), i=1..n) od;

MATHEMATICA

nmax = 9; t[n_ /; n > 0, k_ /; k > 0] := t[n, k] = k*(t[n-1, k-1] + t[n-1, k] + 1/2*t[n-1, k+1]);

t[1, 1] = 1; t[0, _] = 0; t[_, 0] = 0; Flatten[Table[t[n, k], {n, 1, nmax}, {k, 1, n}]]

(* Jean-François Alcover, Jun 22 2011, after recurrence *)

PROG

(PARI) {T(n, k)=if(n<1|k<1|k>n, 0, if(n==1, 1, k*(T(n-1, k-1)+T(n-1, k)+T(n-1, k+1)/2)))}

(PARI) {T(n, k)=local(X=x+x*O(x^n)); n!*polcoeff(polcoeff(1/(1-y*((1+sin(X))/cos(X)-1))-1, n, x), k, y)}

CROSSREFS

Cf. A147315, A147309, A185423.

Sequence in context: A173869 A247377 A167909 * A219976 A063944 A086447

Adjacent sequences:  A185418 A185419 A185420 * A185422 A185423 A185424

KEYWORD

nonn,easy,tabl

AUTHOR

Peter Bala, Jan 31 2011

EXTENSIONS

Maple program corrected by Peter Luschny, Aug 02 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 April 25 08:06 EDT 2018. Contains 303048 sequences. (Running on oeis4.)