Counting intersecting Families of size 2^{n-1}

Ooh, nothing makes me happier than thinking about an interesting combinatorics problem.

@algopuzzles shared this interesting puzzle in the #exportober challenge.

A family of subsets $\mathcal{F}$ from a ground set $[n]$ is an intersecting family if any two elements in the family intersect. Find an intersecting family of size $2^{n-1}$ without having a common fixed element among the elements of the family.

In one of the comments, @neeldhara had asked how many such families are there? This is an attempt to answer the question (which could possibly be incorrect - I am just giving a fair warning before you decide to spend your time reading this post. I often make mistakes in counting and overlook it).

Edit: I am answering a different question here

A family of subsets $\mathcal{F}$ from a ground set $[n]$ is an intersecting family if at least two elements in the family intersect. Find an intersecting family of size $2^{n-1}$ without having a common fixed element among the elements of the family.

Let us call a family $\mathcal{F}$ of size $2^{n-1}$ a valid family if it is an intersecting family and has no common fixed element among all the elements of the family

Think of each subset in the family as a binary string of length $n$ . Let $\mathbf{b}_1, \ldots, \mathbf{b}_{2^{n-1}}$ be the $2^{n-1}$ binary strings corresponding to some valid family $\mathcal{F}$ . Just because I like matrices, let us arrange these strings in a matrix (this is a $2^{n-1} \times n$ matrix).

$\begin{bmatrix}\dots &\mathbf{b}_1& \dots\\ & \vdots & \\ \dots & \mathbf{b}_{2^{n-1}} & \dots \end{bmatrix}$

Since these strings correspond to a valid family, it means that there are no columns that are all 1s, and there exists at least one column with at least two ones.

For ease of typing, let us denote $2^{n-1} = m$ .

Let us define the following sets :

$\mathcal{U}$ - set of all possible configurations of the above matrix.
$\mathcal{A}$ - set of all matrix configurations in which no column has all 1's.
$\mathcal{B}$ - set of all matrix configurations in which at least one column has at least 2 ones.
$\mathcal{B^c}$ - set of all matrix configurations in which all columns have at most 1 one.

So from the definition of a valid configuration, it follows that the total number of valid configurations are $|\mathcal{A} \cap \mathcal{B}|$ .

Observation 1: $\mathcal{B}^c \subseteq A$

Observation 2: $\mathcal{A} \cup \mathcal{B} = \mathcal{U}$ .

Observation 3: $|\mathcal{A} \cap \mathcal{B}| = |\mathcal{A}| - |\mathcal{B}^c|$ .

(Proof). $|\mathcal{A} \cap \mathcal{B}| = |\mathcal{A}| + |\mathcal{B}| - |\mathcal{A} \cup \mathcal{B}| = |\mathcal{A}| + (|\mathcal{U}|- |\mathcal{B}^c|) - |\mathcal{U}| = |\mathcal{A}| - |\mathcal{B}^c|$ .

Computing $|\mathcal{A}|$

$\mathcal{A}$ is the set of all matrix configurations in which no column has all 1's. Each column can be a non-all-ones column in $2^m - 1$ ways. Since there are $n$ columns, the total number of configurations in which no column is filled with all-ones is $(2^m - 1)^n$ .

Computing $|\mathcal{B}^c|$
$\mathcal{B}^c$ is the set of all matrix configurations in which all columns have at most 1 one. Each column can have at most 1 one in $(m+1)$ ways. So the total number of configurations in which all columns have at most 1 one is $(m+1)^n$

Note: The above proof holds for counting the number of valid families of any size $m > 2$ .

Please let me know if you spot some issues. Thanks 🙂