# Why is the following not $S(n,3)$ where $S(n,k)$ is a Stirling number of the second kind? (almost solved)

In an attempt to relate the number of partitions of integers to that of partitions of distincts objects I stumbled, in the particular case of $$k:=3$$, on the following sum

$$\sum_{\genfrac{}{}{0pt}{1}{p\leq q \leq r}{p+q+r =n}} \frac{n!}{p!\, q!\, r!} \times \begin{cases} 1 & \text{if}\ p< q where $$S(n,k)$$ denotes the number of partitions of a set of $$n$$ distinct objects into $$k$$ non-empty subsets while the number $$p_k(n)$$ of summands/indices of summation/ is the number of way of writing $$n$$ as a sum of $$k$$ non zero integers.

Remark: one finds the argument leading to the first equality in this Q$$\&$$A while the last equality is stated in wikipedia and proved for example here.

My reasoning: compute for each given partition $$n=p+q+r$$ of integers the number of partitions of $$\{1,2,\cdots , n\}$$ into $$3$$ subsets of respective cardinal $$p,q$$ and $$r$$. That quantity is in fact the cardinal of the orbit $$O_{(p,q,r)}$$ of e.g. the set partition $$\Pi_{(p,q,r)}:=\left\lbrace \vphantom{\frac{a}{a}}\{1, 2 , \cdots , p\}, \{p+1,\cdots , p+q\}, \{p+q+1 , \cdots , n\} \right\rbrace$$ under the group $$\mathfrak{S}_n$$ of permutations, which is given by the formula $$\operatorname{Card}\left( O_{(p,q,r)} \right)= \frac{\operatorname{Card}\left( \mathfrak{S}_n\right) }{\operatorname{Card}\left(\operatorname{Stab}\Pi_{(p,q,r)}\right)} = \frac{n!}{p!\, q!\, r!} \times \begin{cases} 1 & \text{if}\ p\neq q \neq r,\; p\neq r\\ \frac{1}{2} & \text{if exactly two indices are equal}\\ \frac{1}{3!} & \text{if}\ p=q=r= \frac{n}{3} \end{cases}$$ where the stabilizer subgroup $$\operatorname{Stab}\Pi_{(p,q,r)}$$ consists of all the permutations of $$\mathfrak{S}_n$$ that leave the partition $$\Pi_{(p,q,r)}$$ unchanged, e.g. permuting only elements withing $$\{1, 2 , \cdots , p\}$$ or when $$p=q$$ sending bijectively all elements of $$\{1, 2 , \cdots , p\}$$ to $$\{p+1, p+ 2 , \cdots , p+q\}$$ etc.

It's always like this... while writing this question I just noticed that in order for the two members of the first equation to be equal, one must exclude the case where any of $$p,q$$ or $$r$$ are $$0$$: so neither $$(0,0,n)$$, nor $$(0,q,r)$$ with $$q+r =n$$. It seems to work then... but I post the question anyway...

• It is exactly what you said, perhaps you can write it up nicely as an answer and accept it as such. Sep 1 at 11:23

Yeah I think one should not overlook the details... such as the following paradox in the first equality: $$\begin{split} \frac{(1+1+1)^n}{3!} & = \frac{1}{3!} \sum_{p+q+r =n} \frac{n!}{p!\, q!\, r!} \\ &\overset{??!!}{=} \frac{1}{3!} \sum_{\genfrac{}{}{0pt}{1}{p\leq q \leq r}{p+q+r =n}} \frac{n!}{p!\, q!\, r!} \times \begin{cases} 3! & \text{if}\ p< q R.h.s. is supposedly a sum of integer (with the interpretation that we are summing the cardinal of orbits, cf. question)... but l.h.s. isn't (as $$3^n$$ is not a multiple of $$2$$...)?!?!
Solution: again it is the case where $$p=q=0$$ that is problematic. Without the $$p\leq q\leq r$$ condition, it appears $$3$$ times ($$(p,q,r)= (0,0,n)$$ or $$(0,n,0)$$ or $$(n,0,0)$$) and hence contributes $$\frac{1}{3!}\, \frac{n!}{n!} \times 3 = \frac{1}{2}$$ so finally the first equality is valid!
Now we just have to retrieve the number of set-partitions in two or one subsets (reformulation of the cases $$(0,q,r)$$ with $$q+r=n$$ or $$(p,q,r) = (0,0,n)$$) with the caveat that the last partition was counted $$\frac{1}{2}$$. By analogy, the number of partitions into two or fewer subsets is
$$\sum_{\genfrac{}{}{0pt}{1}{q\leq r }{q+r=n}} \frac{n!}{q! \, r!} \times \begin{cases} 1 & \text{if}\ q < r \\ \frac{1}{2} & \text{if}\ q=r= \frac{n}{2} \end{cases} = \frac{2^n}{2}$$ Here the partition $$(q,r)=(0,n)$$ really contributes $$1$$ so we'll have to artificially add a $$\frac{1}{2}$$ at the end to obtain $$\sum_{\genfrac{}{}{0pt}{1}{{\color{red} 0 < p}\leq q \leq r}{p+q+r =n}} \frac{n!}{p!\, q!\, r!} \times \begin{cases} 1 & \text{if}\ p< q