# 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.

983 questions
Filter by
Sorted by
Tagged with
1 vote
19 views

1 vote
39 views

### A combinatorial proof of a binomial coefficient summation identity. [duplicate]

$$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$ This is the exercise 3.3.6 of the book Invitation to Discrete Mathematics. The answer in book is Let M be an m-...
49 views

39 views

42 views

1 vote
47 views

### Ballot problem but the probability that candidate B is ahead of candidate A

Alice and Bob are running for office. Alice receives a votes and Bob receives b votes, where a>b. The votes are counted one at a time. What is the probability that sometime during the counting Bob ...
112 views

### Alternative way of writing the stars and bars formula where each bar is associated with at least one star.

I was looking for a different way of writing the formula of the number of different $k$-tuples of non-negative integers whose sum is equal to $n$ and I thought of this formula followed by this ...
1 vote
I want to prove the identity $\sum_{i=0}^n{n + i \choose i}\frac{1}{2^i} = 2^n$ combinatorially. I tried multiplying both sides of the equation by $2^n$ and obtained $\sum_{i=0}^n{n + 1 \choose i}2^{n ... 1 vote 1 answer 75 views ### prove that$\sum_{k=0}^{n}S(n,k)(x)_k=x^n$my attempt: assume there are a teacher decided to buy$n$different types of chocolate and present it as a reward to the students who will give a correct answer to one of the questions. The number of ... 3 votes 1 answer 98 views ###${ n \choose k}={ n-1 \choose k-1}+{ n-2 \choose k-1}+{ n-3 \choose k-1}+...+{ k-1 \choose k-1}$i tried to prove this by using the concept of composition${ n \choose k}={ n-1 \choose k-1}+{ n-2 \choose k-1}+{ n-3 \choose k-1}+...+{ k-1 \choose k-1}$my attempt: for explain my idea let's take$ ... 