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

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

• Not following your computation. Recursively, note that either the first element is chosen or it isn't. If it is, then you are down to choosing $t-1$ good pairs out of $n-2$. If it isn't, then you are choosing $t$ out of $n-1$.
– lulu
Commented Sep 2, 2023 at 22:02

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\}$$.

• Sorry I noticed that there was a typo in my question, now my result is the same as yours. Is my reasoning correct? Commented Sep 3, 2023 at 5:59
• While you did not explicitly say so, it looks like you are counting the number of arrangements of the remaining $n - t$ numbers that are not the first numbers in a pair of consecutive numbers. If my understanding is correct, then your solution is correct. Commented Sep 3, 2023 at 8:58

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

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