A091320 -id:A091320 - 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.

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

N. J. A. Sloane, Jul 06 2002

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

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

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

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

Cf. A091320.

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

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

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

Offset corrected by Andrew Howroyd, Nov 06 2017

More terms from Sean A. Irvine, Sep 12 2024

A334062 Triangle read by rows: T(n,k) is the number of non-crossing set partitions of {1..4n} into n sets of 4 with k of the sets being a contiguous set of elements.

Original entry on oeis.org

1, 3, 1, 9, 12, 1, 27, 81, 31, 1, 81, 432, 390, 65, 1, 243, 2025, 3330, 1365, 120, 1, 729, 8748, 22815, 17415, 3909, 203, 1, 2187, 35721, 135513, 166320, 70938, 9730, 322, 1, 6561, 139968, 728028, 1312038, 911358, 242004, 21816, 486, 1, 19683, 531441, 3630420, 9032310, 9294264, 4067658, 722316, 45090, 705, 1

Offset: 1

Donovan Young, May 28 2020

T(n,k) is also the number of non-crossing configurations with exactly k polyomino matchings in a generalized game of memory played on the path of length 4n, see [Young].
For the case of partitions of {1..3n} into sets of 3, see A091320.
For the case of partitions of {1..2n} into sets of 2, see A001263.

			Triangle starts:
    1;
    3,    1;
    9,   12,    1;
   27,   81,   31,    1;
   81,  432,  390,   65,   1;
  243, 2025, 3330, 1365, 120, 1;
  ...
For n=2 and k=1 the configurations are (1,6,7,8),(2,3,4,5), (1,2,7,8),(3,4,5,6), and (1,2,3,8),(4,5,6,7); hence T(2,1) = 3.

Donovan Young, Linear k-Chord Diagrams, arXiv:2004.06921 [math.CO], 2020.

Row sums are A002293.
Column 2 is A069996.
Cf. A001263, A091320, A334063.

G.f.: G(t, z) satisfies z*G^4 - (1 + z - t*z)*G + 1 = 0.

A334063 Triangle read by rows: T(n,k) is the number of non-crossing set partitions of {1..5n} into n sets of 5 with k of the sets being a contiguous set of elements.

Original entry on oeis.org

1, 4, 1, 16, 18, 1, 64, 168, 52, 1, 256, 1216, 936, 121, 1, 1024, 7680, 11040, 3760, 246, 1, 4096, 44544, 103040, 67480, 12264, 455, 1, 16384, 243712, 827904, 888160, 318976, 34524, 784, 1, 65536, 1277952, 5992448, 9554944, 5716704, 1254512, 86980, 1278, 1

Offset: 1

Donovan Young, May 28 2020

T(n,k) is also the number of non-crossing configurations with exactly k polyomino matchings in a generalized game of memory played on the path of length 5n, see [Young].
For the case of partitions of {1..4n} into sets of 4, see A334062.
For the case of partitions of {1..3n} into sets of 3, see A091320.
For the case of partitions of {1..2n} into sets of 2, see A001263.

			Triangle starts:
     1;
     4,    1;
    16,   18,     1;
    64,  168,    52,    1;
   256, 1216,   936,  121,   1;
  1024, 7680, 11040, 3760, 246,  1;
  ...
For n = 2 and k = 1 the configurations are (1,7,8,9,10), (2,3,4,5,6), (1,2,8,9,10),(3,4,5,6,7), (1,2,3,9,10), (4,5,6,7,8) and (1,2,3,4,10), (5,6,7,8,9); hence T(2,1) = 4.

Donovan Young, Linear k-Chord Diagrams, arXiv:2004.06921 [math.CO], 2020.

Row sums are A002294.

Cf. A001263, A091320, A334062.

G.f.: G(t, z) satisfies z*G^5 - (1 + z - t*z)*G + 1 = 0.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A334062 Triangle read by rows: T(n,k) is the number of non-crossing set partitions of {1..4n} into n sets of 4 with k of the sets being a contiguous set of elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A334063 Triangle read by rows: T(n,k) is the number of non-crossing set partitions of {1..5n} into n sets of 5 with k of the sets being a contiguous set of elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula