Counting k-combinations excluding duplicate mathematically

Let's say I have a multiset of integers a with a size n (here n = 10)

$$a = \{1, 1, 2, 2, 3, 4, 5, 6, 6, 10\}$$

I'd like to know the count of k-combinations I can obtain with a provided k value and excluding the duplicate combinations

From the dedicated article I know the formula to count those including duplicates is $\frac{n!}{k! (n - k)!}$, but I found no mention of a possible way to get a count while excluding them anywhere. Is there only a mathematical formula allowing to calculate it, or is the only solution to rely on some algorithm?

Solution 1:

Possible strategies

As discussed in Number of k-combinations of a multiset, your problem of counting $k$-combinations $\mathcal C_k$ of some multiset $\{a_1^{(r_i)},a_2^{(r_i)},\dots,a_n^{(r_i)}\}$ where $(r_i)$ counts how many elements of kind $a_i$ are in there, is equivalent to counting the number of integer solutions to the equation

$$ x_1+x_2+x_3+\dots+x_n=k, 0\le x_i\le r_i, $$

where $x_i$ represents the number of times the element of $a_i$ kind was used in a combination.

Note that if $k=0,1$ then the answer is simply $1,n$. Otherwise, this problem does not have a closed form solution, but there are still different ways to solve it.

See answers given to extended stars-and-bars problem(where the upper limit of the variable is bounded). As demonstrated there, you can use for example the Inclusion–exclusion principle or look at coefficients of corresponding polynomial.

Applying possible strategies to your example

In the case of your example: $$\{1^{(2)},2^{(2)},3^{(1)},4^{(1)},5^{(1)},6^{(2)},10^{(1)}\}\implies n=7,$$ I will try out both mentioned answers to the previously linked question.

$$\text{I}.$$ We can for example use the Inclusion–exclusion principle: (see an answer from the linked post)

$$\begin{align} \mathcal C_k = \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{k+n-1-\sum_{i\in S}(r_i+1)}{n-1} \end{align}$$

Which is for corresponding $k$ expanded and simplified as:

$$\begin{align} \cal C_{2} = C_{8} &= \binom{8}{6} - 4\cdot\binom{6}{6} &= 24 \\ \cal C_{3} = C_{7} &= \binom{9}{6} - \left(3\cdot\binom{6}{6}+4\cdot\binom{7}{6}\right) &= 53 \\ \cal C_{4} = C_{6} &= \binom{10}{6} - \left(3\cdot\binom{7}{6}+4\cdot\binom{8}{6}\right) + 6\cdot\binom{6}{6} &= 83 \\ \cal C_{5} = C_{5} &= \binom{11}{6} - \left(3\cdot\binom{8}{6}+4\cdot\binom{9}{6}\right) + \left(12\cdot\binom{6}{6}+6\cdot\binom{7}{6}\right) &= 96 \\ \end{align}$$

Note that if total number of elements is $m$, then $\cal C_i = C_{m-i}$, which is $m=10$ in your example.

$$\text{II}.$$Alternatively, if you don't want to use Inclusion–exclusion principle, you can look at the coefficients of (see the other answer from the linked post):

$$ P(x) = \prod_{i=1}^n (1-x^{(r_i+1)}) = \sum_ic_ix^{e_i} $$

Then your answer becomes:

$$ {\cal{C}}_k = \sum_{i=0}^kc_i\binom{k-e_i+n-1}{n-1} $$

In the case of your example, the polynomial I got is:

$$P(x) = -x^{17}+\dots+18 x^{10}+11 x^9-11 x^8-18 x^7-x^6+12 x^5+6 x^4-3 x^3-4 x^2+1 $$

And when I substitute in the coefficients, I get the exact same equations as in previous method.

$$\text{III}.$$ Sometimes if your multiset is simple enough, you can use tricks or counting principles to get a result without needing to rely on things like previous two methods. Or if your multiset is of special kind, then there are nicer formulas. For example, if all $r_i$ are equal or if all $r_i$ are $\infty$.

If you want to explore such examples, you can search questions tagged [multisets] [combinations].

For example, the accepted answer to Unable to think about 10-combinations of a multiset is able to reduce the problem to a "Stars and bars" problem which does have a closed formula. The other answer there is also nice because it solves it graphically.

Remark

In case you wanted, you can easily print out every of those combinations for every $k$ with python.

from sympy.utilities.iterables import multiset_combinations

M = {1:2, 2:2, 3:1, 4:1, 5:1, 6:2, 10:1}

for k in range(sum(M.values())+1):  
    print(k)
    for i,m in enumerate(multiset_combinations(M,k)):
        print(i+1,m)

The code gives the expected results for your example:

0
1 []
1
1 [1]
2 [2]
3 [3]
4 [4]
5 [5]
6 [6]
7 [10]
2
1 [1, 1]
2 [1, 2]
3 [1, 3]
4 [1, 4]
5 [1, 5]
6 [1, 6]
7 [1, 10]
8 [2, 2]
9 [2, 3]
10 [2, 4]
11 [2, 5]
12 [2, 6]
13 [2, 10]
14 [3, 4]
15 [3, 5]
16 [3, 6]
17 [3, 10]
18 [4, 5]
19 [4, 6]
20 [4, 10]
21 [5, 6]
22 [5, 10]
23 [6, 6]
24 [6, 10]
3
1 [1, 1, 2]
2 [1, 1, 3]
3 [1, 1, 4]
4 [1, 1, 5]
5 [1, 1, 6]
6 [1, 1, 10]
7 [1, 2, 2]
8 [1, 2, 3]
9 [1, 2, 4]
10 [1, 2, 5]
11 [1, 2, 6]
12 [1, 2, 10]
13 [1, 3, 4]
14 [1, 3, 5]
15 [1, 3, 6]
16 [1, 3, 10]
17 [1, 4, 5]
18 [1, 4, 6]
19 [1, 4, 10]
20 [1, 5, 6]
21 [1, 5, 10]
22 [1, 6, 6]
23 [1, 6, 10]
24 [2, 2, 3]
25 [2, 2, 4]
26 [2, 2, 5]
27 [2, 2, 6]
28 [2, 2, 10]
29 [2, 3, 4]
30 [2, 3, 5]
31 [2, 3, 6]
32 [2, 3, 10]
33 [2, 4, 5]
34 [2, 4, 6]
35 [2, 4, 10]
36 [2, 5, 6]
37 [2, 5, 10]
38 [2, 6, 6]
39 [2, 6, 10]
40 [3, 4, 5]
41 [3, 4, 6]
42 [3, 4, 10]
43 [3, 5, 6]
44 [3, 5, 10]
45 [3, 6, 6]
46 [3, 6, 10]
47 [4, 5, 6]
48 [4, 5, 10]
49 [4, 6, 6]
50 [4, 6, 10]
51 [5, 6, 6]
52 [5, 6, 10]
53 [6, 6, 10]
4
1 [1, 1, 2, 2]
2 [1, 1, 2, 3]
3 [1, 1, 2, 4]
4 [1, 1, 2, 5]
5 [1, 1, 2, 6]
6 [1, 1, 2, 10]
7 [1, 1, 3, 4]
8 [1, 1, 3, 5]
9 [1, 1, 3, 6]
10 [1, 1, 3, 10]
11 [1, 1, 4, 5]
12 [1, 1, 4, 6]
13 [1, 1, 4, 10]
14 [1, 1, 5, 6]
15 [1, 1, 5, 10]
16 [1, 1, 6, 6]
17 [1, 1, 6, 10]
18 [1, 2, 2, 3]
19 [1, 2, 2, 4]
20 [1, 2, 2, 5]
21 [1, 2, 2, 6]
22 [1, 2, 2, 10]
23 [1, 2, 3, 4]
24 [1, 2, 3, 5]
25 [1, 2, 3, 6]
26 [1, 2, 3, 10]
27 [1, 2, 4, 5]
28 [1, 2, 4, 6]
29 [1, 2, 4, 10]
30 [1, 2, 5, 6]
31 [1, 2, 5, 10]
32 [1, 2, 6, 6]
33 [1, 2, 6, 10]
34 [1, 3, 4, 5]
35 [1, 3, 4, 6]
36 [1, 3, 4, 10]
37 [1, 3, 5, 6]
38 [1, 3, 5, 10]
39 [1, 3, 6, 6]
40 [1, 3, 6, 10]
41 [1, 4, 5, 6]
42 [1, 4, 5, 10]
43 [1, 4, 6, 6]
44 [1, 4, 6, 10]
45 [1, 5, 6, 6]
46 [1, 5, 6, 10]
47 [1, 6, 6, 10]
48 [2, 2, 3, 4]
49 [2, 2, 3, 5]
50 [2, 2, 3, 6]
51 [2, 2, 3, 10]
52 [2, 2, 4, 5]
53 [2, 2, 4, 6]
54 [2, 2, 4, 10]
55 [2, 2, 5, 6]
56 [2, 2, 5, 10]
57 [2, 2, 6, 6]
58 [2, 2, 6, 10]
59 [2, 3, 4, 5]
60 [2, 3, 4, 6]
61 [2, 3, 4, 10]
62 [2, 3, 5, 6]
63 [2, 3, 5, 10]
64 [2, 3, 6, 6]
65 [2, 3, 6, 10]
66 [2, 4, 5, 6]
67 [2, 4, 5, 10]
68 [2, 4, 6, 6]
69 [2, 4, 6, 10]
70 [2, 5, 6, 6]
71 [2, 5, 6, 10]
72 [2, 6, 6, 10]
73 [3, 4, 5, 6]
74 [3, 4, 5, 10]
75 [3, 4, 6, 6]
76 [3, 4, 6, 10]
77 [3, 5, 6, 6]
78 [3, 5, 6, 10]
79 [3, 6, 6, 10]
80 [4, 5, 6, 6]
81 [4, 5, 6, 10]
82 [4, 6, 6, 10]
83 [5, 6, 6, 10]
5
1 [1, 1, 2, 2, 3]
2 [1, 1, 2, 2, 4]
3 [1, 1, 2, 2, 5]
4 [1, 1, 2, 2, 6]
5 [1, 1, 2, 2, 10]
6 [1, 1, 2, 3, 4]
7 [1, 1, 2, 3, 5]
8 [1, 1, 2, 3, 6]
9 [1, 1, 2, 3, 10]
10 [1, 1, 2, 4, 5]
11 [1, 1, 2, 4, 6]
12 [1, 1, 2, 4, 10]
13 [1, 1, 2, 5, 6]
14 [1, 1, 2, 5, 10]
15 [1, 1, 2, 6, 6]
16 [1, 1, 2, 6, 10]
17 [1, 1, 3, 4, 5]
18 [1, 1, 3, 4, 6]
19 [1, 1, 3, 4, 10]
20 [1, 1, 3, 5, 6]
21 [1, 1, 3, 5, 10]
22 [1, 1, 3, 6, 6]
23 [1, 1, 3, 6, 10]
24 [1, 1, 4, 5, 6]
25 [1, 1, 4, 5, 10]
26 [1, 1, 4, 6, 6]
27 [1, 1, 4, 6, 10]
28 [1, 1, 5, 6, 6]
29 [1, 1, 5, 6, 10]
30 [1, 1, 6, 6, 10]
31 [1, 2, 2, 3, 4]
32 [1, 2, 2, 3, 5]
33 [1, 2, 2, 3, 6]
34 [1, 2, 2, 3, 10]
35 [1, 2, 2, 4, 5]
36 [1, 2, 2, 4, 6]
37 [1, 2, 2, 4, 10]
38 [1, 2, 2, 5, 6]
39 [1, 2, 2, 5, 10]
40 [1, 2, 2, 6, 6]
41 [1, 2, 2, 6, 10]
42 [1, 2, 3, 4, 5]
43 [1, 2, 3, 4, 6]
44 [1, 2, 3, 4, 10]
45 [1, 2, 3, 5, 6]
46 [1, 2, 3, 5, 10]
47 [1, 2, 3, 6, 6]
48 [1, 2, 3, 6, 10]
49 [1, 2, 4, 5, 6]
50 [1, 2, 4, 5, 10]
51 [1, 2, 4, 6, 6]
52 [1, 2, 4, 6, 10]
53 [1, 2, 5, 6, 6]
54 [1, 2, 5, 6, 10]
55 [1, 2, 6, 6, 10]
56 [1, 3, 4, 5, 6]
57 [1, 3, 4, 5, 10]
58 [1, 3, 4, 6, 6]
59 [1, 3, 4, 6, 10]
60 [1, 3, 5, 6, 6]
61 [1, 3, 5, 6, 10]
62 [1, 3, 6, 6, 10]
63 [1, 4, 5, 6, 6]
64 [1, 4, 5, 6, 10]
65 [1, 4, 6, 6, 10]
66 [1, 5, 6, 6, 10]
67 [2, 2, 3, 4, 5]
68 [2, 2, 3, 4, 6]
69 [2, 2, 3, 4, 10]
70 [2, 2, 3, 5, 6]
71 [2, 2, 3, 5, 10]
72 [2, 2, 3, 6, 6]
73 [2, 2, 3, 6, 10]
74 [2, 2, 4, 5, 6]
75 [2, 2, 4, 5, 10]
76 [2, 2, 4, 6, 6]
77 [2, 2, 4, 6, 10]
78 [2, 2, 5, 6, 6]
79 [2, 2, 5, 6, 10]
80 [2, 2, 6, 6, 10]
81 [2, 3, 4, 5, 6]
82 [2, 3, 4, 5, 10]
83 [2, 3, 4, 6, 6]
84 [2, 3, 4, 6, 10]
85 [2, 3, 5, 6, 6]
86 [2, 3, 5, 6, 10]
87 [2, 3, 6, 6, 10]
88 [2, 4, 5, 6, 6]
89 [2, 4, 5, 6, 10]
90 [2, 4, 6, 6, 10]
91 [2, 5, 6, 6, 10]
92 [3, 4, 5, 6, 6]
93 [3, 4, 5, 6, 10]
94 [3, 4, 6, 6, 10]
95 [3, 5, 6, 6, 10]
96 [4, 5, 6, 6, 10]
6
1 [1, 1, 2, 2, 3, 4]
2 [1, 1, 2, 2, 3, 5]
3 [1, 1, 2, 2, 3, 6]
4 [1, 1, 2, 2, 3, 10]
5 [1, 1, 2, 2, 4, 5]
6 [1, 1, 2, 2, 4, 6]
7 [1, 1, 2, 2, 4, 10]
8 [1, 1, 2, 2, 5, 6]
9 [1, 1, 2, 2, 5, 10]
10 [1, 1, 2, 2, 6, 6]
11 [1, 1, 2, 2, 6, 10]
12 [1, 1, 2, 3, 4, 5]
13 [1, 1, 2, 3, 4, 6]
14 [1, 1, 2, 3, 4, 10]
15 [1, 1, 2, 3, 5, 6]
16 [1, 1, 2, 3, 5, 10]
17 [1, 1, 2, 3, 6, 6]
18 [1, 1, 2, 3, 6, 10]
19 [1, 1, 2, 4, 5, 6]
20 [1, 1, 2, 4, 5, 10]
21 [1, 1, 2, 4, 6, 6]
22 [1, 1, 2, 4, 6, 10]
23 [1, 1, 2, 5, 6, 6]
24 [1, 1, 2, 5, 6, 10]
25 [1, 1, 2, 6, 6, 10]
26 [1, 1, 3, 4, 5, 6]
27 [1, 1, 3, 4, 5, 10]
28 [1, 1, 3, 4, 6, 6]
29 [1, 1, 3, 4, 6, 10]
30 [1, 1, 3, 5, 6, 6]
31 [1, 1, 3, 5, 6, 10]
32 [1, 1, 3, 6, 6, 10]
33 [1, 1, 4, 5, 6, 6]
34 [1, 1, 4, 5, 6, 10]
35 [1, 1, 4, 6, 6, 10]
36 [1, 1, 5, 6, 6, 10]
37 [1, 2, 2, 3, 4, 5]
38 [1, 2, 2, 3, 4, 6]
39 [1, 2, 2, 3, 4, 10]
40 [1, 2, 2, 3, 5, 6]
41 [1, 2, 2, 3, 5, 10]
42 [1, 2, 2, 3, 6, 6]
43 [1, 2, 2, 3, 6, 10]
44 [1, 2, 2, 4, 5, 6]
45 [1, 2, 2, 4, 5, 10]
46 [1, 2, 2, 4, 6, 6]
47 [1, 2, 2, 4, 6, 10]
48 [1, 2, 2, 5, 6, 6]
49 [1, 2, 2, 5, 6, 10]
50 [1, 2, 2, 6, 6, 10]
51 [1, 2, 3, 4, 5, 6]
52 [1, 2, 3, 4, 5, 10]
53 [1, 2, 3, 4, 6, 6]
54 [1, 2, 3, 4, 6, 10]
55 [1, 2, 3, 5, 6, 6]
56 [1, 2, 3, 5, 6, 10]
57 [1, 2, 3, 6, 6, 10]
58 [1, 2, 4, 5, 6, 6]
59 [1, 2, 4, 5, 6, 10]
60 [1, 2, 4, 6, 6, 10]
61 [1, 2, 5, 6, 6, 10]
62 [1, 3, 4, 5, 6, 6]
63 [1, 3, 4, 5, 6, 10]
64 [1, 3, 4, 6, 6, 10]
65 [1, 3, 5, 6, 6, 10]
66 [1, 4, 5, 6, 6, 10]
67 [2, 2, 3, 4, 5, 6]
68 [2, 2, 3, 4, 5, 10]
69 [2, 2, 3, 4, 6, 6]
70 [2, 2, 3, 4, 6, 10]
71 [2, 2, 3, 5, 6, 6]
72 [2, 2, 3, 5, 6, 10]
73 [2, 2, 3, 6, 6, 10]
74 [2, 2, 4, 5, 6, 6]
75 [2, 2, 4, 5, 6, 10]
76 [2, 2, 4, 6, 6, 10]
77 [2, 2, 5, 6, 6, 10]
78 [2, 3, 4, 5, 6, 6]
79 [2, 3, 4, 5, 6, 10]
80 [2, 3, 4, 6, 6, 10]
81 [2, 3, 5, 6, 6, 10]
82 [2, 4, 5, 6, 6, 10]
83 [3, 4, 5, 6, 6, 10]
7
1 [1, 1, 2, 2, 3, 4, 5]
2 [1, 1, 2, 2, 3, 4, 6]
3 [1, 1, 2, 2, 3, 4, 10]
4 [1, 1, 2, 2, 3, 5, 6]
5 [1, 1, 2, 2, 3, 5, 10]
6 [1, 1, 2, 2, 3, 6, 6]
7 [1, 1, 2, 2, 3, 6, 10]
8 [1, 1, 2, 2, 4, 5, 6]
9 [1, 1, 2, 2, 4, 5, 10]
10 [1, 1, 2, 2, 4, 6, 6]
11 [1, 1, 2, 2, 4, 6, 10]
12 [1, 1, 2, 2, 5, 6, 6]
13 [1, 1, 2, 2, 5, 6, 10]
14 [1, 1, 2, 2, 6, 6, 10]
15 [1, 1, 2, 3, 4, 5, 6]
16 [1, 1, 2, 3, 4, 5, 10]
17 [1, 1, 2, 3, 4, 6, 6]
18 [1, 1, 2, 3, 4, 6, 10]
19 [1, 1, 2, 3, 5, 6, 6]
20 [1, 1, 2, 3, 5, 6, 10]
21 [1, 1, 2, 3, 6, 6, 10]
22 [1, 1, 2, 4, 5, 6, 6]
23 [1, 1, 2, 4, 5, 6, 10]
24 [1, 1, 2, 4, 6, 6, 10]
25 [1, 1, 2, 5, 6, 6, 10]
26 [1, 1, 3, 4, 5, 6, 6]
27 [1, 1, 3, 4, 5, 6, 10]
28 [1, 1, 3, 4, 6, 6, 10]
29 [1, 1, 3, 5, 6, 6, 10]
30 [1, 1, 4, 5, 6, 6, 10]
31 [1, 2, 2, 3, 4, 5, 6]
32 [1, 2, 2, 3, 4, 5, 10]
33 [1, 2, 2, 3, 4, 6, 6]
34 [1, 2, 2, 3, 4, 6, 10]
35 [1, 2, 2, 3, 5, 6, 6]
36 [1, 2, 2, 3, 5, 6, 10]
37 [1, 2, 2, 3, 6, 6, 10]
38 [1, 2, 2, 4, 5, 6, 6]
39 [1, 2, 2, 4, 5, 6, 10]
40 [1, 2, 2, 4, 6, 6, 10]
41 [1, 2, 2, 5, 6, 6, 10]
42 [1, 2, 3, 4, 5, 6, 6]
43 [1, 2, 3, 4, 5, 6, 10]
44 [1, 2, 3, 4, 6, 6, 10]
45 [1, 2, 3, 5, 6, 6, 10]
46 [1, 2, 4, 5, 6, 6, 10]
47 [1, 3, 4, 5, 6, 6, 10]
48 [2, 2, 3, 4, 5, 6, 6]
49 [2, 2, 3, 4, 5, 6, 10]
50 [2, 2, 3, 4, 6, 6, 10]
51 [2, 2, 3, 5, 6, 6, 10]
52 [2, 2, 4, 5, 6, 6, 10]
53 [2, 3, 4, 5, 6, 6, 10]
8
1 [1, 1, 2, 2, 3, 4, 5, 6]
2 [1, 1, 2, 2, 3, 4, 5, 10]
3 [1, 1, 2, 2, 3, 4, 6, 6]
4 [1, 1, 2, 2, 3, 4, 6, 10]
5 [1, 1, 2, 2, 3, 5, 6, 6]
6 [1, 1, 2, 2, 3, 5, 6, 10]
7 [1, 1, 2, 2, 3, 6, 6, 10]
8 [1, 1, 2, 2, 4, 5, 6, 6]
9 [1, 1, 2, 2, 4, 5, 6, 10]
10 [1, 1, 2, 2, 4, 6, 6, 10]
11 [1, 1, 2, 2, 5, 6, 6, 10]
12 [1, 1, 2, 3, 4, 5, 6, 6]
13 [1, 1, 2, 3, 4, 5, 6, 10]
14 [1, 1, 2, 3, 4, 6, 6, 10]
15 [1, 1, 2, 3, 5, 6, 6, 10]
16 [1, 1, 2, 4, 5, 6, 6, 10]
17 [1, 1, 3, 4, 5, 6, 6, 10]
18 [1, 2, 2, 3, 4, 5, 6, 6]
19 [1, 2, 2, 3, 4, 5, 6, 10]
20 [1, 2, 2, 3, 4, 6, 6, 10]
21 [1, 2, 2, 3, 5, 6, 6, 10]
22 [1, 2, 2, 4, 5, 6, 6, 10]
23 [1, 2, 3, 4, 5, 6, 6, 10]
24 [2, 2, 3, 4, 5, 6, 6, 10]
9
1 [1, 1, 2, 2, 3, 4, 5, 6, 6]
2 [1, 1, 2, 2, 3, 4, 5, 6, 10]
3 [1, 1, 2, 2, 3, 4, 6, 6, 10]
4 [1, 1, 2, 2, 3, 5, 6, 6, 10]
5 [1, 1, 2, 2, 4, 5, 6, 6, 10]
6 [1, 1, 2, 3, 4, 5, 6, 6, 10]
7 [1, 2, 2, 3, 4, 5, 6, 6, 10]
10
1 [1, 1, 2, 2, 3, 4, 5, 6, 6, 10]