The number of ways of choosing $3$ distinct numbers from first $15$ natural numbers such that no two are consecutive

Question

The number of ways of choosing $3$ distinct numbers from first $15$ natural numbers such that no two are consecutive is $143\cdot k$ then what is $k$ equal to?

---

My attempt:

$$\text{Total ways of selecting non consecutive no's} = \text{Total ways of selecting} - \text{Total ways of selecting consecutive no's}$$

$$= ^{15}C_{3} - (15-3+1)$$

$$= ^{15}C_{3} - (13)$$

which is wrong when inspected.

Please help me out.

Answer 1

Each admissible selection can be encoded as a binary word $w$ of length $15$ having three ones, no two of them consecutive. Given such a $w$ there are a zero immediately after the first and the second ones. Suppress these two zeros, and obtain a binary word $w'$ of length $13$ having three ones and no other specialities. There are ${13\choose3}=286$ such words $w'$. Conversely: Given such a $w'$ you obtain an admissible $w$ of length $15$ by inserting a zero after the first and after the second one.

Answer 2

Elaborating on / transferring my comment, let $x_1$ be the number of numbers skipped before the first number in your subset. Let $x_2$ be the number of numbers skipped between the first and second number in your subset, $x_3$ the number of numbers skipped between the second and third, and finally $x_4$ the number of numbers skipped larger than the third number.

Note that as $x_1$ is the number of numbers skipped between the first and second and we wanted our first and second to not be adjacent, that there is at least one skipped number so we have $x_1\geq 1$. Similarly for $x_2$. Otherwise $x_1$ and $x_4$ may be any non-negative integer.

Further notice that $x_1+x_2+x_3+x_4$ is effectively counting the number of unused numbers in $\{1,2,3,\dots,15\}$ just having organized the count in a particular way. The count will always be just $15-3=12$.

We are now to the question of counting the number of non-negative integral solutions to $\begin{cases}x_1+x_2+x_3+x_4=12\\x_1\geq 0\\x_2\geq 1\\x_3\geq 1\\x_4\geq 0\end{cases}$

You can proceed counting with stars-and-bars after making a slight change of variable to put it into a form you are more familiar with.

Change to $y_1=x_1,~ y_2=x_2-1,~ y_3=x_3-1,~ y_4=x_4$ to put it in the form where all are just non-negative and $y_1+y_2+y_3+y_4=10$. The total is then $\binom{10+4-1}{4-1}=\binom{13}{3}=286$