1
$\begingroup$

Consider the following scenario:

In how many ways, $f$, can you arrange $n$ different coloured lightbulbs in $m$ sockets ($n \geq m$) if all permutations of the same $m$ different coloured lightbulbs are considered the same configuration?

By experiment, I have come to the conclusion that

\begin{equation*} f(m,n) = \sum_{i = 1}^{n - m + 1}\left(\sum_{j = 1}^{i}j^{m - 2}\right) \end{equation*}

for all $m,n \in \mathbf{N}$ with $n \geq m$.

Is this correct, and if it is, why is it correct?

Example: $5$ different coloured lightbulbs ($L_{1},\dots,L_{5}$) can be placed in $3$ suckets in the follwing $10$ ways:

\begin{align*} &L_{1},L_{2},L_{3},\\ &L_{1},L_{2},L_{4},\\ &L_{1},L_{2},L_{5},\\ &L_{1},L_{3},L_{4},\\ &L_{1},L_{3},L_{5},\\ &L_{1},L_{4},L_{5},\\ &L_{2},L_{3},L_{4},\\ &L_{2},L_{3},L_{5},\\ &L_{2},L_{4},L_{5},\\ &L_{3},L_{4},L_{5}. \end{align*}

Therefore,

\begin{equation*} f(3,5) = 10. \end{equation*}

P.S. This is not some homework assignment; it's just something I've tried to figure out for fun.

$\endgroup$
  • 2
    $\begingroup$ You want to choose $m$ things from a set of $n$ things ... en.wikipedia.org/wiki/Combination ... Pascal's triangle ... binomial coefficients ? $\endgroup$ – Donald Splutterwit Mar 31 '17 at 19:12
  • $\begingroup$ Pasal's triangle was indeed what I was looking for. Thank you very much. $\endgroup$ – Svend Tveskæg Mar 31 '17 at 19:27
  • 1
    $\begingroup$ Your formula only works for $m=2$ and $3$ due to the Pascal's hockey stick identity for binomial coefficients. In general you want the binomial coefficient for choosing $m$ things from $n$ things: $$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$ $\endgroup$ – N. Shales Mar 31 '17 at 19:29
1
$\begingroup$

I think you're just looking for $\binom{5}{3}=10$ which is given by:

$$\binom{n}{m}=\frac{n!}{(n-m)!m!}$$

This is the standard formula for calculating combinations - i.e. the number of arrangements in which the order chosen doesn't matter.

This is because $\frac{n!}{(n-m)!}$ gives you the number of ways of choosing (i.e. $5\times4\times 3$) and then you divide by $m!$ to discount the duplicates since you have counted $3\times2\times1$ duplicates of each result.

You wouldn't do this last division if you wanted to enumerate all the distinct solutions.

$\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.