How to count the $r$-tuples of subsets of $\{1,\dots,n\}$ that are cyclically disjoint?

Question

I want to count the following,

$$\#\{S_1,S_2,\dots, S_r\subseteq[n]\;|\; S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq r-1 \mbox{ and } S_1\cap S_r=\emptyset\}=A_{n,r},$$

Then $A_{n,1}=2^n$,

$$A_{n,2} =\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}=\sum_{a_1=0}^{n}\binom{n}{a_1}2^{n-a_1}=3^n$$

\begin{align*} A_{n,3} &=\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}\sum_{a_3=0}^{n-a_2-a_1}\binom{n-a_2-a_1}{a_3}\\ &=\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}2^{n-a_2-a_1}\\ &=\sum_{a_1=0}^{n}\binom{n}{a_1}3^{n-a_1}\\ &=4^n. \end{align*}

when counting $A_{n,4}$, the problem comes, I cannot do it like following,

$$A_{n,4} =\sum_{a_1=0}^{n}\binom{n}{a_1}\sum_{a_2=0}^{n-a_1}\binom{n-a_1}{a_2}\sum_{a_3=0}^{n-a_2}\binom{n-a_2}{a_3}\sum_{a_4=0}^{n-a_3-a_1}\binom{n-a_3-a_1}{a_4}$$

instead, for the last term, I need to choose $a_4$ from n- union of $a_1$ and $a_3$

How can I do it? or is there any other method to do it?

Answer 1

The pattern is obvious! $A_{n,4}=7^n$.

Well, maybe not totally obvious, but here is a proof is by induction.

First, $A_{1,4}=7$ is verified by listing out the possibilities: $(\emptyset,\emptyset,\emptyset,\emptyset),(1,\emptyset,\emptyset,\emptyset),(\emptyset,1,\emptyset,\emptyset),(\emptyset,\emptyset,1,\emptyset),(\emptyset,\emptyset,\emptyset,1),(1,\emptyset,1,\emptyset),(\emptyset,1,\emptyset,1)$

Let $$\mathcal{A}_{n,4}=\{S_1,S_2,S_3,S_4\subseteq[n]\;|\; S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq 3 \mbox{ and } S_1\cap S_4=\emptyset\},$$ and assume that $A_{n-1,4}=7^{n-1}$. Let $(S_1,\ldots,S_4)\in \mathcal{A}_{n,4}$. Then deleting $n$ from each $S_i$ gives an element of $\mathcal{A}_{n-1,4}$. Conversely, from a fixed $(S_1,\ldots,S_4)\in \mathcal{A}_{n-1,4}$ we can form an element of $A_{n,4}$ by inserting $n$ into the $S_i$'s. We can:

1. Insert zero $n$'s in one way.
2. Insert one $n$ in $4$ ways.
3. Insert two $n$'s in $2$ ways.
4. Insert three or four $n$'s in $0$ ways.

So for each $(S_1,\ldots,S_4)\in\mathcal{A}_{n-1,4}$ we can form $7$ elements of $\mathcal{A}_{n,4}$, and each element of $\mathcal{A}_{n,4}$ arises exactly once with this construction. Thus $A_{n,4}=7A_{n-1,4}=7(7^{n-1})=7^n$.

Answer 2

Let $B_k$ be the number of subsets of $\mathbb{Z}_n$ that have no consecutive numbers. As Casteels noted, $A_{n,k}={B_k}^{n}$.

To form a recursion in $k$, I look at subsets of $\{1,\ldots, k\}$, that lack consecutive numbers, and worry about the neighbours $1$ and $k$ later.

• Let $C_k$ be the number of these subsets that include both $1$ and $k$.
• Let $D_k$ be the number of these subsets that include $1$ but not $k$.
• Let $E_k$ be the number of these subsets that include $k$ but not $1$.
• Let $F_k$ be the number of these subsets that include neither $1$ nor $k$.

Then we can't have both $1$ and $k$, so $B_k=D_k+E_k+F_k$.

The following recursions happen because we can't have both $k$ and $k+1$: $$\begin{align}C_{k+1}&=&D_k\\ D_{k+1}&=&C_k+D_k&=&D_{k-1}+D_k\\ E_{k+1}&=&F_k\\ F_{k+1}&=&E_k+F_k&=&F_{k-1}+F_k \end{align}$$ So they are all Fibonacci-type numbers. $B_{k+1}=B_k+B_{k-1}$. ($B_1=2$ might be a special case.) Other than that, I think they will be 'Lucas numbers'. That is, 3,4,7,11,18,29,...

