0,4

This is the inverse of the coefficient array for the orthogonal polynomials p(n,x) defined by: p(n,x)=if(n=-1,0,if(n=0,1,(x-n)p(n-1,x)-C(n,2)p(n-2,x))).

The Hankel array H for A000111(n+1) satisfies H=L*D*U with U the transpose of L.

Row sums are A000772(n+1) with e.g.f. dif(exp(-1)exp(sec(x)+tan(x)),x). The following comments refer to the table with an offset of 1: i.e., both the row and column indexing starts at 1.

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>=1 enumerates the number 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 entry T(n,k) of the present table counts forests of k increasing unordered trees on the vertex set {1,2,...,n} in which all outdegrees are <=2. See below for some examples.

For ordered forests of such trees see A185421. For forests of increasing ordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <=2, see A185422.

The Stirling number of the second kind Stirling2(n,k) counts the partitions of the set [n] 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, which counts increasing unary-binary trees, as generalized Stirling numbers of the second kind associated with A000111 or with the zigzag polynomials Z(n,x) of A147309 - see especially formulas (2) and (3) below.

See A145876 for generalized Eulerian numbers associated with A000111.

Table of n, a(n) for n=0..54.

P. Barry, A Note on Three Families of Orthogonal Polynomials defined by Circular Functions, and Their Moment Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.7.2.

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.

T. Copeland, Mathemagical Forests

Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565

From Peter Bala: (Start)

The following formulas refer to the table with an offset of 1: i.e., both the row n and column k indexing start at 1.

GENERATING FUNCTION

E.g.f.:

(1)... exp(x*(sec(t)+tan(t)-1)) - 1 = sum(n>=1, R(n,x)*t^n/n! )

= x*t+(x+x^2)*t^2/2!+(2*x+3*x^2+x^3)*t^3/3!+....

TABLE ENTRIES

(2)... T(n,k) = 1/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.

Compare (2) with the formula for the Stirling numbers of the second kind

(3)... Stirling2(n,k) = 1/k!*sum {j=0..k}(-1)^(k-j)*binomial(k,j)*j^n.

Recurrence relation

(4)... T(n+1,k) = T(n,k-1)+k*T(n,k)+1/2*k(k+1)*T(n,k+1).

ROW POLYNOMIALS

The row polynomials R(n,x) begin

R(1,x) = x

R(2,x) = x+x^2

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

They satisfy the recurrence

(5)... R(n+1,x) = x*{R(n,x)+R'(n,x)+1/2*R''(n,x)},

where ' indicates differentiation with respect to x. This should be compared with the recurrence satisfied by the Bell polynomials Bell(n,x)

(6)... Bell(n+1,x) = x*(Bell(n,x)+Bell'(n,x)).

(End)

From Vladimir Kruchinin, Feb 17 2011: (Start)

sum_{m=1..n} T(n,m) = A000772(n).

sum_{m=1..2n-1} T(2n-1,m)* Stirling1(m,1) = A000364(n).

Let Co(n,k) = sum_{j=1..k} binomial(k,j)*(if (n-k+j) is odd then 0 else if (n-k+j)/2<j then 0 else j) *2^(-n+k+1) *binomial(n-k-1,(n-k+j)/2-1)/(n-k+j)) *(-1)^j))) + kron_delta(n,k), then

T(n,m) =m!* sum_{k=m..n} (if n-k is odd then 0 else 2^(1-k)) *sum_{i=0..floor(k/2)}(-1)^(floor((n+k)/2)-i) *binomial(k,i) *(2*i-k)^n))))* sum{i=1..k} Co(i,m) *binomial(k-i+m-1,m-1), n>0.

(End)

T(n,m)=(sum(k=0..n-m, binomial(k+m,m)*((-1)^(n-k-m)+1)*sum(j=0..n-k-m, binomial(j+k+m,k+m)*(j+k+m+1)!*2^(-j-k-1)*(-1)^((n+k+m)/2+j+k+m) *stirling2(n+1,j+k+m+1))))/(m+1)!. - Vladimir Kruchinin, May 17 2011

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/2!)*d/dt. Cf. A008277 and A094198. See also A185422. - Peter Bala, Nov 25 2011

Triangle begins

1,

1, 1,

2, 3, 1,

5, 11, 6, 1,

16, 45, 35, 10, 1,

61, 211, 210, 85, 15, 1,

272, 1113, 1351, 700, 175, 21, 1

