Use generating functions to determine how many four-element subsets of $S = \{1,2,3,4,\dots,15\}$ contain no consecutive integers?

Question

Use generating functions to determine how many four-element subsets of $$S = \{1,2,3,4,\dots,15\}$$ contain no consecutive integers?

How do you approach this problem?

Answer 1

Solution I. Introduce the sequences $a_{n,k}$ and $b_{n,k}$ that count the number of $k$ element-subsets of $n$ that contain no consecutive integers where the $a_{n,k}$ count such sequences that do not use $n$ and the $b_{n,k}$ the ones that do use $n.$

Then we clearly have $$a_{n,1} = n-1 \quad\text{and}\quad b_{n,1} = 1.$$

Furthermore we have the recurrence $$a_{n,k} = a_{n-1,k} + b_{n-1,k}$$ and $$b_{n,k} = a_{n-1,k-1}.$$

Introduce the bivariate generating functions $$ A(z, u) = \sum_{n\ge 1} \sum_{k\ge 1} a_{n, k} u^k z^n \quad\text{and}\quad B(z, u) = \sum_{n\ge 1} \sum_{k\ge 1} b_{n, k} u^k z^n.$$ Multiply the first recurrence by $u^k z^{n-1}$ and sum to get $$\sum_{n\ge 2}\sum_{k\ge 1} a_{n,k} u^k z^{n-1} = \sum_{n\ge 2}\sum_{k\ge 1} a_{n-1,k} u^k z^{n-1} + \sum_{n\ge 2}\sum_{k\ge 1} b_{n-1,k} u^k z^{n-1}.$$ This gives $$1/z \left( A(z,u) - \sum_{k\ge 1} a_{1,k} u^k z \right) = A(z, u) + B(z, u)$$ so that $$ 1/z A(z, u) = A(z, u) + B(z, u).$$ Next multiply the second recurrence by $u^{k-1} z^{n-1}$ and sum to obtain $$\sum_{n\ge 2}\sum_{k\ge 2} b_{n,k} u^{k-1} z^{n-1} = \sum_{n\ge 2}\sum_{k\ge 2} a_{n-1,k-1} u^{k-1} z^{n-1}.$$ This gives $$1/u/z \sum_{n\ge 2}\sum_{k\ge 2} b_{n,k} u^k z^n = A(z,u)$$ which is $$1/u/z \left(\sum_{n\ge 1}\sum_{k\ge 2} b_{n,k} u^k z^n - \sum_{k\ge 2} b_{1,k} u^k z\right) = A(z, u)$$ which is in turn $$1/u/z \left(\sum_{n\ge 1}\sum_{k\ge 1} b_{n,k} u^k z^n - \sum_{n\ge 1} b_{n, 1} u z^n \right) = A(z, u)$$ which finally yields $$1/u/z \left( B(z, u) - \frac{uz}{1-z} \right) = A(z, u).$$ We have a system of two equations for the two unknowns $A(z,u)$ and $B(z,u)$ whose solution is $$A(z, u) = {\frac {u{z}^{2}}{u{z}^{3}-u{z}^{2}+{z}^{2}-2\,z+1}} \quad\text{and}\quad B(z, u) = -{\frac {uz}{u{z}^{2}+z-1}}.$$ The quantity that we are interested in computing is $$a_{n,k} + b_{n,k} = [z^n] [u^k] (A(z,u)+B(z,u)) = [z^n] [u^k] {\frac {uz}{ \left( u{z}^{2}+z-1 \right) \left( -1+z \right) }}.$$ This is $$[z^n] [u^k] \frac{uz}{(1-z-uz^2)(1-z)} = [z^n] \frac{z}{(1-z)^2} [u^k] \frac{u}{1-uz^2/(1-z)}$$ which is $$[z^n] \frac{z}{(1-z)^2} [u^{k-1}] \frac{1}{1-uz^2/(1-z)} = [z^n] \frac{z}{(1-z)^2} \frac{z^{2k-2}}{(1-z)^{k-1}} = [z^n] \frac{z^{2k-1}}{(1-z)^{k+1}}$$ which yields the answer $$[z^{n-(2k-1)}] \frac{1}{(1-z)^{k+1}} = {n-(2k-1)+k\choose k} = {n+1-k\choose k}.$$

Solution II. This method also uses generating functions but in a much simpler way. The result is the same (as it ought to be). Pick your first value $v$ and represent it by $z^v$ in the generating function $$\frac{z}{1-z}.$$ Now pick the difference between the first and the second value, which difference is at least two, and add it to the value you already have, giving $$\frac{z}{1-z} \times \frac{z^2}{1-z}.$$ Next pick the difference between the second and the third value, which difference is at least two, and add it in like before, giving $$\frac{z}{1-z} \times \frac{z^2}{1-z} \times \frac{z^2}{1-z}.$$ There are a total of $k-1$ differences to choose, which finally produces $$\frac{z}{1-z} \times \left(\frac{z^2}{1-z}\right)^{k-1}.$$ The maximum value $q$ contained in the $k$-tuple that we have selected is represented in the above term by $z^q,$ or rather, that is how a $k$-tuple with largest value $q$ is represented. Now we need to sum all the possibilities with the maximum value being at most $n,$ for an answer of $$\frac{1}{1-z} \times \frac{z}{1-z} \times \left(\frac{z^2}{1-z}\right)^{k-1} = \frac{z^{2k-1}}{(1-z)^{k+1}}.$$ Extracting coefficients with the Newton binomial we get as before $$[z^n] \frac{z^{2k-1}}{(1-z)^{k+1}} = [z^{n-(2k-1)}] \frac{1}{(1-z)^{k+1}} = {n-(2k-1)+k\choose k} = {n+1-k\choose k},$$ the same as in the first solution. QED.

Answer 2

so I was searching for this question and came up on an answer which is pretty neat and I found it to be a lot easier for me to understand.

Basically, you take any any 4 numbers within 1 and 15. and consider the differences between the numbers.

eg: say you took the set{2,4,6,11}

See that: 1 <= 2 < 4 < 6 < 11 < 15.

Now take the difference among the element to the previous one

like: 1(2-1),2(4-2),2(6-4),5(11-5),4(15-11)

Notice that their sums add up to 14(1 + 2 + 2 + 5 + 5). This condition is valid for all sets of numbers possible.

So now we can convert the question to a counting problem of the no. ways in which the 5 differences add up to 14:

i.e the solution for: $$ c1 + c2 + c3 + c4 + c5 = 14 $$

We get the conditions that c1 and c5 >= 0 since the first and 4th element could be 1 and 15 as well.

In order to ensure that consecutive numbers are not taken we can give the condition as c2,c3,c4 != 1 Also, c2,c3,c4 cannot be 0 as well since that would mean taking the same element twice. So c2,c3,c4 >= 2

so we can form our generating function as: $$ g(x) = (1 + x + x^2 +...)^2 (x^2 + x^3 + x^4 +...)^3$$ Now you can find the coefficient for $x^{14}$ from this generating function and you'll get the final answer as 495.

Check this image as well