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
Examples
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;
...
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
Crossrefs
Programs
-
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);
Comments