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,1

Comments

See A000088 and A000665 for more references.

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

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.

Example

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, ...

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

Prog

(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(#L<k, listput(L, #L))); Vec(L)}
can(v, f)={my(d=1, u=v); while(d>0, 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

Crossrefs

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

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

Sequence in context: A023518 A326194 A331251 * A022921 A080763 A245920

Adjacent sequences: A309855 A309856 A309857 * A309859 A309860 A309861

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 20 2019

Status

approved