A091320 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves.

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

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

Row sums give A001764.

Column 2 is A276289.

Cf. A072247.

Sequence in context: A221499 A059579 A261763 * A225468 A048787 A030102

Adjacent sequences: A091317 A091318 A091319 * A091321 A091322 A091323

Keyword

nonn,tabl

Author

Emeric Deutsch, Feb 24 2004

Status

approved