TITLE: Calculating the number of combinations in a list expansion
QUESTION [0 upvotes]: 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?

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 0, "question_id": 3347896}