A309858 Number A(n,k) of k-uniform hypergraphs on n unlabeled nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

2, 1, 2, 1, 2, 2, 1, 1, 3, 2, 1, 1, 2, 4, 2, 1, 1, 1, 4, 5, 2, 1, 1, 1, 2, 11, 6, 2, 1, 1, 1, 1, 5, 34, 7, 2, 1, 1, 1, 1, 2, 34, 156, 8, 2, 1, 1, 1, 1, 1, 6, 2136, 1044, 9, 2, 1, 1, 1, 1, 1, 2, 156, 7013320, 12346, 10, 2, 1, 1, 1, 1, 1, 1, 7, 7013320, 1788782616656, 274668, 11, 2

Offset: 0

Author

Alois P. Heinz, Aug 20 2019

Keywords

• nonn
• tabl

Comments

See A000088 and A000665 for more references.

Examples

			Square array A(n,k) begins:
  2, 1,    1,       1,       1,    1, 1, 1, ...
  2, 2,    1,       1,       1,    1, 1, 1, ...
  2, 3,    2,       1,       1,    1, 1, 1, ...
  2, 4,    4,       2,       1,    1, 1, 1, ...
  2, 5,   11,       5,       2,    1, 1, 1, ...
  2, 6,   34,      34,       6,    2, 1, 1, ...
  2, 7,  156,    2136,     156,    7, 2, 1, ...
  2, 8, 1044, 7013320, 7013320, 1044, 8, 2, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..20, flattened
• Jianguo Qian, Enumeration of unlabeled uniform hypergraphs, Discrete Math. 326 (2014), 66--74. MR3188989.
• Wikipedia, Hypergraph

Crossrefs

Columns k=0..10 give: A007395, A000027, A000088, A000665, A051240, A051249, A309860, A309861, A309862, A309863, A309864.

Cf. A301922, A309865 (the same as triangle).

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)):
A:= proc(n, k) option remember; `if`(k>n, 1,
     `if`(k>n-k, A(n, n-k), b(n$2, [], k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

PARI

permcount(v)={my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
rep(typ)={my(L=List(), k=0); for(i=1, #typ, k+=typ[i]; listput(L, k); while(#L0, u=vecsort(apply(f, u)); d=lex(u, v)); !d}
Q(n, k, perm)={my(t=0); forsubset([n, k], v, t += can(Vec(v), t->perm[t])); t}
T(n, k)={my(s=0); forpart(p=n, s += permcount(p)*2^Q(n, k, rep(p))); s/n!} \\ Andrew Howroyd, Aug 22 2019

Formula

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

A(n,k) - A(n-1,k) = A301922(n,k) for n,k >= 1.