# Combinatorics: $m$ Lightbulbs in $n$ sockets

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.

• You want to choose $m$ things from a set of $n$ things ... en.wikipedia.org/wiki/Combination ... Pascal's triangle ... binomial coefficients ? – Donald Splutterwit Mar 31 '17 at 19:12
• Pasal's triangle was indeed what I was looking for. Thank you very much. – Svend Tveskæg Mar 31 '17 at 19:27
• 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)!}$$ – N. Shales Mar 31 '17 at 19:29

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