|
| |
|
|
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 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)
|
|
|
LINKS
|
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
|
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)
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 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;
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)
|
|
|
MAPLE
|
A147315 := proc(n, k) n!*exp(x*(sec(t)+tan(t)-1)) - 1: coeftayl(%, t=0, n) ; coeftayl(%, x=0, k) ; end proc:
# 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)):
|
|
|
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 */
# Adds a column 1, 0, 0, 0, ... at the left side of the triangle.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
