Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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