# Partial Derangement formula for permutation with repeated elements

MY question is to get general formula for repeated permutation: For any $$n$$ numbers,

$$n=1,2,3, \ldots$$

Derangement formula: $$D_n=!n=(n−1)(!(n−1)+!(n−2))$$ Here the numbers are distinct from one another (no repetition of any number in permutation) https://en.wikipedia.org/wiki/Derangement

Partial derangement: Instead of $$n$$ derangement we have $$k$$ derangements, for $$n \geq 0$$ and $$0 \leq k \leq n$$, the rencontres number $$D_{n, k}$$ Partial derangement or rencontre number: https://en.wikipedia.org/wiki/Rencontres_numbers

Is there any general formula for partial derangement of permutation with repeated number (repeated numbers exist in permutation). For example:

$$n=1,1,2,2,3,3,4,5$$

Any general formula for Derangement of $$k$$ numbers??

Rewriting your above example: suppose A is blue and B,C are red; we have the permutations: $$\begin{matrix} ABC\rightarrow ABC \\ ABC\rightarrow ACB\\ ABC\rightarrow BAC \\ ABC\rightarrow BCA \\ ABC\rightarrow CAB \\ ABC\rightarrow CBA \\ \end{matrix}$$ For example, we have $$N=3$$,$$M=2$$ ($$1) Trying to calculate Probability : Example -1: $$P(\overline{A \ or \ B} )$$ , Results: $$\frac{3}{6}$$

Similarly Example -2: $$P(\overline{A \ or \ C})$$

$$P$$: Probability, $$\overline{A \ or \ B}$$ :not hit A or B and so on. Any generalized form of formula to calculate above probability?? I tried with inclusion and exclusion principle but not sure.

Another bigger scenario: suppose A is blue, B is red, C,D are green; We get final polynomial: $$2x^4+10x^2+8x+4$$ We have the permutations: $$\begin{matrix} ABCD\rightarrow ABCD (hit-4) \\ ABCD\rightarrow ABDC (hit-4)\\ ABCD\rightarrow ACBD (hit-2) \\ ABCD\rightarrow ACDB (hit-2) \\ ABCD\rightarrow ADBC (hit-2) \\ ABCD\rightarrow ADCB (hit-2) \\ ABCD\rightarrow BACD (hit-2) \\ ABCD\rightarrow BADC (hit-2) \\ ABCD\rightarrow BCAD (hit-1) \\ ABCD\rightarrow BCDA (hit-1) \\ ABCD\rightarrow BCAD (hit-1) \\ ABCD\rightarrow BCDA (hit-1) \\ ABCD\rightarrow CABD (hit-1) \\ ABCD\rightarrow CADB (hit-1) \\ ABCD\rightarrow CBAD (hit-2) \\ ABCD\rightarrow CBDA (hit-2) \\ ABCD\rightarrow CDAB (hit-0) \\ ABCD\rightarrow CDBA (hit-0) \\ ABCD\rightarrow DABC (hit-1) \\ ABCD\rightarrow DACB (hit-1) \\ ABCD\rightarrow DBAC (hit-2) \\ ABCD\rightarrow DBCA (hit-2) \\ ABCD\rightarrow DCAB (hit-0) \\ ABCD\rightarrow DCBA (hit-0) \\ \end{matrix}$$

For example, we have $$N=4$$,$$M=3$$ (any number less than $$N$$). Trying to calculate Probability : Example -1: $$P(\overline{A \ or \ B \ or \ C})$$ , Results $$\frac{something}{24}=?/24$$

Similarly Example -2: we have $$N=4$$,$$M=2$$ ($$1). Trying to calculate Probability : $$P(\overline{A \ or \ C})$$.

Inclusion exclusion principle: $$P(A \ or \ B \ or C)$$ =$$P(A)+ P(B) + P(C) -P(A \cap B) - P(A \cap C) -P(B \cap C) + P(A\cup B \cup C)$$. Just trying to get formula to calculate the probability of any number of $$N$$ and $$M$$ which will become complex for large number of $$N$$ and $$M$$!!!! Any generalized form of formula to calculate above probability from the rook polynomial theory??

I think I can rewrite the problem according to your statement: Given a set $$S$$ of $$n_1+n_2+⋯+n_k$$ distinguishable, colored objects, with $$n_i$$ of them colored with the ith color, how many permutations are there of $$S$$ so that either any of $$r$$ elements ($$r<=k$$) map to their own color (or does not map their own color)?

• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig Sep 19 '19 at 9:56
• Thanks @ N. F. Taussig. – Tahid Sep 25 '19 at 9:21
• @Tahid Your problem is not very clear. I had to do some guessing as to your question since your original post was not clear, but maybe I was wrong. You need to find a way to state your question in a mathematically precise form. What do you mean by $P(\overline{A \ or \ B} )$? The probability that $A$ or $B$ do what? – Jair Taylor Oct 5 '19 at 5:24
• $P(\overline{A \ or \ B})$: Probability of not ($A$ or $B$). Simply $P(\overline{A \ or \ B}) =1-P(A \ or \ B)$. It is fine, if I can get formula/way for $P(A \ or \ B)$. – Tahid Oct 5 '19 at 5:31
• Writing $P(A \text{ or } B )$ doesn't make sense if you don't specify what $A$ is supposed to represent. I'm assuming it has something to do with derangements. Please specify your problem completely in a single question. – Jair Taylor Oct 5 '19 at 5:37

