cp's OEIS Frontend

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

%I A091320 #41 Apr 18 2025 13:15:28
%S A091320 1,2,1,4,7,1,8,30,16,1,16,104,122,30,1,32,320,660,365,50,1,64,912,
%T A091320 2920,2875,903,77,1,128,2464,11312,17430,9856,1960,112,1,256,6400,
%U A091320 39872,88592,78974,28560,3864,156,1,512,16128,130944,396480,512316,294042,73008,7074,210,1
%N A091320 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves.
%C A091320 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 A091320 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 A091320 Andrew Howroyd, <a href="/A091320/b091320.txt">Table of n, a(n) for n = 1..1275</a>
%H A091320 Paul Barry, <a href="https://arxiv.org/abs/2504.09719">Notes on Riordan arrays and lattice paths</a>, arXiv:2504.09719 [math.CO], 2025. See pp. 28-29.
%H A091320 Alexander Burstein and 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 A091320 Philippe Flajolet and Marc 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 A091320 Marc 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 A091320 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 A091320 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 A091320 G.f.: G(t, z) satisfies z*G^3 - (1 + z - t*z)*G + 1 = 0.
%e A091320 Triangle starts:
%e A091320    1;
%e A091320    2,   1;
%e A091320    4,   7,   1;
%e A091320    8,  30,  16,   1;
%e A091320   16, 104, 122,  30,  1;
%e A091320   32, 320, 660, 365, 50, 1;
%e A091320   ...
%p A091320 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 A091320 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 A091320 Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 29 2018 *)
%o A091320 (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 A091320 Row sums give A001764.
%Y A091320 Column 2 is A276289.
%Y A091320 Cf. A072247.
%K A091320 nonn,tabl
%O A091320 1,2
%A A091320 _Emeric Deutsch_, Feb 24 2004