A135021 Triangle read by rows: T(n,r) = number of maximum r-uniform acyclic hypergraphs of order n and size n-r+1, 1 <= r <= n+1.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 16, 6, 1, 1, 1, 125, 70, 10, 1, 1, 1, 1296, 1215, 200, 15, 1, 1, 1, 16807, 27951, 5915, 455, 21, 1, 1, 1, 262144, 799708, 229376, 20230, 896, 28, 1, 1, 1, 4782969, 27337500, 10946964, 1166886, 55566, 1596, 36, 1, 1, 1, 100000000, 1086190605, 618435840, 82031250, 4429152, 131250, 2640, 45, 1, 1

Offset

0,8

Comments

T(n,r) is the number of (r-1)-trees on n nodes. - Andrew Howroyd, Mar 02 2024

Links

G. C. Greubel, Table of n, a(n) for n = 0..1325 (rows 0..50)

L. W. Beineke and R. E. Pipert, The number of labeled k-dimensional trees, J. Comb. Theory 6 (2) (1969) 200-205, formula (1).

Jian-fang Wang and Hai-zhu Li, Enumeration of Maximum Acyclic Hypergraphs, Acta Mathematicae Applicatae Sinica, English Series, 2002 vol.18 number 2, page 215. [Broken link]

Formula

T(n,r) = binomial(n,r-1)*(n*(r-1)-r^2+2*r)^(n-r-1).

Example

From Bruno Berselli, Dec 08 2012: (Start)
Triangle begins:
  1;
  1,       1;
  1,       1,        1;
  1,       3,        1,        1;
  1,      16,        6,        1,       1;
  1,     125,       70,       10,       1,     1;
  1,    1296,     1215,      200,      15,     1,    1;
  1,   16807,    27951,     5915,     455,    21,    1,  1;
  1,  262144,   799708,   229376,   20230,   896,   28,  1, 1;
  1, 4782969, 27337500, 10946964, 1166886, 55566, 1596, 36, 1, 1;
(End)

Maple

seq(seq(binomial(n, r-1)*(n*(r-1)-r^2+2*r)^(n-r-1), r=1..n), n=1..11);

Mathematica

T[n_, r_] := Binomial[n, r - 1]*(n (r - 1) - r^2 + 2 r)^(n - r - 1);
Table[T[n, r], {n, 1, 5}, {r, 1, n}] (* G. C. Greubel, Sep 16 2016 *)

Prog

(PARI) T(n, r) = binomial(n, r-1)*(n*(r-1)-r^2+2*r)^(n-r-1) \\ Andrew Howroyd, Mar 02 2024

Crossrefs

Columns 1..5 are A000012, A000272, A036361, A036362, A036506.

Cf. A370770 (unlabeled version).

Sequence in context: A284578 A070989 A274741 * A347811 A320412 A286591

Adjacent sequences: A135018 A135019 A135020 * A135022 A135023 A135024

Keyword

easy,nonn,tabl

Author

John Nnamdi (john_info_2008(AT)bbvczx.com), Feb 10 2008

Extensions

Diagonal r=n+1 inserted by Andrew Howroyd, Mar 02 2024

Status

approved