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