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
Best Answer
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.