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

learn more… | top users | synonyms

6
votes
5answers
127 views

Verify the following combinatorial identity: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$

$$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$ Nice, so I've proven some combinatorial identities before via induction, other more simple ones by committee selection models.... But ...
2
votes
1answer
77 views

Proof with combinatorial argument

Show with combinatorial argument that this is equal : $$\dbinom{n}{k+1} = \dbinom{n-1}{k}+ \dbinom{n-2}{k} +...+ \dbinom{k}{k}$$ I have no idea how to do that so it would be really helpful ...
0
votes
0answers
13 views

extreme points of a symmetric doubly stochastic polytope

I have a problem with Katz's paper (On the extreme points of a certain convex polytope)... I did not understand the proof of lemma3 on pages 420-421...I have a problem with getting the values of u ...
0
votes
1answer
33 views

Combinatorial Proof: How many length-n lists can we form using the elements in {1,2,3} [PROOF]

I'm trying to prove that $2\times(3^0) + 2\times(3^1) + 2\times(3^2) + \cdots+ 2\times(3^(n-1)) = 3^n - 1$ by answering the question "how many length-n lists can we form using the elements in ...
0
votes
1answer
36 views

combinatorial proof of summation

Prove $\sum_{i=1}^n2^{i-1}=\sum_{i=0}^{n-1}2^i=2^n-1$ combinatorially. This is easy to prove inductively. I know that $\sum_{i=0}^n{n\choose i}=2^n$ so maybe change $\sum_{i=0}^{n-1}2^i$ to ...
0
votes
1answer
14 views

Proving overlap when distributing certain number of balloons to forty children.

Sorry for the title, couldn't think of a better way to phrase it. The problem is this: Forty children go to a carnival. Twenty-five are given a blue balloon, 30 a red balloon, 35 a green, and 33 a ...
1
vote
2answers
79 views

Give a combinatorial proof to show the following for all integers $n \geq 2$.

$$2^{n-2} n (n -1) = \sum\limits_{k=2}^n k (k - 1) \binom{n}{k}.$$ I'm completely stumped. I just have no idea how to do this. What I've tried so far has been simplifying the right hand side slightly ...
0
votes
2answers
32 views

Understanding a combinatorial relation.

I would like some insight as to why the following expression is true. $$\sum_{i=0}^n {{n}\choose{i}} 2^{n-i} = 3^n $$ I arrived at this relation in solving a subset problem, and I understand the ...
0
votes
5answers
58 views

Combinatorial argument for the sum of the first $n$ integers.

Can someone give a combinatorial argument (at least for $\binom{n+1}{2}$) for why $\binom{n+1}{2}=(n^2+n)/2$?
0
votes
1answer
64 views

Prove with combinatorial arguments this equation [duplicate]

Prove with combinatorial arguments, that, $\forall n \in \mathbb{N}$. $$\sum_{k=0}^n (-1)^k {n \choose k} =0$$
1
vote
0answers
67 views

A sum with binomial coefficients in the numerator and denominator.

I am struggling with a combinatorial sum as apart of a long statistical-mechanics derivation. I would appreciate any help. I seek the result of the following summation, for integer $\ell,n$, and ...
0
votes
2answers
59 views

Combinatorial argument $a(n-a)$ $n \choose a $ = $n(n-1)$ $n-2 \choose a-1$

I can not make sense of this; I am looking for a combinatorial argument that would prove the equivalence of this statement. I can prove it with algebraic manipulation. $a(n-a)$ $n \choose a $ = ...
1
vote
3answers
125 views

Prove this combinatorial identity

$${n \choose k}{k \choose 1}{k-1 \choose 1} = n(n-1){n-2 \choose k-2}$$
2
votes
1answer
118 views

Combinatorial proof involving reciprocals

This is a follow-up to this question: show that if $n$ is a positive integer then $$\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k}\binom{n}{k} =\sum_{k=1}^{n}\frac{1}{k}\ .$$ I was able to answer the question by ...
10
votes
3answers
345 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
2
votes
2answers
81 views

Combinatorial proof of $n! = {n\choose k}k!(n-k)!$

Can someone give me some insight on the proof of $$n! = {n\choose k}k!(n-k)!$$ I understand algebraically why they are equal but I'm having trouble seeing what the right side is actually saying. On ...
3
votes
1answer
89 views

Combinatorial proof of $k\binom{n}{k} = n\binom{n-1}{k-1}$ [duplicate]

I'm trying to prove this combinatorially. $$k\binom{n}{k} = n\binom{n-1}{k-1}$$ I know the first step is to relate a question to the equation. My question was if you have $n$ friends how many ways can ...
1
vote
0answers
37 views

Finite sum identity involving Stirling numbers

I was given the following identities (note: $s_{n,k},S_{n,k}$ are the Stirling numbers of first and second kind respectively): (1) $s_{n+1,k+1}=\sum_{i=k}^{n}\binom{i}{k}s_{n,i}$ (2) ...
0
votes
1answer
97 views

Combinatorial proofs - how?

I'm suppose to proof the following with combinatorial proofs. 1)$$\sum_{i=0}^{n} {a+i \choose i} = {a+n+1 \choose n}$$ 2)$$\sum_{i=0}^{n} i{n \choose i} = n2^{n-1}$$ 3)$$\sum_{i=0}^{n} {n \choose ...
2
votes
1answer
46 views

Confirming the correctness of Combinatoric permutation formula

for the ordering and distinguishable non-empty, is it $$ (n)k = n(n-1)(n-2)\cdots(n-k+1) $$ for no ordering distinguishable non-empty, i got $$ \sum_{i=0}^{n-1}(-1)^i\dbinom{n}{i}(n-i)^k $$ please ...
12
votes
3answers
207 views

Prove $1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3}$

Prove that: $$ 1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3} $$ Now, if I simplify the right hand combinatorial expression, it reduces to $\frac{n(n+1)(2n+1)}{6}$ which is well known and can be ...
1
vote
1answer
85 views

The properties of graph and its relation with the largest eigenvalue

When I was solving questions from a graph theory book by Bondy and Murty, I came across this problem: ( Note: $\Delta$ represents the maximum degree. ) Show that: a) no eigenvalue of a graph ...
1
vote
1answer
37 views

Discrete Mathematics Proof odd degree

Show that for a graph letting r be the number of vertices with odd degree( with an odd number of edges) show that r is even. Is that about Euler's criterion or is there any other solution?
2
votes
3answers
96 views

Combinatorial proofs of the identity $(a+b)^2 = a^2 +b^2 +2ab$

The question I have is to give a combinatorial proof of the identity $(a+b)^2 = a^2 +b^2 +2ab$. I understand the concept of combinatorial proofs but am having some trouble getting started with this ...
4
votes
2answers
125 views

Prove that $(n!)^2$ is greater than $n^n$ for all values of n greater than 2. [duplicate]

This problem , I assume can be proved using induction, however I am trying to find another way. Is there a simple combinatorial approach? One notices that $(n!)^2$ is equal to the number of ...
3
votes
1answer
199 views

Combinatorial Proof - $\ {1 \over n+1} {2n\choose n} = {2n-1\choose n-1} - {2n-1\choose n+1} = {2n\choose n} - {2n\choose n-1}$

I'm been struggling with this proof for quite a while now - I'm trying to combinatorially prove this expression: $$ {1 \over n+1} {2n\choose n} = {2n-1\choose n-1} - {2n-1\choose n+1}$$ $$= ...
2
votes
1answer
162 views

Combinatorial Proof -$\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$

I'm reading about combinatorics, specifically 'Cohen's Introduction to Combinatorial Theory', and am stuck on one of the problems. I'm looking for a combinatorial proof for the following : $\ n ...
13
votes
3answers
344 views

Show that $\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
4
votes
1answer
96 views

Combinatorial Identity Proof

What is a combinatorial proof for this identity: $1 \times 1! + 2 \times 2! + ... + n \times n! = (n + 1)! - 1$ I am trying to figure out what are both sides trying to count.
2
votes
2answers
71 views

Using a combinatorial proof [duplicate]

How should I solve this problem? can anyone help? Thanks.
9
votes
1answer
185 views

A congruence in the number of certain ternary strings

Let $a_n$ be the number of ternary strings of length $n$ which do not contain three consecutive symbols that are all different. That is, $$a_n = \Bigl|\bigl\{\,(b_k)_{1\leq k\leq n}\in ...
1
vote
2answers
99 views

Combinatorial proof with binomial coefficients

I need to prove this with combinatorial arguments. I don't know how to start. $$ \sum_{j = r}^{n + r - k}{j - 1 \choose r - 1}{n - j \choose k - r} = {n \choose k}\,, \qquad\qquad 1\ \leq\ r\ \leq\ ...
3
votes
3answers
126 views

Proof of combinatorial identity

I need a edit:combinatorial proof of the following identity: $$1 = \sum_{k=0}^n \binom {n} {n-k}2^{n-k}(-1)^k$$ I know that I should use inclusion-exclusion, but I am getting stuck. Thanks!
1
vote
2answers
90 views

A (combinatorics?) problem about shoes

"30 shoes are arbitrary ordered in a row, 15 left and 15 right shoes. In this row there will always be 10 succeeding shoes such that 5 of theme are left shoes (and 5 of theme are right shoes. Prove ...
4
votes
3answers
838 views

Combinatorial Proof of Multinomial Theorem - Without Induction or Binomial Theorem

I've been trying to rout out an exclusively combinatorial proof of the Multinomial Theorem with bounteous details but only lighted upon this one - see P2. Any other helpful ones? ...
1
vote
4answers
256 views

For all positive integers n,m,k where $n\ge m\ge k$ , $\binom {n}{m}\binom {m}{k}=\binom {n}{k}\binom {n-k}{n-m}$ [duplicate]

For all positive integers n,m,k where $n\ge m\ge k$ , $\binom {n}{m}\binom {m}{k}=\binom {n}{k}\binom {n-k}{n-m}$ Prove the following statements using combinatorial proofs. I can't come up ...
7
votes
2answers
116 views

Seeking a combinatorial proof of the identity$1+3+\cdots+(2n-1)=n^2$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $$1+3+\cdots+(2n-1)=n^2$$
5
votes
1answer
340 views

Combinatorial Proof for Series of Stirling Numbers & Binomial Coefficients

I am struggling with the following question from an assignment for an introductory course to combinatorics. Show, by means of a combinatorial argument, that the following holds: ...
3
votes
2answers
135 views

proofs for combinatorial identities?

by using the identity $(1-x^2)^n=(1+x)^n(1-x)^n$, show that for each $m \in \Bbb N$ with $m < n$, summation of $$\sum_{i=0}^n(-1)^i\binom{n}i^2=\begin{cases} 0,&\text{if }n\text{ is odd}\\ ...
1
vote
2answers
243 views

Probability that number of heads flipped is divisible by 3

You toss a coin n times. What is the probability that the number of heads you’ll get is divisible by 3? (Find an exact formula, not involving sums of unbounded length; it may depend on the remainder ...
7
votes
2answers
120 views

Seeking a combinatorial proof of the identity $1^3+2^3+3^3+\cdots+n^3=\{{}_{n+1}C_{2}\}^2$

I would appreciate if somebody could help me with the following problem Q: show that combinatoric identity (using by combinatorial proof) $$1^3+2^3+3^3+\cdots+n^3=\{{}_{n+1}C_{2}\}^2$$
3
votes
1answer
144 views

Seeking a combinatorial proof of the identity$1 f_1+2 f_2+\cdots+n f_n=n f_{n + 2} - f_{n + 3} + 2$

I would appreciate if somebody could help me with the following problem Q: $f_1=f_2=1, f_{n+2}=f_{n+1}+f_n(n\geq 2)$ Show that combinatoric identity (using by combinatorial proof) $$1 f_1+2 ...
1
vote
1answer
194 views

Stirling numbers combinatorial proof

This is a Homework Question. I am required to give a Combinatorial proof for the following. $$S(m,n)=\frac 1{n!} \sum_{k=0}^{n} (-1)^k\binom nk (n-k)^m$$ Hint given is : Show that $n!S(m,n)$ ...
2
votes
2answers
191 views

Seeking a combinatorial proof of the identity$n+(n-1)2^1+(n-2)2^2+\cdots+ 2\cdot 2^{n-2}+ 1\cdot 2^{n-1}=-n+2^{n+1}-2$

I would appreciate if somebody could help me with the following problem Q: show that combinatoric identity (using by combinatorial proof) $$n+(n-1)2^1+(n-2)2^2+\cdots+ 2\cdot 2^{n-2}+ 1\cdot ...
8
votes
3answers
207 views

A peculiar binomial coefficient identity

While inventing exercises for a discrete math text I'm writing I came up with this $$ \binom{\binom{n}{2}}{2}=3\binom{n+1}{4} $$ It's an easy result to prove, but it got me wondering Is this pure ...
5
votes
4answers
240 views

Combinatorial Proof

I have trouble coming up with combinatorial proofs. How would you justify this equality? $$ n\binom {n-1}{k-1} = k \binom nk $$
2
votes
1answer
293 views

Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
7
votes
1answer
175 views

Combinatorial Proof of Combinatorial Identity involving (-1)^k[(n - 1) Cr k]

Given the following identity: $$\sum_{i=0}^k (-1)^i \binom ni = (-1)^k \binom {n-1}{k}$$ This is provable by induction , however I wonder if there is a way to prove this in a combinatorial ...
2
votes
1answer
411 views

Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.
3
votes
1answer
483 views

Combinatorial Argument

Can you give a Combinatorial argument that $$\binom{3n}{3}=3\binom{n}{3}+(3)(2)\binom{n}{2}\binom{n}{1}+\binom{n}{1}\binom{n}{1}\binom{n}{1}?$$