Calculating the number of combinations in a list expansion

combinations

How would you calculate the total unique combinations given a list of M elements padded with N additional elements (all the same) at any indexes within the list?

For example, say you have the list m = [a, b, c], and you want to generate all combinations padded with elements n = [z], this would generate 4 combinations, [z, a, b, c], [a, z, b, c], [a, b, z, c], [a, b, c, z].

For m = [a, b, c, d] and n = [z, z], it becomes more complex, with the result having 15 unique combinations, like, [z, z, a, b, c, d], [z, a, z, b, c, d], etc.

I'm trying to write a formula, f(m,n), that will return the total number of combinations, but I'm not sure how to handle the uniqueness factor. At first I thought it was simply f(m,n) = (m+1)*n. That predicts correctly for m=3,n=1 and m=4,n=1 but that fails to predict for m=4 and n=2, which results in 15 unique combinations.

So then I thought it was a summation of these functions, like:

f(m,n) = sum((m+1)*(n-i) for i in range(n))

This correctly predicts 15 for the inputs of m=4,n=2, but again fails for m=4,n=3, which is 35.

What am I missing?

Best Answer

  • Assuming the order of the $m$ distinguishable elements is fixed, the function $f$ can be written as $$ f(m,n) = {\small{\binom{m+n}{n}}} = \frac{(m+n)!}{m!{\,\cdot\,}n!} = \frac{\displaystyle{{\prod_{k=0}^{m-1}(m+n-k)}}}{m!} = \frac{\displaystyle{{\prod_{k=0}^{n-1}(m+n-k)}}}{n!} $$ Explanation: Choose the locations of the $n$ indistinguishable "other" elements:$\;{\large{\binom{m+n}{n}}}\;$ choices.

    For example: $f(4,2)={\large{\binom{6}{2}}}=15$, and $f(4,3)={\large{\binom{7}{3}}}=35$.

  • If the order of the $m$ distinguishable elements is allowed to vary, the function $f$ can be written as $$ f(m,n) = {\small{\binom{m+n}{n}}}{\cdot\,}m! = \frac{(m+n)!}{n!} = \prod_{k=0}^{m-1}(m+n-k) $$ Explanation:
    • Choose the locations of the $n$ indistinguishable "other" elements:$\;{\large{\binom{m+n}{n}}}\;$ choices.
    • Choose the order of the $m$ distinguishable elements:$\;m!\;$choices.
Related Question