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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A147315 L-matrix for Euler numbers A000111(n+1). 14
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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

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

LINKS

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

FORMULA

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

EXAMPLE

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

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

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

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

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 */

(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: A000111(n+1), 10) # Peter Luschny, Jan 18 2016

CROSSREFS

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

Sequence in context: A299105 A144634 A178125 * A085853 A185997 A231733

Adjacent sequences:  A147312 A147313 A147314 * A147316 A147317 A147318

KEYWORD

nonn,tabl

AUTHOR

Paul Barry, Nov 05 2008

EXTENSIONS

More terms from Michel Marcus, Mar 01 2014

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 October 23 05:44 EDT 2018. Contains 316519 sequences. (Running on oeis4.)