Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
1  
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
add comment

1 Answer

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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