Use generating functions to determine how many four-element subsets of $S = \{1,2,3,4,\dots,15\}$ contain no consecutive integers? 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?
 A: 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.
A: 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
