|
| |
|
|
A035342
|
|
A triangle of numbers related to the triangle A035324; generalization of Stirling numbers of second kind A008277 and Lah numbers A008297.
|
|
55
|
|
|
|
1, 3, 1, 15, 9, 1, 105, 87, 18, 1, 945, 975, 285, 30, 1, 10395, 12645, 4680, 705, 45, 1, 135135, 187425, 82845, 15960, 1470, 63, 1, 2027025, 3133935, 1595790, 370125, 43890, 2730, 84, 1, 34459425, 58437855, 33453945, 8998290
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
If one replaces in the recurrence the '2' by '0', resp. '1', one obtains the Lah-number, resp. Stirling-number of 2nd kind, triangle A008297, resp. A008277.
The product of two lower triangular Jabotinsky matrices (see A039692 for the Knuth 1992 reference) is again such a Jabotinsky matrix: J(n,m)=sum(J1(n,j)*J2(j,m),j=m..n). The e.g.f.s of the first columns of these triangular matrices are composed in the reversed order: f(x)=f2(f1(x)). With f1(x)=-(ln(1-2*x))/2 for J1(n,m)=|A039683(n,m)| and f2(x)=exp(x)-1 for J2(n,m)=A008277(n,m) one has therefore f2(f1(x))=1/sqrt(1-2*x) - 1 = f(x) for J(n,m)=a(n,m). This proves the matrix product given below. The m-th column of a Jabotinsky matrix J(n,m) has e.g.f. (f(x)^m)/m!, m>=1.
a(n,m) gives the number of forests with m rooted ordered trees with n non-root vertices labeled in an organic way. Organic labeling means that the vertex labels along the (unique) path from the root with label 0 to any leaf (non-root vertex of degree 1) is increasing. Proof: first for m=1 then for m>=2 using the recurrence relation for a(n,m) given below. W. Lang, Aug 07 2007.
|
|
|
REFERENCES
|
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO]. - From N. J. A. Sloane, Aug 21 2012
E. Neuwirth, Recursively defined combinatorial Functions: Extending Galton's board, Discr. Maths. 239 (2001) 33-51.
|
|
|
LINKS
|
Table of n, a(n) for n=1..40.
P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem.
T. Copeland, Mathemagical Forests
T. Copeland, Addendum to Mathemagical Forests
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
W. Lang, First 10 rows.
|
|
|
FORMULA
|
a(n, m) = sum(|A039683(n, j)|*S2(j, m), j=m..n) (matrix product), with S2(j, m) := A008277(j, m) (Stirling2 triangle). Priv. comm. to W. Lang by E. Neuwirth, Feb 15 2001; see also the 2001 Neuwirth reference. See the comment on products of Jabotinsky matrices.
a(n, m) = n!*A035324(n, m)/(m!*2^(n-m)), n >= m >= 1; a(n+1, m)= (2*n+m)*a(n, m)+a(n, m-1); a(n, m) := 0, n<m; a(n, 0) := 0, a(1, 1)=1.
E.g.f. of m-th column: ((x*c(x/2)/sqrt(1-2*x))^m)/m!, where c(x) = g.f. for Catalan numbers A000108.
Contribution from Vladimir Kruchinin, Mar 30 2011: (Start)
G.f. [1/sqrt(1-2*x)-1]^k=sum(n>=k, k!/n!*a(n,k)*x^n)
a(n,k) = 2^(n+k) * n! / (4^n*n*k!) * sum(j=0..n-k, (j+k) * 2^(j) * binomial(j+k-1,k-1) * binomial(2*n-j-k-1,n-1) ). (End)
Contribution from Peter Bala, Nov 25 2011: (Start)
E.g.f.: G(x,t) = exp(t*A(x)) = 1+t*x+(3*t+t^2)*x^2/2!+(15*t+9*t^2+t^3)*x^3/3!+..., where A(x) = -1 + 1/sqrt(1-2*x) satisfies the autonomous differential equation A'(x) = (1+A(x))^3.
The generating function G(x,t) satisfies the partial differential equation t*(dG/dt+G) = (1-2*x)*dG/dx, from which follows the recurrence given above.
The row polynomials are given by D^n(exp(x*t)) evaluated at x = 0, where D is the operator (1+x)^3*d/dx. Cf. A008277 (D = (1+x)*d/dx), A105278 (D = (1+x)^2*d/dx), A035469 (D = (1+x)^4*d/dx) and A049029 (D = (1+x)^5*d/dx). (End)
|
|
|
EXAMPLE
|
{1};
{3,1};
{15,9,1};
{105,87,18,1};
{945,975,285,30,1};
...
Combinatoric meaning of a(3,2)=9: The nine increasing path sequences for the three rooted ordered trees with leaves labeled with 1,2,3 and the root labels 0 are: {(0,3),[(0,1),(0,2)]}; {(0,3),[(0,2),(0,1)]}; {(0,3),(0,1,2)}; {(0,1),[(0,3),(0,2)]}; [(0,1),[(0,2),(0,3)]]; [(0,2),[(0,1),(0,3)]]; {(0,2),[(0,3),(0,1)]}; {(0,1),(0,2,3)}; {(0,2),(0,1,3)}.
|
|
|
MATHEMATICA
|
a[n_, k_] := 2^(n+k)*n!/(4^n*n*k!)*Sum[(j+k)*2^(j)*Binomial[j + k - 1, k-1]*Binomial[2*n - j - k - 1, n-1], {j, 0, n-k}]; Flatten[Table[a[n, k], {n, 1, 9}, {k, 1, n}] ] [[1 ;; 40]] (* From Jean-François Alcover, Jun 1 2011, after V. Kruchinin *)
|
|
|
PROG
|
(Maxima) a(n, k):=2^(n+k)*n!/(4^n*n*k!)*sum((j+k)*2^(j)*binomial(j+k-1, k-1)*binomial(2*n-j-k-1, n-1), j, 0, n-k) [From Vladimir Kruchinin, Mar 30 2011]
|
|
|
CROSSREFS
|
The column sequences are A001147, A035101, A035119, ... Row sums: A049118(n), n >= 1.
Cf. A000108, A035324, A008277, A008297.
Cf. A094638
Sequence in context: A038553 A135896 A134144 * A039815 A147453 A147020
Adjacent sequences: A035339 A035340 A035341 * A035343 A035344 A035345
|
|
|
KEYWORD
|
easy,nice,nonn,tabl
|
|
|
AUTHOR
|
Wolfdieter Lang
|
|
|
STATUS
|
approved
|
| |
|
|