I am going to assume your problem is the following:

Given a set $$S$$ of $$n_1 + n_2 + \cdots + n_k$$ distinguishable, colored objects, with $$n_i$$ of them colored with the $$i$$th color, how many permutations are there of $$S$$ so that exactly $$k$$ elements map to their own color?

You can solve this problem with a similar method to my answer to your previous question. That is, you can use rook theory.

Given a subset (or "board") $$B \subseteq [n] \times [n]$$, let $$r_{B,k}$$ be the the $$k$$-th rook number, that is, the number of placements of $$k$$ rooks on the board $$B$$ so that no two rooks are in the same row or column. Let $$h_{B,k}$$ be the $$k$$-th hitting number of $$B$$, defined to be the number of permutations $$\sigma \in S_n$$ so that $$\{(i,j) \in B | \sigma(i) = j\} = k$$. Put another way - we call any $$1$$ on the adjacency matrix of $$\sigma$$ that lands on the board $$B$$ a hit of $$\sigma$$. Then $$h_{B,k}$$ is the number of permutations $$\sigma \in S_n$$ with exactly $$k$$ hits in $$B$$.

Then the following relation holds:

$$$$\sum_{k=0}^n h_{B,k} x^k = \sum_{k=0}^n r_{B, k} (n-k)! (x-1)^k. \tag{*}$$$$

See, e.g., Theorem 1 in Remmel's notes here. This equation (*) allows you to find hit numbers from rook numbers, and vice verse.

Using the same notation there, let $$B = B_1 \oplus \cdots \oplus B_k$$ where $$B_i = [n_i] \times [n_i]$$. That is, $$B \subseteq [n] \times [n]$$ is the block-diagonal set consisting k disjoint squares with dimensions $$n_i \times n_i$$. Then the answer to your question is the $$k$$-th hit number $$h_{B,k}$$ of the board $$B$$. Thus it remains to find the rook numbers $$r_{B,k}$$; then we can use (*) to find $$h_{B,k}$$.

Define the rook polynomial $$r_B(x)$$ of a board $$B \subseteq [n] \times [n]$$ to be $$r_B(x) = \sum_{k=0}^n r_{B,k} x^k.$$ This is slightly different, but equivalent to, the definition of $$r_B(x)$$ I gave in the previous answer. But we still have $$r_{B_1}(x) r_{B_2}(x) = r_{B_1 \oplus B_2}(x).$$

Then if $$B$$ is the full square $$[n] \times [n]$$, we have $$r_B(x) = \sum_{k=0}^n {n \choose k}^2 \, k!\, x^k.$$ Call this $$L_n(x)$$. Then to find the partial derangement numbers, expand $$r_B(x) = L_{n_1}(x) \cdot \cdots \cdot L_{n_k}(x)$$ and apply (*).

Example: Let $$n=3$$, with $$n_1 = 1$$, $$n_2 = 2$$. Compute $$L_{1}(x) = 1+x$$, $$L_2(x) = 1 + 4x + 2x^2$$. Then if $$B$$ is the block diagonal subset $$[1] \times[1] \oplus [2] \times [2]$$ Then $$r_B(x) = L_1(x) L_2(x) = 1 + 5x + 6x^2 + 2x^3.$$ Send each power $$x^k$$ to $$(n-k)! (x-1)^k$$ to get

\begin{align*}3! + 5\cdot 2! (x-1) + 6 \cdot 1! (x-1)^2 + 2 \cdot 0!(x-1)^3 &= 4x + 2x^3\\ &= \sum_{k = 0}^n h_{B,k} x^k.\end{align*}

This means that if $$B$$ that the number of permutations $$\sigma \in S_n$$ with $$1$$ hits in $$B$$ is $$4$$, the number of permutations $$\sigma \in S_n$$ with $$3$$ hit in $$B$$ is 2, and there are no permutations with $$0$$ or $$2$$ hits. (note that the coefficients here sum to $$2 + 4 = 6 = 3!$$, the number of permutations of $$S_3$$.)

To verify, suppose $$1$$ is blue and $$2,3$$ are red; we have the permutations

\begin{align*} 123 \rightarrow 123\,\, \text{(3 hits)} \\ 123 \rightarrow 132\,\, \text{(3 hits)} \\ 123 \rightarrow 213\,\, \text{(1 hit)}\hphantom{1} \\ 123 \rightarrow 231\,\, \text{(1 hit)}\hphantom{1} \\ 123 \rightarrow 312\,\, \text{(1 hit)}\hphantom{1} \\ 123 \rightarrow 321\,\, \text{(1 hit)}\hphantom{1} \\ \end{align*}

• Thanks @ Jair Taylor. Nice information. I got a lot of information (as i m in travel for my conference, i could not have any feedback to you). I will have some inquery soon. – Tahid Sep 25 '19 at 9:20
• I have written the problem again with examples from your given information. @Jair Taylor. – Tahid Oct 5 '19 at 4:53