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.

How many 4-element subsets of the set S = {1,2,3...,10} contain no consecutive integers?

We went over a problem like this is class. The lecturer said the answer is the number of integer solutions to

$b_0 + b_1 + b_2 + b_3 + b_4 = 9$

Where for the choice $a_1, a_2, a_3, a_4$ $b_0 = a_1 - 1, b_{4} = 10 - a_4, b_i = a_{i+1}-a_i, 1 \le i \le 3$

The condition is then imposed that $b_0 \ge 0, b_4 \ge 0, b_1 \ge 2, b_2 \ge 2, b_3 \ge 2$

I understand that $b_1 \ge 2$ etc conditions are used to specify the next choice can't directly follow it, but I don't understand what $b_0$ is used for or even how the first equation was even found. The lecturer used a generating function produced from the above information to solve the problem. Could someone help clarify a few things, by explaining how the above equations are found and how they can be used in a generating function?

Thanks

share|improve this question
    
Is easier computing all 4-element subsets and then removing the ones that has all consecutive elements. –  Gastón Burrull Jun 4 '12 at 7:53

2 Answers 2

up vote 2 down vote accepted

Suppose that you’ve picked a legitimate set $A=\{a_1,a_2,a_3,a_4\}$, where $a_1<a_2<a_3<a_4$. Let $b_1=a_2-a_1$, the size of the gap between $a_1$ and $a_2$. Similarly, let $b_2=a_3-a_2$ and $b_3=a_4-a_3$. If you know the numbers $b_1,b_2$, and $b_3$, you almost know $A$. You would know $A$ if you also had $a_1$; then you could recover the whole lot:

$$\begin{align*} a_1&=a_1\\ a_2&=a_1+b_1\\ a_3&=a_1+b_1+b_2\\ a_4&=a_1+b_1+b_2+b_3 \end{align*}$$

Now we know how to count the integer solutions to equations of the form $x_1+\ldots+x_m=n$, even subject to various conditions on the $x_k$, so it would be nice to be able to recast this problem in such terms. We’re not there yet, because $a_1+b_1+b_2+b_3$ doesn’t have to be a particular number. However, we could use another number, $b_4$, to measure the size of the gap from $a_4$ to $10$, the maximum possible value, by setting $b_4=10-a_4$. Now we know that $a_1+b_1+b_2+b_3+b_4=10$, and all four members of $A$ are recoverable from these five numbers.

Your instructor made one further small modification: instead of using $a_1$ directly, he used $a_1-1$, calling it $b_0$. You can think of $b_0$ as the gap between $1$, the lowest possible value, and the actual value of $a_1$. Notice that $b_0+b_1+b_2+b_3+b_4=(a_1-1)+b_1+b_2+b_3+b_4=10-1=9$, and that we can recover $A$ just as well from $b_0,b_1,b_2,b_3,b_4$ as from $a_1,b_1,b_2,b_3,b_4$:

$$\begin{align*} a_1&=1+b_0\\ a_2&=1+b_0+b_1\\ a_3&=1+b_0+b_1+b_2\\ a_4&=1+b_0+b_1+b_2+b_3 \end{align*}$$

(We don’t need $b_4$ to reconstruct $A$; it’s there to make the sum a known constant.)

