3
$\begingroup$

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$

  • 1
    http://en.wikipedia.org/wiki/Burnside's_lemma2012-01-01

1 Answers 1

1

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.

  • 0
    @AlexanderKondratskiy Yes, that's exactly it!2012-01-02