Combinatoric interpretation of an equality between sums

We have $g$ green balls and $r$ red balls (all numbered), we wish to pick $r$ balls and, further, we are allowed to place a mark on the selected green balls. Let $C$ count the ways of doing this.

Letting $k$ be the number of picked green balls, we have $$ C=\sum_{k=0}^{g}{r \choose r-k}{g \choose k}2^{k}=\sum_{k=0}^{g}{g \choose k}{r \choose k}2^{k}$$ which is the RHS of the original eq ($g \leftrightarrow m$, $r \leftrightarrow n$).

Also, letting $j$ be the number of green balls that were not marked (picked or not):

$$C=\sum_{j=0}^{g}{g \choose g-j}{r + j \choose r-(g-j)}=\sum_{j=0}^{g}{g \choose j}{r + j \choose g}$$

where the first factor counts the marked green balls, and the other the rest.

Tags:

Combinatorics

Combinatorial Proofs

Related

For non-negative reals $a$, $b$, $c$, show that $3(1-a+a^2)(1-b+b^2)(1-c+c^2)\ge(1+abc+a^2b^2c^2)$ Can $S^k$ be embedded in $S^n$ for all $k>n$? Hilbert System Logical Axiom 1 follows from Axioms 2 and 3 How to know if a 8 puzzle is solvable Can I solve this other than using Newton's sums or Newton's identities? Evaluate $\sum_{r=1}^{\infty} \frac{1 \cdot 3 \cdot \ldots (2r-1)}{r!}\left(\frac{2}{5} \right)^{r}$ Are Disjoint Open Subsets Contained in Disjoint Open Sets in a General Topological Space? Proximal Operator of $ f \left( x \right) = {\left\| A x \right\|}_{2} $ Where $ A $ Is Diagonal Matrix (Weighted $ {L}_{2} $ Norm) Example of cw complexes quasi isomorphic but not homotopic. The closed form for $\sum_{n=1}^\infty \frac{H_{n/2}}{n^2}x^n$ any real number between $0$ and $1$ is expressible as an (infinite) sum of particular fractions Is the number of primes equal to the number of integers?

Recent Posts