Thus, there is a bijection between $4$-element subsets $A$ of $\{1,\dots,10\}$ satisfying the condition that no two members are consecutive, and ordered $5$-tuples $\langle b_0,b_1,b_2,b_3,b_4\rangle$ of integers satisfying the equation $$b_0+b_1+b_2+b_3+b_4=9\tag{1}$$ together with the conditions $b_1,b_2,b_3\ge 2$ (to ensure that no two members of $A$ are consecutive), $b_0\ge 0$ (to ensure that $1$ is the smallest possible value of $a_1$), and $b_4\ge 0$ (to ensure that $10$ is the largest possible value of $a_4$.

Now the fact is that I wouldn’t use generating functions to count the number of solutions to $(1)$ subject to the given constraints. This is a bog-standard stars-and-bars problem that can be solved immediately by the technique explained in the article to which I linked. Because I think that the idea is a useful one to understand, I’ll give my own explanation here. Imagine that I have $9$ indistinguishable marbles and five boxes, labelled $B_0$ through $B_4$, and I want to count the number of distinguishable ways to put the $9$ marbles into the $5$ boxes. If you think of $b_k$ as representing the number of marbles in box $B_k$, you can see that the answer is the same as the number of solutions of $(1)$ in non-negative integers. Ah, but I’m required to have at least $2$ marbles in each of boxes $B_1,B_2$, and $B_3$. No problem: I just put $2$ marbles into each of those boxes right away, leaving myself with just $9-6=3$ marbles to distribute as I please amongst the $5$ boxes. (By the way, this shows that the number of solutions of $(1)$ that meet the stated conditions is the same as the number of solutions of $$b_0+b_1+b_2+b_3+b_4=3\tag{2}$$ in non-negative integers.) From here on I’ll simply ignore the $6$ required marbles and look at the number of ways of distributing the other three.

Draw a schematic of the boxes: instead of drawing the boxes themselves, draw the boundaries between them, representing them by vertical bars, $|$: $$|\;|\;|\;|\;.$$ The spaces between the bars, before the first bar, and after the last bar represent the five boxes. If I represent the marbles by $o$’s, I can symbolize the arrangement with two marbles in the first box and one in the third by $$oo||o||\;.$$ Each possible distribution of the three marbles corresponds to a unique string of three $o$’s and four $|$’s, and each string of three $o$’s and four $|$’s corresponds to a unique distribution of the three marbles. Thus, the number of solutions to $(2)$ in non-negative integers, and hence the number of solutions to $(1)$ that meet the extra conditions, is simply the number of strings of four $|$’s and three $o$’s. This is just the number of ways of choosing which $3$ of the $7$ positions in the string are to be $o$’s, so it’s $\binom73$. (Or, if you prefer, it’s the number of ways of choosing which $4$ of the $7$ position in the string are to be $|$’s, which is $\binom74$; of course these are the same.)

If you use generating functions directly on $(1)$, it works like this. The possible values for $b_0$ and $b_4$ are $0,1,\dots$, while those for $b_1,b_2$, and $b_3$ are $2,3,\dots$. These are the exponents on the terms of $\sum\limits_{n\ge 0}x^n$ and $\sum\limits_{n\ge 2}x^n$, respectively. We know that formally $$\sum_{n\ge 0}x^n=\frac1{1-x}\;,$$ so $$\sum_{n\ge 2}x^n=x^2\sum_{n\ge 0}x^n=\frac{x^2}{1-x}\;.$$ Let $$g(x)=\left(\sum_{n\ge 0}x^n\right)^2\left(\sum_{n\ge 2}x^n\right)^3=\frac{x^6}{(1-x)^5}\;;$$ this is the desired generating function.

To see what this means, imagine multiplying out the summations:

$$(1+x+x^2+x^3+\ldots)^2(x^2+x^3+x^4+\ldots)^3=x^6(1+x+x^2+x^3+\ldots)^5\;.$$

When you’ve collected terms, the coefficient of $x^9$ will be the number of products that produced $x^9$: $x^6\cdot x^0\cdot x^0\cdot x^0\cdot x^0\cdot x^3$, $x^6\cdot x\cdot x^0\cdot x^0\cdot x^2\cdot x^0$, etc. Each of these corresponds to one solution of $(1)$. For instance, the two that I just listed correspond to $$0+2+2+2+3=9$$ and $$1+2+2+4+0=9\;,$$ respectively. Thus, the answer to the question is simply the coefficient of $x^9$ in $$g(x)=\frac{x^6}{(1-x)^5}\;.$$ This is the coefficient of $x^3$ in $$\frac1{(1-x)^5}=(1+x+x^2+x^3+\ldots)^5\;,$$ which is the same as the coefficient of $x^3$ in $$(1+x+x^2+x^3)^5\;,$$ since the higher powers of $x$ can’t contribute to an $x^3$ term. You can go ahead and work out this coefficient by direct calculation, though it’s a bit tedious.

share|improve this answer
    
Thanks for the great reply, it cleared everything up! –  urbanyoung Jun 4 '12 at 21:58

The idea is that you first choose $a_1$ and then $a_2-a_1$ which determines $a_2$ and then $a_3-a_2$ which determines $a_3$ and so on, and finally the difference to 10 to make sure that you stayed below 10.

Summing over the given definitions of your $b_i$, the equation is obviously true and also the inequalities are easily checked.

There are two issues with going to a generating function:


1) It is easier to solve the problem directly without generating functions or $b_i$.

You have 10 items and want to choose 4 which are non-consecutive. Add an 11th one at the end. Now, the task is the choice of four pairs of two consecutive items without overlap (because you take away the "forbidden" one after your choice as well). But this is the same thing as choosing four items freely from 7 objects because you can just add four additional objects after your four chosen ones.

So, you have $\displaystyle \binom 7 4$ choices.


2) For the generating function approach, it is not good that the $b$s have different lower bound, so it is a good idea to set $c_0=b_0$, $c_1=b_1-2$, $c_2=b_2-2$, $c_3=b_3-2$, $c_4=b_4$ before starting any calculation because this gives $c_0+c_1+c_2+c_3+c_4=3$ and $c_i \ge 0$.

But this is means that you just have to pick the coefficient of $x^3$ in the sum

$$\sum_{c_0\ge 0} \sum_{c1\ge 0}\sum_{c_2\ge 0}\sum_{c_3\ge 0}\sum_{c_4\ge 0} x^{c_0+c_1+c_2+c_3+c_4}= \left(\sum_{n\ge 0} x^n\right)^5 = (1-x)^{-5}.$$

This coefficent is $(-1)^3\binom{-5}{3}= \binom{7}{3}$.

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.