1
$\begingroup$

I have m objects and insert n indistinguishable objects between them. For example, with m=4:
n=1: {0,x,1,2,3},{0,1,x,2,3},{0,1,2,x,3} (3 ways)
n=2:{0,x,x,1,2,3},{0,1,x,x,2,3},{0,1,2,x,x,3},{0,x,1,x,2,3},{0,x,1,2,x,3},{0,1,x,2,x,3} (6 ways)

By counting and guessing I got this formula:

$\frac{1}{(m-2)!}\prod _{i=1}^{m-2} (n+i)$

But I don't know how to derive it. Can somebody help me?

$\endgroup$
1
$\begingroup$

This can be represented exactly as a modified stars and bars problem, where the distinguished numbers play the role of bars and the indistinguishable objects the role of stars.

The only restriction is that we cannot have any "stars" on the left of the most-left bar and on the right of the most-right bar.


Let the numbers $0,1,2,3$ represent the $4$ bars and also, we have $2$ indistinguishable stars. The $4$ bars define $3$ distinct bins, in which we need to place the $2$ stars.

$$ | \quad bin1\quad | \quad bin2 \quad| \quad bin3 \quad | $$

According to the stars and bars formula we have that the number of ways to do so is: $$ \binom{n+k-1}{n} = \binom{n+k-1}{k-1},$$

where $k$ is the number of bins and $n$ is the number of stars.


In our case the $m$ distinct numbers define $m-1$ bars. Thus, the formula becomes: $$ \binom{n+m-2}{n} = \binom{n+m-2}{m-2} = \frac{(n+m-2)!}{(m-2)! \cdot n!}.$$ But $\frac{(n+m-2)!}{n!} = \prod\limits_{i = 1}^{m-2}(n+i).$

$\endgroup$
0
$\begingroup$

First pretend that the $n$ objects are distinct. You require that one of the $m$ be first and another be last, so there are $m(m-1)$ ways to select the first and last. There are $(n+m-2)!$ ways to arrange the rest in the middle, but when we say the $n$ are indistinguishable we have to divide by $n!$. This gives $m(m-1)\frac {(n+m-2)!}{n!}$ arrangements.

$\endgroup$
0
$\begingroup$

Multiplying out the product, we get:

$$\frac{(n+1)\dots(n+m-2)}{(m-2)!}$$

This equals:

$$\frac{(n+m-2)!}{n!(m-2)!}=\binom{n+m-2}{n}$$

which is the number of ways to arrange $n$ objects from $n+m-2$ objects.

$\endgroup$

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.