|
%I #90 Dec 17 2022 02:53:50
%S 1,1,1,2,3,1,5,11,6,1,16,45,35,10,1,61,211,210,85,15,1,272,1113,1351,
%T 700,175,21,1,1385,6551,9366,5901,1890,322,28,1,7936,42585,70055,
%U 51870,20181,4410,546,36,1,50521,303271,563970,479345,218925,58107,9240,870,45,1
%N L-matrix for Euler numbers A000111(n+1).
%C 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))).
%C The Hankel array H for A000111(n+1) satisfies H=L*D*U with U the transpose of L.
%C Row sums are A000772(n+1) with e.g.f. dif(exp(-1)exp(sec(x)+tan(x)),x).
%C From _Peter Bala_, Jan 31 2011: (Start)
%C The following comments refer to the table with an offset of 1: i.e., both the row and column indexing starts at 1.
%C 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.])
%C 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.
%C 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.
%C 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.
%C See A145876 for generalized Eulerian numbers associated with A000111. (End)
%C The Bell transform of A000111(n+1). For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 18 2016
%H Alois P. Heinz, <a href="/A147315/b147315.txt">Rows n = 0..140, flattened</a>
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry3/barry84r2.html">A Note on Three Families of Orthogonal Polynomials defined by Circular Functions, and Their Moment Sequences</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.7.2.
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of increasing trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H Tom Copeland, <a href="https://tcjpn.wordpress.com/2008/06/12/mathemagical-forests/">Mathemagical Forests</a>
%H Vladimir Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.
%F From _Peter Bala_, Jan 31 2011: (Start)
%F 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.
%F GENERATING FUNCTION
%F E.g.f.:
%F (1)... exp(x*(sec(t)+tan(t)-1)) - 1 = Sum_{n>=1} R(n,x)*t^n/n!
%F = x*t + (x+x^2)*t^2/2! + (2*x+3*x^2+x^3)*t^3/3! + ....
%F TABLE ENTRIES
%F (2)... T(n,k) = (1/k!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*Z(n,j),
%F where Z(n,x) denotes the zigzag polynomials as described in A147309.
%F Compare (2) with the formula for the Stirling numbers of the second kind
%F (3)... Stirling2(n,k) = (1/k!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*j^n.
%F Recurrence relation
%F (4)... T(n+1,k) = T(n,k-1) + k*T(n,k) + (1/2)*k(k+1)*T(n,k+1).
%F ROW POLYNOMIALS
%F The row polynomials R(n,x) begin
%F R(1,x) = x
%F R(2,x) = x+x^2
%F R(3,x) = 2*x+3*x^2+x^3
%F They satisfy the recurrence
%F (5)... R(n+1,x) = x*{R(n,x)+R'(n,x) + (1/2)*R''(n,x)},
%F where ' indicates differentiation with respect to x. This should be compared with the recurrence satisfied by the Bell polynomials Bell(n,x)
%F (6)... Bell(n+1,x) = x*(Bell(n,x) + Bell'(n,x)). (End)
%F From _Vladimir Kruchinin_, Feb 17 2011: (Start)
%F Sum_{m=1..n} T(n,m) = A000772(n).
%F Sum_{m=1..2n-1} T(2n-1,m)* Stirling1(m,1) = A000364(n).
%F 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
%F 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.
%F (End)
%F 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
%F 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
%e Triangle begins
%e 1;
%e 1, 1;
%e 2, 3, 1;
%e 5, 11, 6, 1;
%e 16, 45, 35, 10, 1;
%e 61, 211, 210, 85, 15, 1;
%e 272, 1113, 1351, 700, 175, 21, 1;
%e ...
%e The production array for L is the tridiagonal array
%e 1, 1;
%e 1, 2, 1;
%e 0, 3, 3, 1;
%e 0, 0, 6, 4, 1;
%e 0, 0, 0, 10, 5, 1;
%e 0, 0, 0, 0, 15, 6, 1;
%e 0, 0, 0, 0, 0, 21, 7, 1;
%e 0, 0, 0, 0, 0, 0, 28, 8, 1,;
%e 0, 0, 0, 0, 0, 0, 0, 36, 9, 1;
%e From _Peter Bala_, Jan 31 2011: (Start)
%e Examples of forests:
%e The diagrams below are drawn so that the leftmost child of a binary node has the maximum label.
%e T(4,1) = 5. The 5 forests consisting of a single non-plane increasing unary-binary tree on 4 nodes are
%e ...4... ........ .......... ........... ...........
%e ...|... ........ .......... ........... ...........
%e ...3... .4...3.. .4........ ........4.. ........3..
%e ...|... ..\./... ..\....... ......./... ......./...
%e ...2... ...2.... ...3...2.. ..3...2.... ..4...2....
%e ...|... ...|.... ....\./... ...\./..... ...\./.....
%e ...1... ...1.... .....1.... ....1...... ....1......
%e T(4,2) = 11. The 11 forests consisting of two non-plane increasing unary-binary trees on 4 nodes are
%e ......... ...3.....
%e .3...2... ...|.....
%e ..\./.... ...2.....
%e ...1...4. ...|.....
%e ......... ...1...4.
%e .
%e ......... ...4.....
%e .4...2... ...|.....
%e ..\./.... ...2.....
%e ...1...3. ...|.....
%e ......... ...1...3.
%e .
%e ......... ...4.....
%e .4...3... ...|.....
%e ..\./.... ...3.....
%e ...1...2. ...|.....
%e ......... ...1...2.
%e .
%e ......... ...4.....
%e .4...3... ...|.....
%e ..\./.... ...3.....
%e ...2...1. ...|.....
%e ......... ...2...1.
%e .
%e ......... ......... ..........
%e ..2..4... ..3..4... ..4...3...
%e ..|..|... ..|..|... ..|...|...
%e ..1..3... ..1..2... ..1...2...
%e ......... ......... .......... (End)
%p A147315 := proc(n,k) n!*exp(x*(sec(t)+tan(t)-1)) - 1: coeftayl(%,t=0,n) ; coeftayl(%,x=0,k) ; end proc:
%p seq(seq(A147315(n,k),k=1..n),n=0..12) ; # _R. J. Mathar_, Mar 04 2011
%p # second Maple program:
%p b:= proc(u, o) option remember;
%p `if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
%p end:
%p g:= proc(n) option remember; expand(`if`(n=0, 1, add(
%p g(n-j)*x*binomial(n-1, j-1)*b(j, 0), j=1..n)))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n+1))(g(n+1)):
%p seq(T(n), n=0..10); # _Alois P. Heinz_, May 19 2021
%t 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. *)
%o (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 */
%o (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 */
%o (PARI) /* Generate from the production matrix P: */
%o {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]))}
%o (Maxima)
%o 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);
%o 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 */
%o (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 */
%o (Sage) # uses[bell_matrix from A264428, A000111]
%o # Adds a column 1,0,0,0, ... at the left side of the triangle.
%o bell_matrix(lambda n: A000111(n+1), 10) # _Peter Luschny_, Jan 18 2016
%Y Cf. A145876, A147309, A185421, A185422, A185424.
%K nonn,tabl
%O 0,4
%A _Paul Barry_, Nov 05 2008
%E More terms from _Michel Marcus_, Mar 01 2014
|
