Group action & cardinality of a set.

108 Views Asked by At

You can find here more details and explanation on this question.

Question:

Let $n$ be a non-negative integer. For any family $ (i_1, \ldots, i_r) $ of non-negative integers such that $ i_1 + \ldots + i_r = n $, we denote by $ D(n, i_1, \ldots, i_r) $ the set of families $ (I_1, \ldots, I_r) $ of pairwise disjoint subsets of $ \left \{1;2;...;n \right \} $ such that the cardinality of each $ I_\ell $ is $ i_\ell $ for all $ \ell $.
Let $(i_1;...;i_r)$ and $d \in D(n; i_1;...;i_r ) $ calculate the stabilizer of $d$ .
From there, conclude on the cardinality of $D(n; i_1;...;i_r )$.

My answer

1-
Given $d \in D(n; i_1;...;i_r ) \Rightarrow d=(I_1;...;I_k;...; I_r)$ means find all the permuations $ \sigma \in S_n$ that when apply on every $I_k \in d$ doe not permute any element of $I_k$ out side $I_k$ itself.
For exemple if an $I_k= \left \{ 2; 7; 13 \right \}$ a valid permutation is $ \left \{ 7; 2; 13 \right \}$ or $ \left \{ 13; 2; 7 \right \}$ but NOT $ \left \{ 7; 2; 5 \right \}$.
Hence it is obvious that for any given $I_k \in d$ the number of correct permutation that can be proceed is $i_k !=|I_k|!$
Now we can conclude that $|d|=|I_1|! \cdot |I_2|! \cdot ... \cdot |I_r|!$

2-
Here I am a little bit stuck for finding the cardinality of $D(n; i_1;...;i_r )$. Any tip will be appreaciate :-)
More over I would like to know if my part "1-" is correct?

1

There are 1 best solutions below

1
On BEST ANSWER

I think that I have find a solution in all the cases I will be happy to know if it is correct and to read other solutions.

1-
For any fixed $d \in D(n;i_1,...,i_r)$ we are going to find what is $orb(d)$.
By definition $Orb(d) = \left \{ \sigma(d) : \sigma \in S_n \right \} $.
We want to prove that $ Orb(d) = D(n;i_1,...,i_r)$. The proof seems to me simple but long so I may will edit this answer in the futur in order to writte it. The main idea is to show that $Orb(d) \subseteq D(n;i_1,...,i_r) $ and that $D(n;i_1,...,i_r) \subseteq Orb(d)$

2-
Now by the Orbit Stabilizer theorem we have: $|G|=|Orb(x)| \cdot |Stab(x)| = |D(n;i_1,...,i_r)| \cdot |Stab(x)| \Rightarrow |D(n;i_1,...,i_r)| = \frac{|G|}{|Stab(x)|}= \frac{n!}{i_1! i_2! ... i_n!}$