cp's OEIS Frontend

A072247 Triangle T(n,k) (n >= 2, 2 <= k <= n-1 if n > 2) giving number of non-crossing trees with n nodes and k endpoints.

%I A072247 #15 Sep 12 2024 19:33:46
%S A072247 1,3,8,4,20,30,5,48,144,75,6,112,560,595,154,7,256,1920,3440,1848,280,
%T A072247 8,576,6048,16380,14994,4788,468,9,1280,17920,68320,95200,52290,10920,
%U A072247 735,10,2816,50688,258720,510048,429198,155496,22638,1100,11
%N A072247 Triangle T(n,k) (n >= 2, 2 <= k <= n-1 if n > 2) giving number of non-crossing trees with n nodes and k endpoints.
%C A072247 For n > 2 the n-th row has n-2 terms.
%C A072247 The difference between this sequence and A091320 is that this sequence considers the degrees of all vertices whereas A091320 ignores the degree of the root vertex. - _Andrew Howroyd_, Nov 06 2017
%H A072247 E. Deutsch and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00366-1">Statistics on non-crossing trees</a>, Discrete Math., 254 (2002), 75-87.
%F A072247 T(n, k) = U(n, k-1) - U(n, k) + binomial(n-1, k)*Sum_{j=0..k-1} binomial(n-1, j)*binomial(n-k-1, k-1-j)*2^(n-2*k+j)/(n-1) where U(n,k) = 2*binomial(n-2, k)*Sum_{j=0..k-1} binomial(n-1, j)*binomial(n-k-2, k-1-j)*2^(n-1-2*k+j)/(n-2) for 2 < k < n. - _Andrew Howroyd_, Nov 06 2017
%e A072247 Triangle begins:
%e A072247    1;
%e A072247    3;
%e A072247    8,   4;
%e A072247   20,  30,  5;
%e A072247   48, 144, 75, 6;
%e A072247   ...
%t A072247 U[n_, k_] := 2 Binomial[n - 2, k] Sum[Binomial[n - 1, j] Binomial[n - k - 2, k - 1 - j] 2^(n - 1 - 2k + j), {j, 0, k - 1}]/(n - 2);
%t A072247 W[n_, k_] := Binomial[n - 1, k] Sum[Binomial[n - 1, j] Binomial[n - k - 1, k - 1 - j] 2^(n - 2k + j), {j, 0, k - 1}]/(n - 1);
%t A072247 T[n_, k_] := If[n < 3, n == 2 && k == 2, If[1 < k && k < n, U[n, k - 1] - U[n, k] + W[n, k]]];
%t A072247 Table[T[n, k] /. True -> 1, {n, 2, 10}, {k, 2, n-Boole[n>2]}] // Flatten (* _Jean-François Alcover_, Sep 06 2019, from PARI *)
%o A072247 (PARI)
%o A072247 U(n,k) = 2*binomial(n-2,k)*sum(j=0,k-1,binomial(n-1,j)*binomial(n-k-2,k-1-j)*2^(n-1-2*k+j))/(n-2);
%o A072247 W(n,k) = binomial(n-1, k)*sum(j=0,k-1,binomial(n-1,j)*binomial(n-k-1,k-1-j)*2^(n-2*k+j))/(n-1);
%o A072247 T(n,k) = if(n<3, n==2&&k==2, if(1<k&&k<n, U(n,k-1)-U(n,k)+W(n,k)));
%o A072247 for(n=2, 10, for(k=2, n-(n>2), print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 06 2017
%Y A072247 Column k=2 gives A001792, row sums are A001764.
%Y A072247 Cf. A091320.
%K A072247 nonn,tabf
%O A072247 2,2
%A A072247 _N. J. A. Sloane_, Jul 06 2002
%E A072247 Offset corrected by _Andrew Howroyd_, Nov 06 2017
%E A072247 More terms from _Sean A. Irvine_, Sep 12 2024