|
|
A091320
|
|
Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves.
|
|
4
|
|
|
1, 2, 1, 4, 7, 1, 8, 30, 16, 1, 16, 104, 122, 30, 1, 32, 320, 660, 365, 50, 1, 64, 912, 2920, 2875, 903, 77, 1, 128, 2464, 11312, 17430, 9856, 1960, 112, 1, 256, 6400, 39872, 88592, 78974, 28560, 3864, 156, 1, 512, 16128, 130944, 396480, 512316, 294042, 73008, 7074, 210, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
T(n,k) is the number of even trees with 2n edges and k-1 jumps. An even tree is an ordered tree in which each vertex has an even outdegree. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 19 2007
T(n,k) is the number of non-crossing set partitions of {1..3n} into n sets of 3 with k of the sets being a contiguous set of elements; also the number of non-crossing configurations with exactly k polyomino matchings in a generalized game of memory played on the path of length 3n, see [Young]. - Donovan Young, May 29 2020
|
|
LINKS
|
|
|
FORMULA
|
T(n, k) = (1/n)*binomial(n, k)*Sum_{j=0..n} 2^(n+1-2*k+j)*binomial(n, j)*binomial(n-k, k-1-j).
G.f.: G(t, z) satisfies z*G^3 - (1 + z - t*z)*G + 1 = 0.
|
|
EXAMPLE
|
Triangle starts:
1;
2, 1;
4, 7, 1;
8, 30, 16, 1;
16, 104, 122, 30, 1;
32, 320, 660, 365, 50, 1;
...
|
|
MAPLE
|
T := proc(n, k) if k=n then 1 else (1/n)*binomial(n, k)*sum(2^(n+1-2*k+j)*binomial(n, j)*binomial(n-k, k-1-j), j=0..n) fi end: seq(seq(T(n, k), k=1..n), n=1..12);
|
|
MATHEMATICA
|
T[n_, k_] := 1/n Binomial[n, k] Sum[2^(n+1-2k+j) Binomial[n, j] Binomial[n-k, k-1-j], {j, 0, n}];
|
|
PROG
|
(PARI) T(n, k) = binomial(n, k)*sum(j=0, n, 2^(n+1-2*k+j)*binomial(n, j)*binomial(n-k, k-1-j))/n; \\ Andrew Howroyd, Nov 06 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|