1
$\begingroup$

Suppose that I have $n$ distinct objects. In how many ways can I colour the $n$ objects with at most $n$ distinct colours up to permutations of colours. For e.g

$1,1,1,1$ is the same thing as $2,2,2,2$

$1,1,2,3$ is the same thing as $4,4,1,2$
but $1,1,2,3$ is different from $2,3,1,1$

My approach is count the number of ways to use exactly $i \leq n$ colours to colour the $n$ objects using the inclusion-exclusion principle then divide by $ \binom{n}{i}$. Then I add everything up. However I'm not sure if the method is correct and I'm also looking for a general solution in terms on $n$.

$\endgroup$
2
$\begingroup$

What you want to count is the number of different partitions of an $n$ element set into $\leq n$ nonempty subsets. The number of these partitions is the Bell number $B_n$. There is a recursive formula for these and an asymptotic formula involving the Lambert $W$-function.

$\endgroup$
  • $\begingroup$ Thanks. I didn't see the problem was simply a partition of a set. $\endgroup$ – A. Napster Dec 29 '17 at 19:17
0
$\begingroup$

By way of enrichment I would like to point out that this can also be done by Power Group Enumeration as defined by Harary and Palmer. Here we have that the slot permutation group is the identity $E_n$ with cycle index $Z(E_n) = a_1^n$ and the object permutation group is the symmetric group $S_n$ with cycle index given by the exponential formula

$$Z(S_n) = [z^n] \exp\left(\sum_{l\ge 1} a_l \frac{z^l}{l}\right).$$

Now to apply PGE we must cover the single permutation $a_1^n$ with cycles from the permutations in $Z(S_n).$ Clearly if the latter has $k$ fixed points this can be done in $k^n$ ways. Hence we introduce the mixed generating function with fixed points marked

$$G(z, u) = \exp\left(uz-z+\log\frac{1}{1-z}\right).$$

The answer is thus given by (we turn $u^k z^n$ into $k^n z^n$)

$$ [z^n] \left. \left(u\frac{\partial}{\partial u}\right)^n G(z, u) \right|_{u=1} \\ = [z^n] \left. \left(u\frac{\partial}{\partial u}\right)^n \frac{1}{1-z} \exp(z(u-1)) \right|_{u=1} \\ = \left. \left(u\frac{\partial}{\partial u}\right)^n \sum_{q=0}^n \frac{(u-1)^q}{q!} \right|_{u=1} \\ = \left. \left(u\frac{\partial}{\partial u}\right)^n \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^q {q\choose p} (-1)^{q-p} u^p \right|_{u=1} \\ = \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^q {q\choose p} (-1)^{q-p} p^n.$$

We recognize Stirling numbers at this point but we may also continue with the EGF

$$F(w) = \sum_{n\ge 0} \frac{w^n}{n!} \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^q {q\choose p} (-1)^{q-p} p^n \\ = \sum_{n\ge 0} \frac{w^n}{n!} \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^q {q\choose p} (-1)^{q-p} n! [v^n] \exp(pv) \\ = \sum_{n\ge 0} w^n [v^n] \sum_{q=0}^n \frac{1}{q!} \sum_{p=0}^q {q\choose p} (-1)^{q-p} \exp(pv) \\ = \sum_{n\ge 0} w^n [v^n] \sum_{q=0}^n \frac{1}{q!} (\exp(v)-1)^q.$$

Now since $\exp(v)-1=v+\cdots$ we may extend $q$ beyond $n$ as there is no contribution to the coefficient extractor $[v^n]$ in that case, getting

$$\sum_{n\ge 0} w^n [v^n] \sum_{q\ge 0} \frac{1}{q!} (\exp(v)-1)^q \\ = \sum_{n\ge 0} w^n [v^n] \exp(\exp(v)-1) = \exp(\exp(w)-1)$$

and we see that we indeed have Bell numbers here as observed in the reply that was first to appear. Note also that PGE rests on the Burnside lemma which was suggested in the comments.

$\endgroup$

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.