[Math] An interesting combinatorics problem

combinatorics

$A$ is a set containing $n$ elements. A subset $P_1$ of $A$ is chosen. The set is reconstructed by replacing the elements of $P_1$. Then a subset $P_2$ is chosen and again the set is reconstructed by replacing the elements of $P_2$. In this way $m$ subsets $P_1,……,P_m$ are chosen where $m>1$.
Find the number of ways of choosing $P_1,…….,P_m$ such that no two of them are pairwise disjoint.

I don't have any clue how to start this problem
I tried a lot of things but couldn't even get close to a conclusion.

Edit: An equivalent (and hopefully simpler and neater) way of putting it.

Given a set $A$ with $n$ elements, let $B=(P_1,P_2 \cdots, P_m)$ be a tuple of $m$ non-empty subsets of $A$, $P_i \subset A$ such that $P_i \cap P_j \ne \varnothing$. How many different $B$ there are?

Best Answer

Hint: The following reformulation of the problem might be useful:

Consider $(0,1)$-matrices with $m$ rows and $n$ columns. Find the number of $(0,1)$-matrices so that for each two rows there is at least one position $j\ (1\leq j \leq n)$ where both rows have a $1$ at this position.

Here we consider wlog $A=[n]=\{1,2,\ldots,n\}$ and encode the subset $\emptyset\ne P_k\subset A$ with the $k$-th $(1\leq k\leq m)$ row. The position $j$ in the $k$-th row is $1$ iff $j\in P_k$.

Small values:

With the help of a little R code we obtain for small values of $m$ and $n$ the number $S(n,m)$ of admissible matrices as

$$ \begin{array}{c|rrrrrrr} m\backslash n&1&2&3&4&5&6&\cdots\\ \hline 1&1&3&7&15&31&63&\cdots\\ 2&1&7&37&175&781&3\,367&\cdots\\ 3&1&15&175&1\,827&17\,791&\cdots\\ 4&1&31&781&17\,887&\cdots\\ 5&1&63&3\,367&\cdots\\ \vdots&\\ \end{array} $$

We find in OEIS the values of $S(n,m)$ for

  • $m=1$ as A000225 the number of non-empty subsets with $n$ elements.

\begin{align*} S(n,1)&=(1,3,7,15,31,\ldots)\\ &=(2^n-1)_{n\geq 1} \end{align*}

  • $m=2$ as A005061 the number of binary $(2\times n)$-arrays with a path of adjacent $1$'s from top row to bottom row.

\begin{align*} S(n,2)&=(1,7,37,175,781,3\,367,\ldots)\\ &=(4^n-3^n)_{n\geq 1} \end{align*}

  • $m=3$ as A051588 the number of binary $(3\times n)$-matrices such that any $2$ rows have a common $1$.

\begin{align*} S(n,3)&=(1,15,175,1\,827,17\,791,\ldots)\\ &=(8^n-3\cdot 6^n+3\cdot5^n-4^n)_{n\geq 1} \end{align*}

  • $m=4$ as A051587 the number of binary $(4\times n)$-matrices such that any $2$ rows have a common $1$.

\begin{align*} S(n,4)&=(1,31,781,17\,887,\ldots)\\ &=(16^n -6\cdot 12^n +12\cdot 10^n -9^n\\ &\qquad-16\cdot 8^n +15\cdot 7^n -6\cdot 6^n +5^n)_{n\geq 1} \end{align*}

  • $m=5$ as A051589 the number of binary $(5\times n)$-matrices such that any $2$ rows have a common $1$.

\begin{align*} S(n,5)&=(1, 63, 3\,367, \ldots)\\ &=(32^n - 10\cdot 24^n + 30\cdot 20^n - 5\cdot 18^n + 5\cdot 17^n\\ &\qquad - 70\cdot 16^n - 30\cdot 15^n + 135\cdot 14^n + 30\cdot 13^n\\ &\qquad- 140\cdot 12^n - 2\cdot 11^n + 130\cdot 10^n - 110\cdot 9^n\\ &\qquad+ 45\cdot 8^n - 10\cdot 7^n + 6^n)_{n\geq 1} \end{align*}

Note: We observe that $S(n,m)$ has for $1\leq m\leq 5$ a representation as alternating sum of certain powers of $n$. When we recall that ${n\brace k}$ the Stirling numbers of the second kind gives the number of partitions of $n$ elements into $k$ non-empty subsets and a representation can be given as alternating sum of powers of $n$ \begin{align*} {n\brace k}=\frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n \end{align*} this indicates that a summation formula for $S(m,n)$ including Stirling numbers of the second kind should be within reach.

Related Question