Number of different hypergraphs realizable on N vertices

Question

I am interested in the following: Given $N$ vertices, how many different hypergraphs in total can be realized on them counting the equivalent hypergraphs only once. Consider two hypergraphs equivalent if one can be transformed into another just by relabeling the vertices (for example $\{1,2\},\{2,3\}$ on 3 vertices is equivalent to $\{2,3\},\{1,3\}$). I am not really familiar with the graph theory terminology, but this question can probably be rephrased like this: What is the number of different hypergraphs relizable on $N$ unlabeled vertices.

By exhaustion, i have found:

1) N=1 only 1 Hg

2) N=2 only 2 Hg-s

3) N=3, 5 Hg-s

4) N=4, 20 Hg-s

but these numbers might not be correct!

Thanks!

Answer 1

With this problem we basically require the cycle index of the induced action of the symmetric group $S_N$ on the powerset of the vertices. This can be done by constructing representatives of the cycle structures from $Z(S_N)$, applying them to the powersets and factoring the result, making use of the fact that the order of the subsets is constant on the orbit so we do not have to allocate them all at once, iterating over the subset size instead. Add to obtain the cycle index. We can then count hypergraphs by setting all variables to $2.$ This will yield

$$2, 4, 12, 80, 3984, 37333248, 25626412338274304, \\ 67516342973185974328175690087661568, \ldots$$

We also obtain the corresponding cycle indices e.g. for seven vertices we find

$$\frac{1}{5040} \left({a_{{1}}}^{128}+21\,{a_{{1}}}^{64}{a_{{2}}}^{32} +105\,{a_{{1}}}^{32}{a_{{2}}}^{48}+105\,{a_{{1}}}^{16}{a_{{2}}}^{56} +70\,{a_{{1}}}^{32}{a_{{3}}}^{32} \\ +420\,{a_{{1}}}^{16}{a_{{2}}}^{8}{a_{{3}}}^{16}{a_{{6}}}^{8} +210\,{a_{{1}}}^{16}{a_{{2}}}^{8}{a_{{4}}}^{24} +280\,{a_{{1}}}^{8}{a_{{3}}}^{40} +630\,{a_{{1}}}^{8}{a_{{2}}}^{12}{a_{{4}}}^{24} \\ +210\,{a_{{1}}}^{8}{a_{{2}}}^{12}{a_{{3}}}^{8}{a_{{6}}}^{12} +504\,{a_{{1}}}^{8}{a_{{5}}}^{24} +840\,{a_{{1}}}^{4}{a_{{2}}}^{2}{a_{{3}}}^{4}{a_{{6}}}^{18} \\ +420\,{a_{{1}}}^{4}{a_{{2}}}^{2}{a_{{3}}}^{4} {a_{{4}}}^{6}{a_{{6}}}^{2}{a_{{12}}}^{6} +504\,{a_{{1}}}^{4}{a_{{2}}}^{2}{a_{{5}}}^{12}{a_{{10}}}^{6} +720\,{a_{{1}}}^{2}{a_{{7}}}^{18}\right).$$

Armed with these data we discover that the sequence is OEIS A003180 and that the problem has been investigated by several authors. Among more recent work there is the paper Enumeration of hypergraphs by Toru Ishihara in the European Journal of Combinatorics, Volume 22, Issue 4, May 2001. We discover on consulting this work that the results obtained therein are a perfect match of what we have above. The author also adopts the convention of including the empty set among the hyperedges, a choice that we make as well. Note that Wikipedia says different. The algorithm proposed by the paper is simple and efficient and not at all difficult to implement, consult the Maple program shown below, which makes it possible to compute e.g. the cycle index for hypergraphs on $25$ vertices, here is an excerpt:

$$\cdots+{\frac {{a_{{1}}}^{16384}{a_{{2}}}^{57344} {a_{{3}}}^{16384}{a_{{6}}}^{319488} {a_{{5}}}^{49152}{a_{{10}}}^{172032}{a_{{15}}}^{49152}{a_ {{30}}}^{958464}}{870912000}} \\ +{\frac {{a_{{1}}}^{64}{a_{{2}}}^{224} {a_{{4}}}^{384}{a_{{8}}}^{3840}{a_{{3}}}^{1344}{a_{{6}}}^{86624}{a_ {{12}}}^{130944}{a_{{24}}}^{1309440}}{3456}} \\ +{\frac {{a_{{1}}}^{64} {a_{{3}}}^{320}{a_{{9}}}^{465920}{a_{{2}}}^{32}{a_{{6}}}^{160}{a_{{ 18}}}^{232960}{a_{{4}}}^{96}{a_{{12}}}^{480}{a_{{36}}}^{698880}}{ 3888}} \\ +{\frac {{a_{{1}}}^{128}{a_{{5}}}^{6528}{a_{{2}}}^{960}{a_{{ 10}}}^{835392}{a_{{3}}}^{128}{a_{{6}}}^{960}{a_{{15}}}^{6528}{a_{{ 30}}}^{835392}}{7200}} \\ +{\frac {{a_{{1}}}^{8192}{a_{{2}}}^{12288}{a_ {{4}}}^{122880}{a_{{8}}}^{983040}{a_{{3}}}^{8192}{a_{{6}}}^{12288}{ a_{{12}}}^{122880}{a_{{24}}}^{983040}}{348364800}}+\cdots$$

This is the code.

with(combinat); with(numtheory);

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

TI_mu :=
proc(pv)
local p, n, beta, ind, res;

    if pv = 1 then return 2 fi;

    p := op(2, ifactors(pv));
    n := nops(p);

    res := 0;

    for ind from 2^n to 2^(n+1)-1 do
        beta := convert(ind, base, 2);

        res := res +
        (-1)^add(beta[q], q=1..n)
        *2^mul(p[q][1]^(p[q][2]-beta[q]),
               q=1..n);
    od;

    res/pv;
end;

TI_rcyc :=  r -> mul(a[p]^TI_mu(p), p in divisors(r));

CART_prod :=
proc(t1, t2)
local v1, v2, l1, l2, res;

    res := 1;

    for v1 in indets(t1) do
        l1 := op(1, v1);
        for v2 in indets(t2) do
            l2 := op(1, v2);

            res := res *
            a[lcm(l1, l2)]^
            (gcd(l1, l2)
             *degree(t1, v1)
             *degree(t2, v2));
        od;
    od;

    res;
end;

CART_pow :=
proc(t, q)
local res, p;

    res := t;

    for p to q-1 do
        res := CART_prod(res, t);
    od;

    res;
end;

pet_cycleind_hypergraph :=
proc(n)
option remember;
local term, v, contr, edgidx, edgterm;

    if n = 0 then return a[1] fi;
    if n = 1 then return a[1]^2 fi;

    edgidx := 0;

    for term in pet_cycleind_symm(n) do
        edgterm := 1;

        for v in indets(term) do
            contr :=
            CART_pow(TI_rcyc(op(1, v)),
                     degree(term, v));

            if type(edgterm, `integer`) then
                edgterm := contr;
            else
                edgterm :=
                CART_prod(edgterm, contr);
            fi;
        od;

        edgidx :=
        edgidx + lcoeff(term) * edgterm;
    od;

    edgidx;
end;

hypergraph :=
proc(n)
option remember;
local idx, vars;

    idx := pet_cycleind_hypergraph(n);
    vars := indets(idx);

    subs([seq(v=2, v in vars)], idx);
end;