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
Andrew Howroyd, Table of n, a(n) for n = 1..1275
Alexander Burstein, Megan Martinez, Pattern classes equinumerous to the class of ternary forests, Permutation Patterns Virtual Workshop, Howard University (2020).
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.
Donovan Young, Polyomino matchings in generalised games of memory and linear k-chord diagrams, arXiv:2004.06921 [math.CO], 2020. See also J. Int. Seq., Vol. 23 (2020), Article 20.9.1.
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}];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 29 2018 *)
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
nonn,tabl
AUTHOR
Emeric Deutsch, Feb 24 2004
STATUS
approved