Suppose that I have n apples and n oranges, I want to arrange the apples and oranges in a row such that no apples will be next to another apple and no oranges will be next to another orange.

Please check my solution

attempt 1:

suppose apples and oranges are interchangeable (no order)

then we have $(n)*(n)*(n-1)*(n-1)*(n-2)...*(n-n+1)*(n-n+1)$ ways

attempt 2:

suppose apples and oranges are not interchangeable (ordered)

then we have ${\binom{n}{1} * \binom{n}{1}* \binom{n}{2}* \binom{n}{2}*...* \binom{n}{n-1}*\binom{n}{n-1}}$ ways, and this is equal to $\sum_{i=1}^{n-1}\binom{n}{i}$

Please inform me whether I've done this correctly and give pointers, thank you.

Note: suppose that each apple and orange has a unique number on them i.e. apple 1, apple 2....orange 1, orange 2

  • $\begingroup$ Since you have the same number $n$ of apples and oranges, they must alternate. Thus if they're interchangeable, there are only two ways to order them. $\endgroup$ – Dave Sep 6 '14 at 3:37
  • $\begingroup$ My interpretation is that all apples are identical, and all oranges are identical, so the answer is very simple. $\endgroup$ – André Nicolas Sep 6 '14 at 3:38

If the apples and oranges are individuals, perhaps because each has a student number, then there are only $2$ basic patterns allowed, $AOAOAO\dots AO$ and $OAOAOA\dots OA$.

In either case, the $n$ apples can be placed in the $A$ slots in $n!$ possible orders, and for each order the $n$ oranges can be placed in the $O$ slots in $n!$ ways, for a total of $2(n!)^2$.

But I think that unless we are told explicitly that the apples are distinct from each other, as are the oranges, the natural interpretation is that they are not, giving answer $2$.

Remark: Your first attempt yielded $(n!)^2$. That is close to right under the "distinct" hypothesis, except that it does not take into account that there are $2$ basic allowed patterns.

I have not understood the reasoning that may underlie the second attempt. The product you get is not equal to $\sum_1^{n-1}\binom{n}{i}$.


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.