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,2

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

Links

Table of n, a(n) for n=2..47.

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

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

Example

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

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 *)

Prog

(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(1<k&&k<n, U(n, k-1)-U(n, k)+W(n, k)));
for(n=2, 10, for(k=2, n-(n>2), print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 06 2017

Crossrefs

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

Cf. A091320.

Sequence in context: A303217 A106292 A336884 * A051359 A322470 A016670

Adjacent sequences: A072244 A072245 A072246 * A072248 A072249 A072250

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jul 06 2002

Extensions

Offset corrected by Andrew Howroyd, Nov 06 2017

More terms from Sean A. Irvine, Sep 12 2024

Status

approved