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
$$