# How many such families exist? (Placing pigs into pens)

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.

• Yeah, I do. Thanks. – Jorge Fernández Hidalgo Feb 12 '15 at 2:47
• So what's the relation to pigs in pens? – Kundor Feb 12 '15 at 2:48
• 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). – Jorge Fernández Hidalgo Feb 12 '15 at 2:52