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

%I #36 Jan 29 2021 20:46:18

%S 1,2,1,4,7,1,8,30,16,1,16,104,122,30,1,32,320,660,365,50,1,64,912,

%T 2920,2875,903,77,1,128,2464,11312,17430,9856,1960,112,1,256,6400,

%U 39872,88592,78974,28560,3864,156,1,512,16128,130944,396480,512316,294042,73008,7074,210,1

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

%C 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

%C 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

%H Andrew Howroyd, <a href="/A091320/b091320.txt">Table of n, a(n) for n = 1..1275</a>

%H Alexander Burstein, Megan Martinez, <a href="https://permutationpatterns.com/files/2020/06/WednesdayA_Burstein.pdf">Pattern classes equinumerous to the class of ternary forests</a>, Permutation Patterns Virtual Workshop, Howard University (2020).

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.

%H M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00121-0">Enumeration of noncrossing trees on a circle</a>, Discrete Math., 180, 301-313, 1998.

%H Donovan Young, <a href="https://arxiv.org/abs/2004.06921">Polyomino matchings in generalised games of memory and linear k-chord diagrams</a>, arXiv:2004.06921 [math.CO], 2020. See also <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Young/young5.html">J. Int. Seq.</a>, Vol. 23 (2020), Article 20.9.1.

%F 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).

%F G.f.: G(t, z) satisfies z*G^3 - (1 + z - t*z)*G + 1 = 0.

%e Triangle starts:

%e 1;

%e 2, 1;

%e 4, 7, 1;

%e 8, 30, 16, 1;

%e 16, 104, 122, 30, 1;

%e 32, 320, 660, 365, 50, 1;

%e ...

%p 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);

%t 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}];

%t Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 29 2018 *)

%o (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

%Y Row sums give A001764.

%Y Column 2 is A276289.

%Y Cf. A072247.

%K nonn,tabl

%O 1,2

%A _Emeric Deutsch_, Feb 24 2004