A147315 L-matrix for Euler numbers A000111(n+1).

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, 1385, 6551, 9366, 5901, 1890, 322, 28, 1, 7936, 42585, 70055, 51870, 20181, 4410, 546, 36, 1, 50521, 303271, 563970, 479345, 218925, 58107, 9240, 870, 45, 1

Offset: 0

Author

Paul Barry, Nov 05 2008

Keywords

• nonn
• tabl

Comments

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).

From Peter Bala, Jan 31 2011: (Start)

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 gives the number of 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) is the number of 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. (End)

The Bell transform of A000111(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

Examples

			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 tridiagonal 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;
From _Peter Bala_, Jan 31 2011: (Start)
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...
......... ......... .......... (End)
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Paul 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.
• Tom Copeland, Mathemagical Forests
• Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.

Crossrefs

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

Programs

Maple

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
# second Maple program:
b:= proc(u, o) option remember;
      `if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
    end:
g:= proc(n) option remember; expand(`if`(n=0, 1, add(
      g(n-j)*x*binomial(n-1, j-1)*b(j, 0), j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n+1))(g(n+1)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 19 2021

Mathematica

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. *)

Maxima

Co(n,k):=sum(binomial(k,j)*(if oddp(n-k+j) then 0 else if (n-k+j)/2A147315(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 */

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]))}

Sage

# uses[bell_matrix from A264428, A000111]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A000111(n+1), 10) # Peter Luschny, Jan 18 2016

Formula

From Peter Bala, Jan 31 2011: (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

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

Extensions

More terms from Michel Marcus, Mar 01 2014

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.