1
$\begingroup$

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<M<N$) 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<M<N$). 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)?

$\endgroup$
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Sep 19 '19 at 9:56
  • $\begingroup$ Thanks @ N. F. Taussig. $\endgroup$ – Tahid Sep 25 '19 at 9:21
  • $\begingroup$ @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? $\endgroup$ – Jair Taylor Oct 5 '19 at 5:24
  • $\begingroup$ $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)$. $\endgroup$ – Tahid Oct 5 '19 at 5:31
  • $\begingroup$ 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. $\endgroup$ – Jair Taylor Oct 5 '19 at 5:37
0
$\begingroup$

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:

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

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*}

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tahid Sep 25 '19 at 9:20
  • $\begingroup$ I have written the problem again with examples from your given information. @Jair Taylor. $\endgroup$ – Tahid Oct 5 '19 at 4:53

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.