Number of combinations of two numbers from a list with repeating numbers? [duplicate]

Question

I've tried googling it and looking it up on this website but since I don't know the technical term for this calculation I ran out of luck. Basically, if I have a collection of numbers (each of which may have duplicates) how many unique combinations of $n$ numbers can I make by picking from that collection?

(This question addresses the same issue)

For example:

$C = \{ 1, 2, 2, 3, 3, 3 \}$ and I want to know how many combinations of $2$ numbers I can make.

Glancing over the collection, I can quickly see I can only make the following pairs:

$P = \{ (1,2),(1,3),(2,2),(2,3),(3,3) \}$

Which gives me the answer $|P|=5$.

But if I want to find the number of combinations of $4$ numbers, I can't just enumerate all the possible $4$-tuples because there's no way to make $(1,1,1,1)$ or $(1,2,2,2)$, for example.

Is there a way to calculate this in general using combinatorics?

Answer 1

Let's reduce the question to something I am sure you will be able to solve:

We will use the following notation:

$n$ will denote the number of different numbers (we assume the numbers are precisely $1,...,n$).

$a_k$ is the number of copies of the number $k$.

$s$ is the length of the tuples.

Let us for a second assume we have no restrictions, in this case, we have $n$ choices for each element, we need to choose $s$ in total and divide by the internal orderings: $$\frac{n^s}{s!}$$ However we counted illeagal combinations! so let us remove the ones in which we took at least $a_k + 1$ copies of the number $k$ for each $k\in[n]$, we need to choose where we put the $a_k+1$ copies, for that there are ${s\choose a_k+1}$ options, and we multiply by the ways to choose wats left. from those we have $$\sum_{1\leq k \leq n}{\frac{n^{s-a_k-1}}{(s-a_k-1)!}\cdot {s\choose a_k+1}}$$

Remember we need to remove those from the total: $$\frac{n^s}{s!} - \sum_{1\leq k \leq n}{\frac{n^{s-a_k-1}}{(s-a_k-1)!}\cdot {s\choose a_k+1}}$$

But wait! what if we exceeded the limit in more than one of the variables? We double count that... For this type of problems, we have the inclusion-exclusion formula with the events being $A_k$ means we exceeded the amount with the number $k$

$$\sum_{I \subseteq \{1,...,n\}}(-1)^{\vert I\vert}\cdot{\frac{n^{s-\sum _{k\in I}(a_k+1)}}{(s-\sum _{k\in I}(a_k+1))!}\cdot {s\choose \sum _{k\in I}(a_k+1)}}$$

With no more assumptions on the set of restrictions, I doubt the existence of an explicit formula, however, asymptotic can be calculated by assessing the first few terms.