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.

1, 3, 8, 4, 20, 30, 5, 48, 144, 75, 6, 112, 560, 595, 154, 7, 256, 1920, 3440, 1848, 280, 8, 576, 6048, 16380, 14994, 4788, 468, 9, 1280, 17920, 68320, 95200, 52290, 10920, 735, 10, 2816, 50688, 258720, 510048, 429198, 155496, 22638, 1100, 11

Offset: 2

Author

N. J. A. Sloane, Jul 06 2002

Keywords

• nonn
• tabf

Comments

For n > 2 the n-th row has n-2 terms.

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

Examples

			Triangle begins:
   1;
   3;
   8,   4;
  20,  30,  5;
  48, 144, 75, 6;
  ...
		

Links

• E. Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math., 254 (2002), 75-87.

Crossrefs

Column k=2 gives A001792, row sums are A001764.

Cf. A091320.

Programs

Mathematica

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);
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[n_, k_] := If[n < 3, n == 2 && k == 2, If[1 < k && k < n, U[n, k - 1] - U[n, k] + W[n, k]]];
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 *)

PARI

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);
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);
T(n,k) = if(n<3, n==2&&k==2, if(12), print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 06 2017

Formula

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

Extensions

Offset corrected by Andrew Howroyd, Nov 06 2017

More terms from Sean A. Irvine, Sep 12 2024