Number of ways to select $t$ non adjacent couples of consecutive numbers.

Question

A good couple of the set $\{1,...,n\}$ is a couple of the type $(k,k+1)$ where $k,k+1\in \{1,...,n\}$. Two good couples $(k,k+1)$ and $(j,j+1)$ are disjoint iff they don't have any element in common.

In how many ways can I select $t$ disjoint good couples of $\{1,...,n\}$?

My attempt

Let's suppose we have $n$ balls $$\bullet \bullet \cdots \bullet \bullet$$ representing the numbers $\{1,...,n\}$. I just have to select the first element of each couple, so I have just to select $t$ elements properly. When I select the $i$-th ball I substitute it with a bar $|$. The rules are that there cannot be adjacent bars and the last ball cannot be selected. To create symmetry I can add an auxiliary ball at the start so that it can't be selected just like the last one $$\star \bullet \bullet \cdots \bullet \bullet $$ Basically this should create a bijection (through stars and bars) between the number of ways to select disjoint good couples and the number of compositions of $(n+1-t)$ in $(t+1)$ positive numbers. So according to this method the answer should be

$$\binom{n-t}{t}$$

Answer 1

Suppose we have $n$ identical balls and $t$ boxes, each of which can hold two balls placed side by side. Place $2$ balls in each of the $t$ boxes. That leaves $n - 2t$ balls. We have $n - t$ objects to arrange, $t$ boxes each containing two balls and $n - 2t$ other balls. Choose $t$ of the $n - t$ positions for the boxes. Now number the balls from left to right. The numbers on the balls in the $t$ boxes are the desired set of $t$ disjoint pairs of consecutive numbers. Hence, there are $$\binom{n - t}{t}$$ ways to select $t$ disjoint pairs of consecutive numbers from the set $[n] = \{1, 2, \ldots, n\}$.

Answer 2

Alternative approach.

Lay the balls in a row, and let $~(k-1) = n-2t.~$

Remove the $~(k-1)~$ balls that will not be selected.

Note that the specific $~(k-1)~$ un-selected balls completely determine the (satisfying) pairings.

Further, the removal of the $~(k-1)~$ un-selected balls create $~k~$ islands of selected balls, and you can assign the variables $~x_1, \cdots, x_k~$ to the size of the respective islands. Note that from the constraints of the problem, $~x_1, \cdots, x_k~$ must each be an even non-negative integer. Note also that the specific values assigned to $~x_1, x_2, \cdots, x_k~$ completely determine which $~(k-1)~$ balls will not be selected.

Then, you want the number of even non-negative integer solutions to

$$x_1 + x_2 + \cdots + x_k = n - (k-1) = 2t.$$

For $~i \in \{1,2,\cdots,k\},~$ let $~y_i = \dfrac{x_i}{2}.~$

Then, the problem has been reduced to computing the number of non-negative integer solutions to

$$y_1 + y_2 + \cdots + y_k = t. \tag1 $$

For Stars and Bars theory, see this article and this article.

By Stars and Bars theory, the number of non-negative integer solutions to (1) above is

$$\binom{t + [k-1]}{k-1} = \binom{t + [n-2t]}{n - 2t} = \binom{n-t}{n-2t} = \binom{n-t}{t}.$$