A309876 Number T(n,k) of k-uniform hypergraphs on n unlabeled nodes with at least one (possibly empty) hyperedge; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 10, 4, 1, 1, 5, 33, 33, 5, 1, 1, 6, 155, 2135, 155, 6, 1, 1, 7, 1043, 7013319, 7013319, 1043, 7, 1, 1, 8, 12345, 1788782616655, 29281354514767167, 1788782616655, 12345, 8, 1

Offset

0,5

Comments

A hypergraph is called k-uniform if all hyperedges have the same cardinality k.

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 0 for k>n.

Links

Alois P. Heinz, Rows n = 0..14, flattened

Jianguo Qian, Enumeration of unlabeled uniform hypergraphs, Discrete Math. 326 (2014), 66--74. MR3188989.

Wikipedia, Hypergraph

Formula

T(n,k) = A309865(n,k) - 1 = A309858(n,k) - 1.

T(n,k) = T(n,n-k) for 0 <= k <= n.

Example

T(3,0) = 1: {{}}.
T(3,1) = 3: {1}, {1,2}, {1,2,3}.
T(3,2) = 3: {12}, {12,13}, {12,13,23}.
T(3,3) = 1: {123}.
(Non-isomorphic representatives of the hypergraphs are given.)
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 2,    1;
  1, 3,    3,       1;
  1, 4,   10,       4,       1;
  1, 5,   33,      33,       5,    1;
  1, 6,  155,    2135,     155,    6, 1;
  1, 7, 1043, 7013319, 7013319, 1043, 7, 1;
  ...

Maple

g:= (l, i, n)-> `if`(i=0, `if`(n=0, [[]], []), [seq(map(x->
     [x[], j], g(l, i-1, n-j))[], j=0..min(l[i], n))]):
h:= (p, v)-> (q-> add((s-> add(`if`(andmap(i-> irem(k[i], p[i]
     /igcd(t, p[i]))=0, [$1..q]), mul((m-> binomial(m, k[i]*m
     /p[i]))(igcd(t, p[i])), i=1..q), 0), t=1..s)/s)(ilcm(seq(
    `if`(k[i]=0, 1, p[i]), i=1..q))), k=g(p, q, v)))(nops(p)):
b:= (n, i, l, v)-> `if`(n=0 or i=1, 2^((p-> h(p, v))([l[], 1$n]))
     /n!, add(b(n-i*j, i-1, [l[], i$j], v)/j!/i^j, j=0..n/i)):
T:= proc(n, k) option remember; `if`(k>n-k,
      T(n, n-k), b(n$2, [], k)-1)
    end:
seq(seq(T(n, k), k=0..n), n=0..9);

Crossrefs

Columns k=0-1 give: A000012, A001477.

Row sums give A309868.

T(2n,n) gives A328157.

Cf. A309858, A309865.

Sequence in context: A283113 A123610 A209631 * A059922 A229556 A159623

Adjacent sequences: A309873 A309874 A309875 * A309877 A309878 A309879

Keyword

nonn,tabl

Author

Peter Dolland and Alois P. Heinz, Aug 21 2019

Status

approved