I've done this problem in this way. We can think this as follows.

There are $n$ identical boxes and $r$ identical objects have been placed in $r$ fixed boxes. We will find the number of arrangements such that any box which has an object has an empty box on its right.

Or better we can see this as the number of ways of arranging $r$ 1's and $n-r$ 0's such that each 1 has at least one 0 to its right. We first place $r$ 1's and then place $r$ 0's beside each of them. Remaining 0's are $n-2r$ in number. We now consider each '10' pair as a separate object. Now, the problem becomes how we arrange $r$ '10' groups and $n-2r$ 0's, which is equal to the number of permutations of $n-r$ objects such that $n-r$ are alike one type and $r$ are alike another type. Thus, it is $\frac{(n-r)!}{r!(n-2r)!}$ or ${n-r \choose r}$.

Now, my solution book has a different approach. It is this:

If $T=\{(a_1, a_1 + 1), (a_2, a_2 + 1), ..., (a_r, a_r + 1)\}$ is a set of $r$ non-overlapping consecutive pais in increasing order chosen from $S$, let $T$ correspond to $T'$ where $T' = \{b_1, b_2, ..., b_r\}$ with $b_1 = a_1$ and $b_i = a_i - (i-1)$ for $i=2,...,r$. Verify that $T\rightarrow T'$ is a bijection.

I cannot understand what it means.

  • $\begingroup$ Did it actually say "$T\to T'$ is a bijection", or did it say "$T\mapsto T'$ is a bijection"? $\endgroup$ – Lord Shark the Unknown Dec 31 '17 at 14:14
  • $\begingroup$ @LordSharktheUnknown What is the difference? $\endgroup$ – Shubhraneel Pal Dec 31 '17 at 14:17
  • 2
    $\begingroup$ @ShubhraneelPal $T \to T'$ refers to a bijection between the sets $T$ and $T'$ (i.e., mapping $(a_1,a_1+1)$ to $b_1$, etc.), while $T \mapsto T'$ refers to a bijection between the set of all possible $T$s and the set of all possible $T'$s. $\endgroup$ – Y. Forman Dec 31 '17 at 14:24

I think this is essentially the same as your solution. We want to re-conceptualize a pair of consecutive integers as a single object (as you did). The book solution conceptualizes a pair $(a_i, a_i +1)$ as as a single integer $b_i$ in the set $T'$, given by the formula $b_i = a_i - (i-1)$.

We must verify that this transformation is a bijection: that it never produces duplicate $b_i$s, and that its inverse never produces any overlapping pairs. Intuitively, this is because the $T \to T'$ transformation deletes each $a_i + 1$ from the list and shifts everything else lift, and the inverse transformation reinserts it. So $b_1$ can never be equal to $b_2$, etc., and conversely, if $b_1 \neq b_2$, the pairs $(a_1, a_1+1)$ and $(a_2, a_2+1)$ won't overlap. (This can be done more carefully.)

Once we know this, choosing the set $T$ of pairs is equivalent to choosing the set $T'$ of integers. A quick check shows that the minimum possible value for $b_1$ is $1$ (since that's the minimum value for $a_1$), and the maximum value for $b_r$ is $n-r$ (since the maximum for $a_r$ is $n-1$). Thus we have reduced the problem to choosing a set $T'$ of $r$ integers from among the set {$1, 2, \dots, n-r$}, which is doable $\binom{n-r}{r}$ ways.


Each admissible choice of $r$ pairs of consecutive numbers from $[n]$ can be encoded as a binary word of length $n-r$ containing exactly $r$ ones. There are ${n-r\choose r}$ such words $w$.

Given such a word $w$ the parsing is as follows: Count along $w$. For each ${\tt 0}$ in $w$ count $1$ ahead, and let the corresponding number single. For each ${\tt 1}$ in $w$ count $2$ ahead, and at the same time pair these two numbers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.