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?

  • $\begingroup$ It seems that you are supposing a condition $S_i \cap S_j=\emptyset$ while finding $A_{n,r}$. $\endgroup$ – The Great Seo Aug 7 '14 at 13:40
  • $\begingroup$ no, the condition is not Si∩Sj=∅ for any i and j, but for j=i+1 and so on. $\endgroup$ – Ginger Aug 7 '14 at 13:48
  • $\begingroup$ Oh, my mistake. When $n<4$, two are equivalent, and I take it wrong. $\endgroup$ – The Great Seo Aug 7 '14 at 13:58
  • $\begingroup$ For $r=1$ you are counting the number of subsets of $[n]$. For $r=2$ you are counting the number of ways you can distribute the elements of $[n]$ in three bins (the members of $S_1$, the members of set $S_2$, and the poor ignored leftovers. For $r=3$ you are placing the elements of $[n]$ in four bins. For $r=4$ this breaks down because an element can be a member of $S_1$ and $S_3$ or a member of $S_2$ and $S_4$. Perhaps you need more bins. $\endgroup$ – deinst Aug 7 '14 at 15:43

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$.

  • $\begingroup$ This begs the question: What is the sequence 2,3,4,7,...? I don't think it is in OEIS. $\endgroup$ – Empy2 Aug 8 '14 at 15:21
  • $\begingroup$ a nice view, thanks. $\endgroup$ – Ginger Aug 8 '14 at 15:45
  • $\begingroup$ And I know the next is 12, so the sequence is 2,3,4,7, 12,... $\endgroup$ – Ginger Aug 8 '14 at 15:46

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,...

  • $\begingroup$ Yes, that is right! 12 was a mistake. $\endgroup$ – Ginger Aug 8 '14 at 16:04

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.