The production array for L is the tri-diagonal array

1, 1,

1, 2, 1,

0, 3, 3, 1,

0, 0, 6, 4, 1,

0, 0, 0, 10, 5, 1,

0, 0, 0, 0, 15, 6, 1,

0, 0, 0, 0, 0, 21, 7, 1,

0, 0, 0, 0, 0, 0, 28, 8, 1,

0, 0, 0, 0, 0, 0, 0, 36, 9, 1

Examples of forests:

The diagrams below are drawn so that the leftmost child of a binary node has the maximum label.

T(4,1) = 5. The 5 forests consisting of a single non-plane increasing unary-binary tree on 4 nodes are

...4... ........ .......... ........... ...........

...|... ........ .......... ........... ...........

...3... .4...3.. .4........ ........4.. ........3..

...|... ..\./... ..\....... ......./... ......./...

...2... ...2.... ...3...2.. ..3...2.... ..4...2....

...|... ...|.... ....\./... ...\./..... ...\./.....

...1... ...1.... .....1.... ....1...... ....1......

T(4,2) = 11. The 11 forests consisting of two non-plane increasing unary-binary trees on 4 nodes are

......... ...3.....

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

..\./.... ...2.....

...1...4. ...|.....

......... ...1...4.

.

......... ...4.....

.4...2... ...|.....

..\./.... ...2.....

...1...3. ...|.....

......... ...1...3.

.

......... ...4.....

.4...3... ...|.....

..\./.... ...3.....

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

......... ...1...2.

.

......... ...4.....

.4...3... ...|.....

..\./.... ...3.....

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

......... ...2...1.

.

......... ......... ..........

..2..4... ..3..4... ..4...3...

..|..|... ..|..|... ..|...|...

..1..3... ..1..2... ..1...2...

......... ......... ..........

A147315 := proc(n, k) n!*exp(x*(sec(t)+tan(t)-1)) - 1: coeftayl(%, t=0, n) ; coeftayl(%, x=0, k) ; end proc:

seq(seq(A147315(n, k), k=1..n), n=0..12) ; # R. J. Mathar, Mar 04 2011

t[n_, k_] := t[n, k] = t[n-1, k-1] + (k+1)*t[n-1, k] + 1/2*(k+1)*(k+2)*t[n-1, k+1]; t[n_, k_] /; (n < 0 || k < 0 || k > n) = 0; t[0, 0] = t[1, 0] = 1; Flatten[Table[t[n, k], {n, 0, 9}, {k, 0, n}]][[1 ;; 47]] (* Jean-François Alcover, Jun 21 2011, after PARI prog. *)

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

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

(PARI) /* Generate from the production matrix P: */

{T(n, k)=local(P=matrix(n, n, r, c, if(r==c-1, 1, if(r==c, c, if(r==c+1, c*(c+1)/2))))); if(k<0||k>n, 0, if(n==k, 1, (P^n)[1, k+1]))}

(Maxima)

Co(n, k):=sum(binomial(k, j)*(if oddp(n-k+j) then 0 else if (n-k+j)/2<j then 0 else j*2^(-n+k+1)*binomial(n-k-1, (n-k+j)/2-1)/(n-k+j))*(-1)^j, j, 1, k)+kron_delta(n, k);

A147315(n, m):=1/m!*sum((if oddp(n-k) then 0 else 2^(1-k)*sum((-1)^(floor((n+k)/2)-i)*binomial(k, i)*(2*i-k)^n, i, 0, floor(k/2)))*(sum(Co(i, m)*binomial(k-i+m-1, m-1), i, 1, k)), k, m, n); /* Vladimir Kruchinin, Feb 17 2011 */

(Maxima) T(n, m):=(sum(binomial(k+m, m)*((-1)^(n-k-m)+1)*sum(binomial(j+k+m, k+m)*(j+k+m+1)!*2^(-j-k-1)*(-1)^((n+k+m)/2+j+k+m)*stirling2(n+1, j+k+m+1), j, 0, n-k-m), k, 0, n-m))/(m+1)!; /* Vladimir Kruchinin, May 17 2011 */

Cf. A145876, A147309, A185421, A185422, A185424.

Sequence in context: A049020 A144634 A178125 * A085853 A185997 A231733

Adjacent sequences:  A147312 A147313 A147314 * A147316 A147317 A147318

nonn,tabl

Paul Barry, Nov 05 2008

More terms from Michel Marcus, Mar 01 2014

approved