Answer 3

Here's another combinatorially based approach for $A_{n,r}$, which also leads to the Lucas numbers and the related Fibonacci numbers. We claim the following:

For $n\geq 1,r\geq 1$ let $A_{n,r}$ denote the cardinality of the set \begin{align*} \mathcal{A}_{n,r}=\{S_1,S_2,\dots, S_r\subseteq[n]\;|\; S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq r-1 \mbox{ and } S_1\cap S_r=\emptyset\} \end{align*} then the following is valid

\begin{align*} A_{n,r} = \begin{cases} 2^n&r=1,n\geq1\\ &\tag{1}\\ L_{r}^n&r\geq2,n\geq 1\\ \end{cases} \end{align*} with \begin{align*} L_{r}=\left(\frac{1+\sqrt{5}}{2}\right)^{r}+\left(\frac{1-\sqrt{5}}{2}\right)^{r}\quad\quad r\geq 0\tag{2} \end{align*} the $r$-th Lucas number.

We will proof the statement in three steps.

First step: Reformulate the problem and split it into simpler pieces

We interpret the subsets $S_1,\ldots,S_r\subseteq[n]$ as $r$ different urns and the set $[n]=\{1,\ldots,n\}$ as a source where we can pick out $n$ different balls numbered with $1$ to $n$ multiple times if necessary and place it in the urns. Respecting that different urns may contain balls with the same number, but a ball with a specific number can be in an urn at most once.

We also observe that the intersection conditions of the sets $S_j, 1\leq j\leq r$ can be considered for each number $1$ to $n$ from $[n]$ separately. We conclude:

If we denote with $B_r$ the number of all valid configurations of the representative $1$ then \begin{align*} A_{n,r}=B_r^n\quad r\geq 1, n\geq 1 \end{align*}

Since a representative $1$ provides the same information as balls without numbers we consider unnumbered balls from now on.

Second step: Combinatorial argument for $B_r$

We now focus on $k\geq 0$ balls and count the number $b_{r,k}$ of possibilities to place them into $r$ urns, so that two consecutive urns $S_j, S_{j+1}$ with $1\leq j,j+1\leq r$ do not both contain balls just as $S_{r}$ and $S_1$. So, the number $B_r$ is the finite sum: $$B_r=\sum_{k \geq 0}b_{r,k}$$

First the special cases $k=0$ and $k=1$: There is $1$ possibility to place no balls on $r$ urns and $r$ possibilities, to place exactly one ball on $r$ urns. Therefore:

\begin{align*} b_{r,0}&=1\quad\quad r\geq 1\\ b_{r,1}&=r\quad\quad r\geq 1\\ \end{align*}

Now let's consider placing $k\geq 2$ balls into $r$ urns.

The number of possibilities to place $k\geq 2$ balls into $r$ urns, so that no two balls are placed in consecutive urns $S_j,S_{j+1}$ with $1\leq j,j+1\leq r$ is \begin{align*} \binom{r-(k-1)}{k}\tag{3} \end{align*} since, there are $\binom{r-(k-1)}{k}$ possibilities to choose $k$ urns out of $r-(k-1)$ where we can place our $k$ balls. We have also $k-1$ additional urns which will be now placed between each of two neighbouring balls. So, we guarantee that $k-1$ urns are left empty and no two consecutive urns are filled with balls.

But in (3) we also count the invalid configurations, which contain balls in both urns $S_1$ and $S_r$. Let's subtract them explicitely: Since two balls are placed in urns $S_1$ and $S_r$, we have $k-2$ balls left which can be placed in $r-(k+1)$ urns. So, we have to subtract from (3) \begin{align*} \binom{r-(k+1)}{k-2} \end{align*}

Therefore, the number of placing $k\geq 2$ balls in $r$ urns is

\begin{align*} b_{r,k}=\binom{r-(k-1)}{k}-\binom{r-(k+1)}{k-2}\quad\quad r\geq 0, k\geq 2 \end{align*}

Now we sum over all $k\geq 0$ to get the number $B_r$:

\begin{align*} B_r&=b_{r,0}+b_{r,1}+\sum_{k\geq 2}b_{r,k}&r\geq 1\\ &=1+r+\sum_{k\geq 2}\left(\binom{r-(k-1)}{k}-\binom{r-(k+1)}{k-2}\right)&\\ &=\sum_{k\geq 0}\left(\binom{r-(k-1)}{k}-\binom{r-(k+1)}{k-2}\right)\tag{4}& \end{align*}

Observe, that we follow the convention that binomial coefficients $\binom{n}{m}=0$, if $m>n$ or one of $n,m< 0$.

Third step: Closed formula for $B_r$ and Lucas numbers

Let's consider the first part $B_r^{(1)}$ of the sum of $B_r$ in expression (4):

\begin{align*} B_r^{(1)}=\sum_{k\geq 0}\binom{r-(k-1)}{k} \end{align*}

We calculate

\begin{align*} B_1^{(1)}&=\sum_{k\geq 0}\binom{1-(k-1)}{k}=\binom{2}{0}+\binom{1}{1}=2&\\ B_2^{(1)}&=\sum_{k\geq 0}\binom{2-(k-1)}{k}=\binom{3}{0}+\binom{2}{1}=3&\\ B_r^{(1)}&=\sum_{k\geq 0}\binom{r-(k-1)}{k}&\\ &=\sum_{k\geq 0}\binom{r-k}{k}+\sum_{k\geq 1}\binom{r-k}{k-1}&\\ &=\sum_{k\geq 0}\binom{r-k}{k}+\sum_{k\geq 0}\binom{r-k-1}{k}&\\ &=B_{r-1}^{(1)}+B_{r-2}^{(1)}\qquad\qquad r\geq 3&\tag{5} \end{align*}

Observe, the $B_r^{(1)}$ are the (shifted) Fibonacci Numbers $F_{r+2}$ for $r\geq 1$. Similarly we derive for the second part $B_r^{(2)}$ of the sum of $B_r$ in expression (4):

\begin{align*} B_1^{(2)}&=B_2^{(2)}=0\\ B_3^{(2)}&=1\\ B_4^{(2)}&=1\\ B_r^{(2)}&=\sum_{k\geq 0}\binom{r-(k-1)}{k-2}\\ &=B_{r-1}^{(2)}+B_{r-2}^{(2)}=F_{r-2}\quad\quad r\geq 3\tag{6} \end{align*}

Let's combine the results from above.

According to $(5)$ and $(6)$ we get: \begin{align*} B_1&=2\\ B_2&=3\\ B_r&=F_{r+2}-F_{r-2}\quad\quad r\geq 3 \end{align*}

Finally, applying the recursion formula for the Fibonacci numbers, we can rewrite the $B_r$ with $r \geq 3$ as \begin{align*} B_r&=F_{r+2}-F_{r-2}\\ &=F_{r+1}+F_{r}-F_{r-2}\\ &=F_{r}+2F_{r-1}\tag{7}\\ &=L_{r}\quad\quad r\geq 3\\ \end{align*}

Observe from (7) $$L_r=F_{r}+2F_{r-1}\quad\quad r\geq 1$$ which is often mentioned as recursion formula for the $r$-th Lucas numbers with the related Fibonacci numbers. The Lucas number follow the same recursion formula as the Fibonacci Numbers but start with different initial values $L_0=2, L_1=1$.

Now, since the closed formula $L_{r}=\left(\frac{1+\sqrt{5}}{2}\right)^{r}+\left(\frac{1-\sqrt{5}}{2}\right)^{r}$ for the Lucas numbers is well known and $L_3=B_3=3$, we see that the claimed statement (2) is valid.

---

Note: When going through the proof we see that the $B_r^{(1)}=F_{r+2}$ solve the problem without respecting the boundary condition $S_1\cap S_r=\emptyset$. So we also have the solution for the related problem:

For $n\geq 1,r\geq 1$ let $T_{n,r}$ denote the cardinality of the set \begin{align*} \mathcal{T}_{n,r}=\{S_1,S_2,\dots, S_r\subseteq[n]\;|\; S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq r-1\} \end{align*} then the following is valid.

\begin{align*} T_{n,r} = F_{r+2}^n\quad\quad r\geq1,n\geq 1\\ \end{align*} with \begin{align*} F_{r}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{r}-\left(\frac{1-\sqrt{5}}{2}\right)^{r}\right)\quad\quad r\geq 0 \end{align*} the $r$-th Fibonacci number.