# Questions tagged [combinatorial-proofs]

Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc. They avoid complicated algebraic manipulations.

1,100 questions
Filter by
Sorted by
Tagged with
49 views

### Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$.

Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$. I got this problem from the double counting handout ( ...
• 4,039
49 views

### Find all natural numbers $n$ such that $\binom{n+1}{k}$ is even $\forall~k=1,\dots,n$.

I want to study the parity of $\binom{n}{k}$. I know that there are several ways to do this for a given $n$ and a given $k$, such as Kummer's theorem or Lucas' theorem, which give a method to find the ...
• 1,606
53 views

### ${r + s \choose r + s - n} = \sum_{p,q,p',q'} {r \choose p} {s \choose q}$

I am fixing $m,n,r,s$ such that $m + n = r + s$ from the beginning. I have the following $4$ conditions that should be satisfied : \begin{align*} r &= p + p'\\ s &= q + q'\\ m &...
• 1,339
76 views

### Prove combinatorially that: $\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$

Prove combinatorially that: $$\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$$ I couldn't solve it by myself. it's to complicated ...
• 383
29 views

• 2,192
56 views

126 views

### Probability of runs with cyclical criteria in Bernoulli trials

I am considering an extension of a previously posed problem, for which I have a hand-wave solution. I would like to determine whether the solution is exact and if not, need help with a rigorous ...
34 views

### arranging p numbered balls in n indistinguishable boxes [closed]

let pDn the number of ways to arrange p numbered balls in n indistinguishable boxes such that p is greater than or = n and no box is empty how to calculate pDp-1. (I tried to dissect the problem and I ...
189 views

• 163
89 views

### Prove that $2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$ using double counting. [duplicate]

Using a combinatorial proof (counting the same thing in different ways), show that: $$2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$$ I was thinking of having some set $A$ where $|A| = n$, and then ...
• 79
42 views

### Number of ways to choose $m$ boys and $k$ girls from $n$ boys and $n$ girls?

Suppose there are $n$ boys and $n$ girls and we want to choose $m$ boys and $k$ girls such that $k \le m$. Then there are $\binom{n}{m} \binom{n}{k}$ ways to do it. Now, using counting in two ways, I ...
• 1,243
Let $A$ be a $n \times n$ matrix and suppose we want to colour elements of this matrix using black and white colours. Since each element can be either white or black, so total number of ways are $2^{n^... • 1,243 2 votes 3 answers 91 views ### How to prove the binomial identity$\binom{n + 1}{a + b + 1} = \sum_{k = 0}^n \binom{k}{a}\binom{n - k}{b}\$
Prove the identity: $$\binom{n + 1}{a + b + 1} = \sum_{k = 0}^n \binom{k}{a}\binom{n - k}{b}$$ So far I understand the left side represents how many ways there are picking a+b+1 elements from a set (...