Understanding Stirling no of first kind

266 Views Asked by At

I was reading about Stirling no of the first kind, so $ \left[ \frac{n}{k} \right] $ represent no of k cycles of n items, so in $ \left[ \frac{4}{2} \right] $ there would be 11 such combinations, of this $ \left[ 1, 4 \right] \left[ 2, 3 \right] $, I think is same as $ \left[ 2, 3 \right] \left[ 1, 4 \right] $, however is it same as $ \left[ 1, 4 \right] \left[ 3, 2 \right] $ i.e does the internal permutation matter?

Also for $ \left[ \frac{3}{1} \right] $, the similar looking cycles, $ \left[ 1,2, 3 \right] $ and $ \left[2, 3,1 \right]$ are considered different right?

2

There are 2 best solutions below

0
On BEST ANSWER

I have read about this now and try to explain the answer to the first part.

In Stirling no of first kind we first distribute the no into indistinguishable boxes and then the inner circular permutations are counted, so if we have elements $\left\lbrace1,2,3,4\right\rbrace$ and $2$ boxes then we can distribute them first as

$$ \left\lbrace 1,2 \right\rbrace \left\lbrace 3,4 \right\rbrace \text{,} \left\lbrace 1,3 \right\rbrace \left\lbrace 2,4 \right\rbrace \text{,} \left\lbrace 1,4 \right\rbrace \left\lbrace 2,3 \right\rbrace \text{,}$$ $$\left\lbrace 1,2,3 \right\rbrace \left\lbrace 4 \right\rbrace \text{,} \left\lbrace 1,2,4 \right\rbrace \left\lbrace 3 \right\rbrace \text{,} \left\lbrace 1,3,4 \right\rbrace \left\lbrace 2 \right\rbrace \text{,} \left\lbrace 2,3,4 \right\rbrace \left\lbrace 1 \right\rbrace $$ Now since they count circular permutation $\left\lbrace 1,4 \right\rbrace $ will be same as $\left\lbrace 4,1 \right\rbrace$ but $\left\lbrace 1,2,3 \right\rbrace$ will be different from $\left\lbrace 1,3,2 \right\rbrace$, thus all the boxes containing 3 elements can be permuted in 2 ways, so total, $S[4,2] =4 . 2 +3 = 11 $ ways.

1
On

the similar looking cycles, $ \left[ 1,2, 3 \right] $ and $ \left[2, 3,1 \right]$ are considered different, right ?

I don't know. Let's spell it out and see. We have $$\begin{align}[1,2,3]&=\ldots,1,2,3,1,2,3,1,2,3,\ldots=\\&=\ldots,1,\color{red}{2,3,1},\color{blue}{2,3,1},2,3,\ldots=[2,3,1]\end{align}$$ and $$\begin{align}[2,3,1]&=\ldots,2,3,1,2,3,1,2,3,1,\ldots=\\&=\ldots,2,3,\color{red}{1,2,3},\color{blue}{1,2,3},1,\ldots=[1,2,3].\end{align}$$ Basically, a cycle has no beginning and no end, so the fact that the only difference between the two is their starting position, means that they are identical. Not so for $[3,2,1],$ though, which can never be made to overlap with $[1,2,3].$ I believe this picture to be quite intuitive in this particular regard.