3
$\begingroup$

Find the number of ways a string of numbers (that may contain similar items) can 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\}$ can 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.

  • 0
    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.2012-05-21

1 Answers 1

8

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.

  • 0
    (+1) In fact, the sign is $(-1)^{2+2+1}=-1$.2017-01-09