Consider the set $[n]$ and a positive integer $k$. Now consider the set $F$ of multisets $M$ of subsets of $[n]$ such that:

  • There are exactly $k$ elements in $M$
  • Subsets can appear more than once in $M$ ( So for example $M$ can contain the same subset twice)
  • Each subset $A$ in $M$ has an odd number of elements
  • Two intersecting subsets $A$ and $B$ in $M$ satisfy $A\subseteq B$ or $B\subseteq A$
  • Every element of $[n]$ belongs to at least one of the subsets in $M$.

We call two multisets $M$ and $N$ of $F$ isomorphic if there is a bijection $\sigma$ of $[n]$ such that every subset $s$ of $[n]$ appears with the same multiplicity in $M$ as $\sigma(s)$ in $N$.

How many different isomorphism types does $F$ have?

The problem when we take $n=9$ and $k=4$ is the same as the question posed in this answer.

I have been trying to write up a recursion and use it to make a table of some values, I will probably do so in the future.

  • $\begingroup$ Yeah, I do. Thanks. $\endgroup$ – Jorge Fernández Hidalgo Feb 12 '15 at 2:47
  • $\begingroup$ So what's the relation to pigs in pens? $\endgroup$ – Kundor Feb 12 '15 at 2:48
  • 1
    $\begingroup$ well, each isomorphism type gives you a different way to put a fence around the pigs. for example,when $n=3,k=5$ the isomorphism type of $M=\{\{1,2,3\},\{1,2,3\},\{1,2,3\},\{1,2,3\},\{1,2,3\}\}$ corresponds to putting all of the pigs inside one fence and then making that fence thicker(like a fence that is five fences thick). $\endgroup$ – Jorge Fernández Hidalgo Feb 12 '15 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.