2
$\begingroup$

I'm trying to work out how many unique combinations (not permutations) there are when some of the elements in the set are indistinguishable. For context, I'm actually considering unique products of combinations of prime factors of a number, which can of course involve duplicate prime numbers.

For example, the set $\{1,1,2,3\}$. To work out the number of combinations of 2 items from this set of 4, I may compute ${4 \choose 2} = 6$. However, because two of the elements of the set are identical, this leaves me with some duplicates. The 6 combinations would be $\{1,1\}$, $\{1,2\}$, $\{1,2\}$, $\{1,3\}$, $\{1,3\}$, $\{2,3\}$. In this simple case, I can see that removing 2 elements will give the correct number of combinations but I'm struggling to see how to generalise this for other more complicated sets with multiple repetitions, and choosing more than 2 elements.

Alternatively, there are 3 unique elements. I could compute ${3 \choose 2} = 3$ and manually add the 1 missing element, $\{1,1\}$. Again, this becomes less trivial when there are many elements and many repetitions and I struggle to see where to start generalising it.

Any pointers would be greatly appreciated!

$\endgroup$
2
  • 2
    $\begingroup$ An approach is to use generating functions. You represent the two $1$s with $(1+x+x^2)$, the one $2$ with $(1+x)$, the one $3$ also with $(1+x)$ and then expand $(1+x+x^2)(1+x)(1+x)$ $=1+3x+4x^2+3x^3+x^4$. So the answer to your example for the number of two-element compositions is the coefficient of $x^2$ which is $4$. Similarly the number of three-element compositions is the coefficient of $x^3$ which is $3$. If it helps, $1+x+\cdots+x^n = \frac{1-x^{n+1}}{1-x}$ so you could have expanded $\left(\frac{1-x^{2+1}}{1-x}\right)^1\left(\frac{1-x^{1+1}}{1-x}\right)^2$ with the same result $\endgroup$
    – Henry
    Commented Oct 30, 2021 at 22:05
  • $\begingroup$ Ooh thank you, that's a really cool idea, I can see how it works in relation to binominal stuff I've learned before $\endgroup$
    – Overtonal
    Commented Oct 31, 2021 at 8:54

1 Answer 1

1
$\begingroup$

Let's say you have to chose $m$ elements and there are $n$ subsets of equal elements. If every subset of equal elements has more or equal elements than $m$ then the formula is simply $(\binom{n}{m})=\binom{n+m-1}{m}$ and the cost of computing it is $O(n+m)$ since you have to compute the factorial of $n+m-1$ and other smaller factorials. This formula doesn't work for the general case, in fact if some sets have less elements than $m$ you can't do it that way, but there's an algorithm that works in $O(nm)$ that solves the general case, and it is based on dynamic programming. The main idea is that if you have let's say a set which is in the form $[a_1,a_1,...,a_1,a_2,a_2,...,a_2,......,a_k,a_k,...,a_k,a_{k+1},a_{k+1},...,a_{k+1}]$ and you have to chose $m$ elements and there are $n$ $a_{k+1}$, let's say you have all the combinations of $0,1,2,3,..,m$ elements for the set $[a_1,a_1,...,a_1,a_2,a_2,...,a_2,......,a_k,a_k,...,a_k]$. Since we can add $0,1,2,...,n$ $a_{k+1}$ to a old combination the resulting combinations with $m$ elements will be the old combinations with $m$ elements plus $0$ $a_{k+1}$, the old combinations with $m-1$ elements plus $1$ $a_{k+1}$, the old combinations with $m-2$ elements plus $2$ $a_{k+1}$ and so on. Since the formal algorithm would be very long to write I'll give an example.

The set is $[1,1,2,2,2,3,4,4,5,5,5]$ and we have to get the number of combinations with $m=5$ elements. We will manage an array of 6 elements representing the number of combinations with 0,1,2,3,4,5 elements at a certain time.

$arr_0=[1,0,0,0,0,0]$ since there is one empty set. Now we have to add the first subset which is made of 2 elements (1,1) so we put $span=2$, that means that the new array will have in each position the current value plus the sum of the 2 previous positions of the current array(the positions behind element 0 are considered 0).

$[1,0,0,0,0,0]-->[(1),0,0,0,0,0]$

$[(1),0,0,0,0,0]-->[1,(1),0,0,0,0]$

$[(1),(0),0,0,0,0]-->[(1,1,(1),0,0,0]$

$[1,(0),(0),0,0,0]-->[(1,1,1,(0),0,0]$

$[1,0,(0),(0),0,0]-->[(1,1,1,0,(0),0]$

$[1,0,0,(0),(0),0]-->[(1,1,1,0,0,(0)]$

$arr_1=[1,1,1,0,0,0]$. Now we add the second subset which is made of 3 elements (2,2,2) so we put $span=3$.

$[1,1,1,0,0,0]-->[(1),1,1,0,0,0]$

$[(1),1,1,0,0,0]-->[1,(2),1,0,0,0]$

$[(1),(1),1,0,0,0]-->[1,2,(3),0,0,0]$

$[(1),(1),(1),0,0,0]-->[1,2,3,(3),0,0]$

$[1,(1),(1),(0),0,0]-->[1,2,3,3,(2),0]$

$[1,1,(1),(0),(0),0]-->[1,2,3,3,2,(1)]$

$arr_2=[1,2,3,3,2,1]$. We add (3), $span=1$.

$arr_3=[1,3,5,6,5,3]$. We add (4,4), $span=2$.

$arr_4=[1,4,9,14,16,14]$. We add (5,5,5), $span=3$.

$arr_5=[1,5,14,28,43,53]$

So 53 is our answer, in order to do less operations instead of sum up the last $span$ elements of the old array we can just sum the previous element of the new array and subtract the element $span +1$ positions behind so that the cost of the algorithm is $O(nm)$ as mentioned before.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .