Take the 2-minute tour ×

Find the number of ways string of numbers (may contain similar items) could be deranged so that a number is not placed in the same place as it or its similar numbers were placed.

For example, $\{0,0,0,1,1,1\}$ could be arranged in only one way and that is $\{1,1,1,0,0,0\}$.

$\{0,0,0,1,1,1,1\}$ cannot be arranged in any way.

$\{1,2,2,14\}$ can be arranged in $2$ ways i.e $\{2,1,14,2\}$, $\{2,14,1,2\}$.

$\{1,1,2,2,14\}$ can be arranged in $5$ ways i.e $\{2,2,1,1,14\}$, $\{14,2,1,1,2\}$, $\{2,2,14,1,1\}$, $\{2,2,1,14,1\}$, $\{2,14,1,1,2\}$.

Please do try and respond. Thanks in advance.

share|improve this question
The answer is in this Wikipedia section. –  joriki May 21 '12 at 6:26
marvis thank you for the edit, @joriki tht was incredile stuff by you. However for words made up of two different letters the answer was pretty simple, but i could not figure out the answer for more no. of numbers. Integrations I am familiar with. but in that secion it says for a certain sequence of polynomials P.. I didnt understand how to implement that P, and what could be the possible x value. A little more clarification on this will be very helpful. Thanks in advance. –  The Recruit May 21 '12 at 7:00

1 Answer 1

The answer is given in this Wikipedia section: Up to a sign, the number of such derangements is given by

$$\int_0^\infty L_{n_1}(x)\cdots L_{n_r}(x)\mathrm e^{-x}\mathrm dx\;,$$

where $r$ is the number of items, $n_i$ is the number of occurrences of item $i$ and $L_k$ is the $k$-th Laguerre polynomial. For instance, for $1,1,2,2,14$, we have $r=3$, $n_1=2$, $n_2=2$, $n_3=1$, so up to a sign the number of derangements is

$$ \begin{align} \int_0^\infty L_2(x)L_2(x)L_1(x)\mathrm e^{-x}\mathrm dx &= \int_0^\infty \frac12(x^2-4x+2)\frac12(x^2-4x+2)(1-x)\mathrm e^{-x}\mathrm dx \\ &= \int_0^\infty\left(-\frac14x^5+\frac94x^4-7x^3+9 x^2-5x+1\right)\mathrm e^{-x}\mathrm dx \\ &=-4\;. \end{align} $$

This indicates an error in your example, and indeed, the arrangement $2,2,1,1,14$ is not a derangement since the $14$ is in the same place.

share|improve this answer
I m spell bound!! Thank you.. :) Got a crystal clear idea.. –  The Recruit May 21 '12 at 10:10

Your Answer


