1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – lulu
    Commented Sep 2, 2023 at 22:02

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Sorry I noticed that there was a typo in my question, now my result is the same as yours. Is my reasoning correct? $\endgroup$
    – Kandinskij
    Commented Sep 3, 2023 at 5:59
  • $\begingroup$ 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. $\endgroup$ Commented Sep 3, 2023 at 8:58
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .