Take the 2-minute tour ×

I'm not sure if I worded the question properly, but I'm trying to understand how to solve certain problems. I'll begin with things I think I understand.

Consider for example the problem of grouping $n$ balls into bags. If the balls are all identical, and we want to know how many ways we can separate them into an unordered set of bags (any number of bags), it is equivalent to integer partitioning of $n$. Here, the fact that the balls are identical, could be interpreted as: groupings are equivalent modulo any permutation of the balls

Conversely, if the $n$ balls are all distinct then the answer can be expressed using bell numbers, $B_n$, for the number of possible partitions of n distinct elements. Balls are distinct, means groupings are all distinct modulo any permutation.

Where I'm going with this, is how do you think of problems like this: If you have 1 green ball and 3 red balls {G, R, R, R}, how many distinct groupings of these balls can be made? All red balls are identical, all green balls are identical, but a green and red ball are distinct. In a sense, only some permutations are allowed to make two groupings equivalent.

The answer to the above problem is 7, but what is the combinatorial way of solving any generalization of the problem?

Thank you in advance, Alex.

P.S. I arrived at this question trying to calculate the number of factorizations of an integer given its prime factors. The above problem I think is equivalent to counting the number of factorizations of $54 = 2 \cdot 3 \cdot 3 \cdot 3$. Putting balls into a bag is the same as multiplying the corresponding primes. Thus { {G, R} {R} {R} } corresponds to $54 = 6 \cdot 3 \cdot 3$

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Expanding on Qiaochu's comment, what you want to do is use Burnside's lemma, which relates the number of distinct arrangements of a set modulo some group of permutations (known as orbits) to the size of the group of permutations and the number of elements in the set fixed by each permutation in the group. In symbols (using the same notation as Wikipedia) this is $$|X/G| = \frac{1}{|G|}\sum\limits_{g\in G} |X^g|$$ which we can apply to your first example of one green and three red balls. Let $X$ be the set of functions $f:\{1,2,3,4\}\to \{1,2,3,4\}$, and let $G=S_4\times S_3'$, where $S_3'$ is the subgroup of $S_4$ which fixes $1$, act on $X$ by $(\sigma,\sigma')\cdot f(x) = \sigma(f(\sigma'(x)))$.

Computation of $|X/G|$ (currently incomplete b/c I need sleep, to be finished): We have $|G| = 24\times 6 = 148$. In this case, I will determine the sum on the RHS somewhat differently than normal, by counting the number of elements of $G$ which fix each function (which clearly gives the same sum). If a function $f$ is invariant on $1\leq n\leq 3$ elements other than $1$ and maps onto $1\leq m\leq 4$ elements, then there are $n!(4-m)!$ elements $(\sigma,\sigma')\in G$ fixing $f$ such that the range of $f$ and the set affected by $\sigma$ are disjoint. It remains to cover the cases where $\sigma$ is a two-cycle, three-cycle, and product of disjoint two-cycles when restricted to the range of $f$.

Now, this may seem like an awful lot of work to answer a simple question, and in the case of your first example it is. But it allows for a general formula. For your motivating example with $$x = \prod\limits_{i=1}^n p_i^{e_i}, c = \sum\limits_{i=1}^n e_i$$ the set becomes $$X = \left\{f: \{1,\ldots,c\}\to \{1,\ldots,c\}\right\}$$ and the group becomes $$G = S_c\times S_{e_1}\times \cdots \times S_{e_n}$$ which acts on a function $f\in X$ by $$(\sigma_0,\sigma_1,\ldots,\sigma_n)\cdot f(x) = \sigma_0(f(\sigma_j(x)))$$ where $j$ is such that $$\sum\limits_{i=1}^j e_i < x\leq \sum\limits_{i=1}^{j+1} e_i$$ which may be torturous to work with, but at least it's a unified framework.

share|improve this answer
Thank you for the answer! I was looking at the problem as a hobby, and I was not very familiar with group theory up until now. I am intrigued, so I've been reading up, trying to understand the lemma, and how it relates to the motivating example. If you don't mind, I have a few questions on this: - The set $X$ of functions- is it itself $S_4$, or the functions don't have to be bijective? - In the end, could you relate each term to its intuition? I am not entirely sure how $X / G$ can describe the groupings. Thank you for your insight –  Alexander Kondratskiy Jan 2 '12 at 6:41
@AlexanderKondratskiy It is not $S_4$, as the functions do not have to be bijective. Each function can be thought of as assigning each element $1,2,3,4$ to either group $1$, group $2$, group $3$, or group $4$. The partition of $\{1,2,3,4\}$ that is the whole set corresponds to any function which assigns $1,2,3,4$ all to the same group (of which there are $4$). –  Alex Becker Jan 2 '12 at 6:45
@AlexanderKondratskiy As for how X/G describes the groupings, each element of $X/G$ is a collection of sets, where each element in a set is equivalent to each other element in that set modulo the permutations in $G$. That is, for any two elements $a,b$ in the same set we have some $g\in G$ such that $g\cdot a = b$. –  Alex Becker Jan 2 '12 at 6:49
Awesome! Mind blown :D. $S_3'$ acts to define that the red balls are interchangeable, X acts as the set of "grouping functions", and $S_4$ specifies that the bags/groups are unordered. Thanks! –  Alexander Kondratskiy Jan 2 '12 at 7:10
@AlexanderKondratskiy Yes, that's exactly it! –  Alex Becker Jan 2 '12 at 7:20

Your Answer


