Probability concerning permutations of non-distinct objects

combinatoricsprobability

I have four not all distinct objects, say $1,1,2,2$, and I am considering the following two settings of the probability concerning the permutations. Let $R_i$ be the number of the $i$-th object, $i=1,2,3,4$.

For any permutation $\sigma_4$ of $1,1,2,2$:

(i) Suppose that
$$
P((R_1,R_2,R_3,R_4)=\sigma_4)=\frac{4!}{2!2!}=6.
$$

(ii) We think of the four elements are distinct, i.e.
$$
P((R_1,R_2,R_3,R_4)=\sigma_4)=4!=24.
$$

Then, after some calculations, I found that the probability distributions of $(R_1,R_2,R_3,R_4)$ under (i) and (ii) are the same. For example,
$$
P(R_1=1)=\frac{1}{2}
$$
in either case. Please correct me if i am wrong, thanks. And, is there any intuitive explanation for this? Thanks a lot.

Best Answer

Explanation 1: $P(R_1=1)$ is the proportion of objects which have the label $1$.

Explanation 2:

Every indistinguishable permutation on $1,1,2,2$ corresponds to $4$ distinguishable permutations on $1,1,2,2$; to turn an indistinguishable permutation into a distinguishable permutation there is a choice of whether or not to swap the $1$s, and a choice of whether or not to swap the $2$s, which gives us $2\times 2$ options.

So for every indistinguishable permutation which begins with a $1$, there are exactly $4$ distinguishable permutations which begin with a $1$.

Explanation 3:

A group is a set $S$ equipped with a binary operation $*$ such that:

For any $a,b$ in $S$, $a*b$ is in $S$

There exists an element $e$ in $S$ (called the identity element) such that, for any $a,b$ in $S$, $a*e=e*a=a$.

For every element $a$ in $S$, there exists an element $a^{-1}$ (called the inverse) such that $aa^{-1}=a^{-1}a=e$

The group of all permutations of $4$ distinguishable objects is denoted by $S_4$. It contains $24$ elements. As an example, if $a$ is the permutation which swaps the first two objects then $a^{-1}=a$ and $aa^-1$ is the 'do nothing' permutation.

Denote the group of (indistinguishable) permutations of $1,1,2,2$ by $H$.

There is a homomorphism $\phi$ from $S_4$ to $H$, which is the map from $S_4$ to $H$ which 'forgets' whether or not it swapped the $1$s and 'forgets' whether or not it swapped the $2$s. The set of elements in $S_4$ which are mapped to the identity permutation in $H$ is called the kernel of the homomorphism $\phi$. It contains $4$ elements and is denoted by $\text{ker}\{\phi\}$

A subgroup $N$ of the group $G$ is a normal subgroup if $gng^{-1}$ is in $N$ for any $g$ in $G$ and $n$ in $N$.

If $N$ is a normal subgroup of $G_1$ then the quotient group $G_1/N$ is defined as follows: Start with the group $G_1$. If two elements $g_1,g_2$ in $G$ satisfy $g_1n_1=g_2n_2$ for some $n_1,n_2$ in $N$ then declare $g_1$ and $g_2$ to be equal.

The first isomorphic theorem states that, for any surjective homomorphism $\varphi:G_1\rightarrow G_2$, $\text{ker}\{\varphi\}$ is a normal subgroup of $G_1$ and $G_1/\text{ker}\{\varphi\}$ is isomorphic to $G_2$.

The first isomorphism theorem implies that four elements in $S_4$ are mapped to every element of $H$.

$\phi$ maps any permutation in $S_4$ which begins with a $1$ to a permutation in $H$ which begins with a $1$, and it also maps permutations which do not begin with a $1$ to permutations which do not begin with a $1$.

Related Solutions

Combinatorics – Circular Permutations with Indistinguishable Objects

I wrote a series of blog posts which explains how to solve questions like this; the relevant one is here. The generating function you want is

$$\frac{1}{n} \sum_{d | n} (x_1^{n/d} + ... + x_k^{n/d})^d \varphi \left( \frac{n}{d} \right)$$

where the coefficient of $x_1^{r_1} ... x_k^{r_k}$ is the number you want.

Combinatorics – How to Find Number of k-Permutations of n Objects with x Types

There's probably not going to be an easy way to do this... Consider two different examples of 15-letter "permutations". Then the number of permutations with that multiset of digits depends on the proportions of the chosen digits.

If you really want to do this, you can sum $k!/(s(1)! s(2)! \cdots s(x)!)$ (called the mulitnomial coefficient) over all partitions of $s(1)+s(2)+ \cdots +s(x)=k$ [in this partition s(i) is allowed to be zero and order is important] such that $s(i) \leq r(i)$ for all i. The part s(i) says you have s(i) copies of the i-th letter. The number of permutations with s(i) i-th letters is given as above, by the Orbit Stabiliser Theorem.

Although, this is only one step better than the caveman's counting formula: sum_P 1 where P is the set of permutations you want to count. I.e. just count them one-by-one.

EDIT: While I'm making a few touch-ups, here's GAP code that implements the above formula.

NrPermIdent:=function(k,T)
  local PSet,x;
  x:=Size(T);
  PSet:=Filtered(OrderedPartitions(k+x,x)-1,p->ForAll([1..x],i->p[i]<=T[i]));
  return Sum(PSet,p->Factorial(k)/Product(p,i->Factorial(i)));
end;;

where T is a list of bounds and k is the number of terms in the partition.

For example:

gap> NrPermIdent(15,[4,5,8,3]);
187957770

As another indication that finding a simple formula for these numbers is not going to be easy, observe that NrPermIdent(n,[n,k]) is equal to $\sum_{0 \leq i \leq k} {n \choose k}$ (which is considered a difficult sum to find -- see: https://mathoverflow.net/questions/17202/). I remember reading somewhere (most likely in A=B) that you can prove there is no "closed-form" solution for this.

Best Answer

Related Solutions

Combinatorics – Circular Permutations with Indistinguishable Objects

Combinatorics – How to Find Number of k-Permutations of n Objects with x Types

Related Question