Post History
#7: Post edited
by
clemens
·
2026-02-24T14:51:12Z (7 months ago)
added further explanation for the formula (and corrected it, per Dylan Callaghan's comments)
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question, giving us the number of ways to collect balls of at most $n_1$ different colors in the first $n_2$ draws without replacement, from a set of colored and black balls.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} -1^{n_1-|K|} {n-|K| \choose n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
- The number of times a given set $K$ needs to be included in our summation is equal to the number of maximal color-sets that includes it, which is ${n \choose n_1-|K|}$ because we are able to pick $n_1-|K|$ (out of the $n_1-|K|$ colors not in $K$) to adjoin to $K$ to get a maximal color-set. (Basically, we sum up the IEP-based formulæ for each maximal color-set $K$. This works as follows (we can ignore the $(m)_{n_2}$ denominator because it's the same in every term of our summation):)
\[\text{\# of seqs. of $n_2$ balls using exactly the colors in $K$} = \sum_{S \subseteq K} -1^{|K|-|S|} (|S|)_{n_2}\]\[\text{\# of seqs. of $n_2$ balls using exactly $n_1$ colors} = \sum_{|K| = n_1}\sum_{S \subseteq K} -1^{n_1-|S|} (|S|)_{n_2}\]- And hence, collecting the terms in the inner summation, we get (as desired):
\[\sum_{|S| ≤ n_1} -1^{n_1-|S|} {n-|S| \choose n_1-|S|} (|S|)_{n_2}\]
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question, giving us the number of ways to collect balls of at most $n_1$ different colors in the first $n_2$ draws without replacement, from a set of colored and black balls.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} -1^{n_1-|K|} {n-|K| \choose n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
- The number of times a given set $K$ needs to be included in our summation is equal to the number of maximal color-sets that includes it, which is ${n \choose n_1-|K|}$ because we are able to pick $n_1-|K|$ (out of the $n_1-|K|$ colors not in $K$) to adjoin to $K$ to get a maximal color-set. (Basically, we sum up the IEP-based formulæ for each maximal color-set $K$. This works as follows (we can ignore the $(m)_{n_2}$ denominator because it's the same in every term of our summation):)
- \[\text{\# of seqs. of $n_2$ balls using exactly the colors in $S$} = \sum_{K \subseteq S} -1^{|S|-|K|} (|\bigcup K|)_{n_2}\]
- \[\text{\# of seqs. of $n_2$ balls using exactly $n_1$ colors} = \sum_{|S| = n_1}\sum_{K \subseteq S} -1^{n_1-|K|} (|\bigcup K|)_{n_2}\]
- And hence, collecting the terms in the inner summation, we get (as desired):
- \[\sum_{|K| ≤ n_1} -1^{n_1-|K|} {n-|K| \choose n_1-|K|} \left(|\bigcup K|\right)_{n_2}\]
#6: Post edited
by
clemens
·
2026-02-24T14:48:46Z (7 months ago)
added further explanation for the formula (and corrected it, per Dylan Callaghan's comments)
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question, giving us the number of ways to collect balls of at most $n_1$ different colors in the first $n_2$ draws without replacement, from a set of colored and black balls.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
\[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} -1^{n_1-|K|} {n \choose n_1-K} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
The number of times a given set $K$ needs to be included in our summation is equal to the number of maximal color-sets that includes it, which is ${n \choose n_1-|K|}$ because we are able to pick $n_1-|K|$ out of $n$ colors to adjoin to $K$ to get a maximal color-set. (Basically, we sum up the IEP-based formulæ for each maximal color-set $K$.)
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question, giving us the number of ways to collect balls of at most $n_1$ different colors in the first $n_2$ draws without replacement, from a set of colored and black balls.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} -1^{n_1-|K|} {n-|K| \choose n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
- The number of times a given set $K$ needs to be included in our summation is equal to the number of maximal color-sets that includes it, which is ${n \choose n_1-|K|}$ because we are able to pick $n_1-|K|$ (out of the $n_1-|K|$ colors not in $K$) to adjoin to $K$ to get a maximal color-set. (Basically, we sum up the IEP-based formulæ for each maximal color-set $K$. This works as follows (we can ignore the $(m)_{n_2}$ denominator because it's the same in every term of our summation):)
- \[\text{\# of seqs. of $n_2$ balls using exactly the colors in $K$} = \sum_{S \subseteq K} -1^{|K|-|S|} (|S|)_{n_2}\]
- \[\text{\# of seqs. of $n_2$ balls using exactly $n_1$ colors} = \sum_{|K| = n_1}\sum_{S \subseteq K} -1^{n_1-|S|} (|S|)_{n_2}\]
- And hence, collecting the terms in the inner summation, we get (as desired):
- \[\sum_{|S| ≤ n_1} -1^{n_1-|S|} {n-|S| \choose n_1-|S|} (|S|)_{n_2}\]
#5: Post edited
by
clemens
·
2026-02-23T14:40:09Z (7 months ago)
corrected the formula and added explanation
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question, giving us the number of ways to collect balls of at most $n_1$ different colors in the first $n_2$ draws without replacement, from a set of colored and black balls.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
\[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question, giving us the number of ways to collect balls of at most $n_1$ different colors in the first $n_2$ draws without replacement, from a set of colored and black balls.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} -1^{n_1-|K|} {n \choose n_1-K} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
- The number of times a given set $K$ needs to be included in our summation is equal to the number of maximal color-sets that includes it, which is ${n \choose n_1-|K|}$ because we are able to pick $n_1-|K|$ out of $n$ colors to adjoin to $K$ to get a maximal color-set. (Basically, we sum up the IEP-based formulæ for each maximal color-set $K$.)
#4: Post edited
by
clemens
·
2026-02-20T13:14:27Z (7 months ago)
added information on what variant of the question this answer answers
I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question.- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question, giving us the number of ways to collect balls of at most $n_1$ different colors in the first $n_2$ draws without replacement, from a set of colored and black balls.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
#3: Post edited
by
clemens
·
2026-02-20T00:38:48Z (7 months ago)
Added a formula at end to help users understand what I am doing
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (unary intersections) are positive, those where $|K| = n_1-1$ (binary intersections) are negative, those where $|K| = n_1-2$ (ternary intersections) are positive, etc. The idea is fundamentally the same as the formula for derangements.
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (corresponding to unary intersections) are positive, those where $|K| = n_1-1$ (corresponding to binary intersections) are negative, those where $|K| = n_1-2$ (corresponding to ternary intersections) are positive, etc. The idea is analogous to the formula $\sum_{i=0}^n -1^i {n \choose i}$ for derangements and to the more general formula $\sum_{i=k}^n -1^{i-k} {n \choose i}$ for permutations that keep exactly $k$ elements fixed.
#2: Post edited
by
clemens
·
2026-02-20T00:27:25Z (7 months ago)
changed first paragraph to better reflect the nature of the solution
This is a *suboptimal* answer. It solves the problem (since it's easy to get the expected number of tries required to get $n$ different colors if you know the probabilities of getting $n$ different colors after each try), but not as elegantly and I think maybe not as efficiently as your "partial solutions" above solve their associated problems.- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (unary intersections) are positive, those where $|K| = n_1-1$ (binary intersections) are negative, those where $|K| = n_1-2$ (ternary intersections) are positive, etc. The idea is fundamentally the same as the formula for derangements.
- I must admit to not yet understanding how we get the expected values in your partial answers (1) and (2). But here is a solution to the main question.
- ---
- Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
- \[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
- where $C_i$ is the set of balls of color $i$.
- This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
- In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (unary intersections) are positive, those where $|K| = n_1-1$ (binary intersections) are negative, those where $|K| = n_1-2$ (ternary intersections) are positive, etc. The idea is fundamentally the same as the formula for derangements.
#1: Initial revision
by
clemens
·
2026-02-19T19:42:28Z (7 months ago)
This is a *suboptimal* answer. It solves the problem (since it's easy to get the expected number of tries required to get $n$ different colors if you know the probabilities of getting $n$ different colors after each try), but not as elegantly and I think maybe not as efficiently as your "partial solutions" above solve their associated problems.
---
Along the lines of your partial answer (4), we can use the Inclusion-Exclusion principle to figure out how many $n_2$-ball draws use exactly $n_1$ different colors (excluding black).
\[\sum_{K \subseteq \{C_1,…,C_n\} ∧ 0 < |K| ≤ n_1} (-1)^{n_1-|K|} \frac{(|\bigcup K|)_{n_2}}{(m)_{n_2}}\]
where $C_i$ is the set of balls of color $i$.
This is because, if there are $b$ balls of one type and $m$ balls total, then the chance that, in an $n$-ball draw, all the balls will be of the said type is $\frac{(b)_n}{(m)_n}$, where $(m)_n$ is the falling Pochhammer symbol. The terms being summed then correspond to the probabilities that the first $n_2$ balls drawn will use only the colors within the elements of the set $K \subseteq \{C_1,…C_n\}$.
In accordance with the Inclusion-Exclusion Principle, the terms where $|K| = n_1$ (unary intersections) are positive, those where $|K| = n_1-1$ (binary intersections) are negative, those where $|K| = n_1-2$ (ternary intersections) are positive, etc. The idea is fundamentally the same as the formula for derangements.