# How to answer the following combinatorial question?

Consider the set $S = \{ 1,2, \cdots , 15 \}$. The general question is: how many subsets of $S$ exist such that the subsets contain 4 different elements without any consecutive numbers? As a sub-question, I have to show that this problem is equivalent with finding the number of solutions $$(*) \qquad a_1 + a_2 + a_3 + a_4 + a_5 = 14 ; \qquad a_1,a_5 \geq 0 ; a_2, a_3, a_4 \geq 2$$ To prove this, I tried the following. Consider the numbers 1 through 15 laid out next to each other in a row, starting with the number 1 and ending with 15. To find the subsets that obbey the given restrictions, we start of by picking some number $a_1 \geq 1$. Then, $a_2$ cannot be a consecutive number, so the distance to $a_1$ should be larger than or equal to two. Similar for $a_3$ and $a_4$. Then I don't know about $a_{5}$.

However: one is asked to prove the original problem is equivalent to proving that $a_1 \geq 0$, not $a_1 \geq 1$. Furthermore, I don't understand why $a_{5}$ enters the scene here: we should find subsets containing $4$ elements, right? Could you please explain this? Furthermore, I don't understand why the $(*)$-marked sum should be equal to 14. Could you please this explain this as well, or give me a hint?

Furthermore, I am asked to show that this number of subsets is equal to the coefficient of $x^{14}$ of the generating function $$f(x) = \frac{x^6}{(1-x)^5} .$$ How does one show that? Or could you please give a hint?

-

Imagine we have picked $4$ numbers, no two consecutive. List them in order, as $p,q,r,s$.

Let $a_1$ be the number of integers in the interval $[1,15]$ that are less than $p$, and let $a_5$ be the number of integers in the interval that are greater than $s$. Let $a_2$ be the number of integers in the interval $(p,q]$. (So we do not count $p$, but we do count $q$.) Let $a_3$ be the number of integers in the interval $(q,r]$, and $a_4$ the number of integers in the interval $(r,s]$.

Note that $a_1\ge 0$, $a_5\ge 0$, and each of $a_2,a_3,a_4$ is $\ge 2$. Note also that $a_1+a_2+a_3+a_4+a_5=14$. For let $g_1$ be the "gap" up to the first of our chosen integers, $g_2$ the gap between the first two chosen integers, $g_3$ the gap between the next two, $g_4$ the gap between the next two, and $g_5$ the final gap. Then $g_1+g_2+g_3+g_4+g_5 +4=15$. We have $g_1=a_1$, $g_5=a_5$, and for the remaining three $i$ we have $g_i=a_i-1$.

Thus $a_1+(a_2-1)+(a_3-1)+(a_4-1)+a_5+4=15$, giving $a_1+a_2+a_3+a_4+a_5=14$. It is the fact that between our four numbers there are three gaps that accounts for the $14$.

We have shown that for every choice of numbers $p,q,r,s$, there are numbers $a_1,\dots,a_5$ satisfying the given inequalities, and with sum $14$.

It is not hard to reverse the argument, and show that any sequence $a_1,\dots,a_5$ that satisfies the given inequalities and with sum $14$ determines a choice of $p\lt q\lt r\lt s$ with no two consecutives.

-

Let $1\leq x<y<z<u\leq15$ such that $y\ne x+1$, $z\ne y+1$ and $u\ne z+1$. Then $\{x,y,z,u\}$ is a subset of $S$ that contains exactly $4$ non-consecutive elements. Taking $a_{1}=x-1$, $a_{2}=y-x$, $a_{3}=z-y$, $a_{4}=u-z$ and $a_{5}=15-u$, the conditions can be rewritten as $a_{1}\ge0$, $a_{i}\geq2$ for $i=2,3,4$, $a_{5}\geq0$ and $a_{1}+\cdots+a_{5}=14$.

Let $a_{1}=b_{1}$, $a_{5}=b_{5}$ and $a_{i}=b_{i}+2$ for $i=2,3,4$. Under condition $b_{i}\geq0$ the number of solutions of $b_{1}+b_{2}+b_{3}+b_{4}+b_{5}=8$ equals $\binom{12}{4}$.

-

Use 'Stars and Bars' to count.

We can represent the four numbers as a string of 4 'bars' and 11 'stars', where the position of each the bar counts off a number.

So the string: "$**|*|***|**|***$" represents: $\{3, 5, 9, 12\}$.

Since we need at least one 'star' between each pair of 'bars', this is equivalent to finding the permutations of 4 bars and 8 remaining stars.

So there are $\dbinom{12}{4} = \dfrac{12!}{4!\;8!} = 495$ ways to do this.

Your next step is to show that the problem of five variables can also be represented by the same string.

-