We have a set $S$ with $E$ elements of which only $N$ are unique. We of course know how many repetitions of each of the $N$ elements are present: element $s_i$ is repeating $t_i$ times.

I would like to count the number of ways we can divide the $E$ elements in $N$ blocks of size $k_1, k_2, \cdots , k_N$ when the elements within the block are indistinguishable.

If the $E$ elements are all unique, we can answer directly using the Bell Polynomials.

Do you think is it possible to extend the above result ?

  • $\begingroup$ Just to be sure I understand if we have the multiset $\{2\bullet3, 3\bullet4\}$ meaning $2$ copies of $3$ and $3$ copies of $4$, and $N=3,$ then $2\bullet3,2\bullet4,1\bullet4$ is an acceptable partition, correct? Does order matter? Is the previous partition the same as $2\bullet3,1\bullet4,2\bullet4?$ $\endgroup$ – saulspatz Aug 19 '18 at 16:15
  • $\begingroup$ In your example $k_1=2,k_2=2,k_3=1$ and $S={3,3,4,4,4}$ the possible partitions are 5: $(3,3)(4,4)(4)$ ; $(3,4)(3,4)(4)$ ; $(3,4)(4,4)(3)$ ; $(4,4)(3,4)(3)$ ; $(4,4)(3,3)(4)$ $\endgroup$ – Ninja Warrior Aug 19 '18 at 17:07

It appears that we have a simplified version of the computation from the following MSE link. Using the notation that was presented there we obtain the closed form

$$\left[\prod_{k=1}^l A_k^{\tau_{k}}\right] \prod_{k=1}^m Z\left(S_k; \sum_{k'=1}^l A_{k'}\right)^{\sigma_k}.$$

In terms of combinatorial classes we have made use of the unlabeled class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=\sigma_k} \left(\textsc{MSET}_{=k} \left(\sum_{k'=1}^l \mathcal{A}_{k'}\right)\right).$$

Note that the cycle index will create the intermediate multisets during evaluation.


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.