# Help me solve a combinatorial problem

Consider a ordered set consisting of $N$ integers. It is called beautiful if for every integer $x$ in the set, either $x-1$ or $x+1$ is present in the set.

How many beautiful sets can be created using the numbers $1$ to $M$ of size $K$ for some arbitrary $M$ and $K$?

The number of sets created using the numbers from $1$ to $6$ of size $4$ is 6. Ex: (1, 2, 3, 4), (2,3,4,5),(3,4,5,6),(1,2,4,5),(1,2,5,6) ,(2,3,5,6).

#### Solutions Collecting From Web of "Help me solve a combinatorial problem"

We want to count the number of strings of length $M+1$ consisting of $M-K+1$ atoms that look like
$$\underbrace{\ 0\ }_1,\underbrace{110}_{x^2},\underbrace{1110}_{x^3},\underbrace{11110}_{x^4},\dots$$
That is, there are $M-K+1$ zeros and $K$ ones. Since the atoms all end with a zero, we’ve added one to the number of zeros and one to the length the string.

As seen by the monomials under the atoms, we want to count the coefficient of $x^K$ in $\left(1+x^2+x^3+x^4+x^5+\dots\right)^{M-K+1}$. Since
\begin{align} 1+x^2+x^3+x^4+x^5+\dots &=\frac1{1-x}-x\\ &=\frac{1-x+x^2}{1-x}\\ &=\frac{1+x^3}{1-x^2} \end{align}
what we are looking for is
$$\bbox[5px,border:2px solid #C0A000]{\left[x^K\right]\left(\frac{1+x^3}{1-x^2}\right)^{M-K+1}}$$
To compute this coefficient, we use the Binomial Theorem
\begin{align} \left(\frac{1+x^3}{1-x^2}\right)^{M-K+1} &=\sum_{a=0}^{M-K+1}\binom{M{-}K{+}1}{a}x^{3a}\sum_{b=0}^\infty(-1)^b\binom{-M{+}K{-}1}{b}x^{2b}\\ &=\sum_{a=0}^{M-K+1}\binom{M-K+1}{a}x^{3a}\sum_{b=0}^\infty\binom{M{-}K{+}b}{b}x^{2b} \end{align}
Therefore,
\begin{align} \left[x^K\right]\left(\frac{1+x^3}{1-x^2}\right)^{M-K+1} &=\bbox[5px,border:2px solid #C0A000]{\sum_{3a+2b=K}\binom{M{-}K{+}1}{a}\binom{M{-}K{+}b}{b}}\\ &=\left\{\begin{array}{} \displaystyle\sum_{j=0}^{\lfloor K/6\rfloor}\binom{M{-}K{+}1}{2j}\binom{M{-}\frac K2{-}3j}{\frac K2-3j}&\text{if K is even}\\ \displaystyle\sum_{j=0}^{\lfloor(K-3)/6\rfloor}\binom{M{-}K{+}1}{2j+1}\binom{M{-}\frac{K+3}2{-}3j}{\frac{K-3}2-3j}&\text{if K is odd} \end{array}\right. \end{align}

To check this with the example given, $6-4+1=3$, so consider
$$\left(\frac{1+x^3}{1-x^2}\right)^3=1+3x^2+3x^3+6x^4+9x^5+\dots$$
Note that the coefficient of $x^4$ is $6$.

Also, since $K$ is even,
$$\binom{6-4+1}{0}\binom{6-2}{2}=6$$