Proof that the Number of Maximal Chains of $℘(S)$ Containing $X ⊆ S$ where $|S|=n$ and $|X|=s$ is $s!(n-s)!$

Question

I came across a proof which I could use, but I don't quite understand everything. Could someone explain this to me?

Lemma

• Let $S$ be a set with $n$ elements. Let $X ⊆ S$ be a subset with $|X|=s\leq n$. Then the number of maximal chains of $℘(S)$ that contain $X$ is $s!(n-s)!$.

Proof

A maximal chain of $℘(S)$ which contains $X$ is obtained by a permutation $a_1, ..., a_n$ of the elements of $S$, for which ${a_1,...,a_s} = X$.

There are $s!$ possibilities to find such an arrangement of the elements of $X$, and for each of them there are $(n-s)!$ possibilities to prolong it with sequences whose elements are in $S \setminus X$.

On the whole we so obtain $s!(n-s)!$ maximal chains which contain $X$.

Answer 1

For every maximal chain, the first $s$ items belong to $X$ and the other $n-s$ are elements not in $X$. We can shuffle the first $s$ elements or the last $n-s$ elements and we'll still have a maximal chain:

$$\underbrace{a_1, \dots, a_s}_{s!\text{ ways to reshuffle}} ,\underbrace{a_{s+1}, \dots, a_n}_{(n-s)!\text{ ways to reshuffle}}.$$

Thus, there is a total of $s!(n-s)!$ maximal chains.