|
| |
|
|
A147315
|
|
L-matrix for Euler numbers A000111(n+1).
|
|
11
| |
|
|
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
(list; table; graph; refs; listen; history; 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 labelled 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.
|
|
|
LINKS
| F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, 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 wrt 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) = A000722(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)!, [From Vladimir Kruchinin kru(AT)ie.tusur.ru, 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 left-most 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]]
(* From Jean-François Alcover, Jun 21 2011, after PARI prog. *)
|
|
|
PROG
| (PARI) {T(n, k)=if(n<0|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(n<0|k<0|k>n, 0, if(n==k, 1, (P^n)[1, k+1]))}
/* Maxima, Vladimir Kruchinin, Feb 17 2011 */
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);
(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)!; [From Vladimir Kruchinin kru(AT)ie.tusur.ru, May 17 2011]
|
|
|
CROSSREFS
| Cf. A145876, A147309, A185421, A185422, A185424.
Sequence in context: A049020 A144634 A178125 * A085853 A185997 A182822
Adjacent sequences: A147312 A147313 A147314 * A147316 A147317 A147318
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Paul Barry (pbarry(AT)wit.ie), Nov 05 2008
|
| |
|
|
