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 <r\\ \frac{1}{2} & \text{if exactly two indices are equal}\\ \frac{1}{3!}& \text{if}\ p=q=r= \frac{n}{3} \end{cases}\enspace =\ \frac{3^n}{3!} \quad \overset{???}{\underset{\textbf{WHY?}}{\neq}} S(n,3)= \frac{3^{n-1} - 2^n +1}{2} $$ 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...

  • $\begingroup$ It is exactly what you said, perhaps you can write it up nicely as an answer and accept it as such. $\endgroup$
    – Phicar
    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\\ 3 & \text{if exactly two indices are equal}\\ 1 & \text{if}\ p=q=r= \frac{n}{3} \end{cases} \end{split} $$ 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 <r\\ \frac{1}{2} & \text{if exactly two indices are equal}\\ \frac{1}{3!} & \text{if}\ p=q=r= \frac{n}{3} \end{cases} = \frac{3^{n-1}-2^n+1}{2}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.