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

5
votes
4answers
132 views

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$ [duplicate]

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant ...
1
vote
1answer
52 views

On an estimation of binomial coefficient

On page 14 of the book 'Proofs from THE BOOK', there is an estimation presented as: $$\binom{2n}{n}\le \prod_{p\le \sqrt{2n}}\ 2n. \prod_{\sqrt{2n}<p\le \frac{2}{3}n}\ p. \prod_{n<p\le 2n}\ p, ...
2
votes
4answers
117 views

A combinatorial proof for $\binom mk$+$\binom m{k-1}$=$\binom {m+1}k$

I do realize that there is a elementary proof of this result which follows from applying the formula $$\binom mk=\frac{m \cdot (m-1) \cdot \ldots \cdot (m-k+1)}{k!}.$$ I do wonder if there is an ...
-4
votes
2answers
56 views

I need to prove the following property of the binomial coefficient…please Help!

$$\binom rk = \frac rk \binom{r-1}{k-1}$$ Any help is immensely appreciated! I am absolutely confused by this problem and have no real idea of how to solve it, my professor mentioned that the answer ...
-3
votes
1answer
44 views

Is this mathematical statement? [closed]

$\{\text{integers $n$ such that $n$ is even}\}$ It can be true/false so does that mean it's proposition/mathematical statement?
4
votes
1answer
49 views

Bijection $f$ of $\mathbb{N}$ such that $n$ divides $\sum_{k=1}^{n} f(k)$

Is it possible to construct a bijection $f: \mathbb{N} \mapsto \mathbb{N}$ such that $n$ divides $\sum_{k=1}^{n} f(k)$ for every $n \in \mathbb{N}$? At first, I've tried to construct such ...
1
vote
1answer
74 views

Combinatorial proof for $\sum_{k = 0}^n \binom {r+k} k = \binom {r + n + 1} n$ [duplicate]

I'm trying to figure out a combinatorial proof for: $$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$ I've tried the committee counting thing, but that didn't work.
0
votes
0answers
8 views

Combinatorial proofs with vandermond's identity [duplicate]

I am studying for my final for discrete math and I have come across a proof that I am confused on solving. I was wondering if anyone could help. I understand that it is vandermond's identity but I ...
1
vote
2answers
59 views

Combinatorial Proof of falling factorial and binomial theorem

For $n,m,k \in \mathbb{N}$ is true: $$(n+m)^{\underline{k}}=\sum^{k}_{i=0}\binom ki \cdot n^{\underline{k-i}} \cdot m^{\underline{i}}$$ I can prove the binomial theorem for itself combinatorically ...
0
votes
0answers
57 views

determine whether a combination number is odd or even

Let $k$ be a given positive integer (fixed). I want to determine whether $$ 2n-k\choose n $$ is even or odd, for each positive integer $n$. Is there any general result? My attempt: Case (1). ...
7
votes
1answer
87 views

Combinatorial interpretation of identity: $\sum_{j=0}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2$

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} ...
0
votes
0answers
13 views

Combinational proof problem [duplicate]

I'm having trouble finding a combinatorial argument for $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}$ The right side is just choosing m+1 things from a set of n+1 things, but I can't see any way ...
2
votes
1answer
32 views

Covering $\mathbb{N}$ with disjoint arithmetic sequences

Suppose that we have a collection $S_1 = \{a_1 + kr_1\}_{k=0}^{\infty}$, $\cdots$, $S_n = \{a_n + kr_n\}_{k=0}^{\infty}$ of disjoint arithmetic sequences where $a_i$, $r_i$ are nonnegative integers ...
4
votes
1answer
84 views

Combinatorial interpretation of double factorial.

Using some basic algebra (and proved afterwards using induction), I found that: $$ 1 \cdot 3 \cdot ... (2n-1) = \frac{(2n)!}{2^n \cdot n!}$$ After a bit of research, I found out that this is known ...
3
votes
4answers
132 views

Show that $\binom{2n}{n}$ is an even number, for positive integers $n$.

I would appreciate if somebody could help me with the following problem Show by a combinatorial proof that $$\dbinom{2n}{n}$$ is an even number, where $n$ is a positive integer. I ...
3
votes
4answers
165 views

Combinatorial proof involving sum of factorials

I need help with this combinatorial proof: $1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1$ So far I came up with this: Let S be a set of numbers $1, 2, \ldots, n+1$ So LHS could be: How many ...
0
votes
1answer
32 views

Chosing $2$ person from each groups using Product rule

Group A has $10$, Group B has $15$, and Group C has $20$ persons. What if only 2 persons can be chosen and they should be from different groups, what should I do? So far I can only think of simple ...
1
vote
2answers
77 views

Find how many different ways you can wallpaper 8 rooms

What are the steps in the solving the problem below. Do you use the product rule, summation rule, or both? In how many ways you can wallpaper the same $8$ rooms with $12$ types of wallpaper?
1
vote
2answers
56 views

Seeking combinatorial proof for $F_{n+1} -1=\sum\limits_{k=0}^{n-1} F_k$

In order to give a combinatorial proof for this equation, we need to find what these two count for. But I don't know what they count for and how I can pivot the RHS to show that it actually counts ...
0
votes
1answer
42 views

Combinatorial Proof of Identity b_n

Prove that: $$b_n = 1 + \sum\limits_{k=1}^{∞} \binom{n-1}{k}b_k.$$ Workings: The first thing I noticed is that the above equation looks very similar to a Bell Numbers proof: ...
2
votes
2answers
146 views

Combinatorial proof for $ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$

Find the combinatorial proof for $$ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$$ After proving it using algebra, I'm unable to find a combinatorial argument for the above statement. Help ...
1
vote
1answer
47 views

Question about some properties of combinatorial structures

Consider $\mathcal A$ as the set of perfect matchings in the complete bipartite graph $K_{n,n}$ and let $i$ be an edge of $K_{n,n}$. Let $$ B_i=\{a\in \mathcal A: \hbox{matching }a\hbox{ has edge ...
1
vote
1answer
39 views

Give an combinatorial argument

I need to find the possible value of $R_i$ and prove it by giving combinatorial argument, for following identity. I was able to give an argument like this. Consider double counting. Count ...
0
votes
2answers
34 views

Modulo congruence

I have a problem here that I have no idea how to go about solving. It states: Let $n∈Z$ with $n>1$. (a) If $n=2k$ for some odd integer $k$, prove that $k^3≡k \pmod{2n}$. (b) If $n=2k$ for ...
2
votes
3answers
62 views

Combinatorial Argument with Natural Numbers

Give a combinatorial argument to show that all natural numbers c(n,k) = c(n,m) where c stands for combination.
1
vote
1answer
104 views

combinatorial proof that $\sum_{i=r}^{n}(2i-r)\binom{i-1}{r-1}^2=r\binom{n}{r}^2$

I came accros the following identity when I was doing an olympiad problem (IMOSL 1997 - 13), but I'm having troubles finding a combinatorial interpretation. Can someone help me? ...
1
vote
0answers
23 views

Special partitions for cubic 3-edge connected graphs

I'm trying to prove the following A cubic 3-edge connected graph $G = (V, E)$ allows partitions $T_{i}\subset E$ such that $G\setminus T_{i}$ is 2-edge connected, for $i = 1,\ldots, 5$. In ...
5
votes
4answers
415 views

Give a combinatorial argument

Give a combinatorial argument to show that $$\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6} = 6\cdot2^5$$ Not quite where to starting proving this ...
3
votes
4answers
193 views

proving an invloved combinatorial identity

How to prove following Identity? $$\sum_{k=0}^n (-1)^k {n-k \choose k} m^k (m+1)^{n-2k} = \frac {m^{n+1}-1}{m-1}, m \ge 2$$ This seems very hard to me. Any idea about how to prove it combinatorialy? ...
2
votes
3answers
113 views

Combinatorial proof of $ k{n \choose k} = n {n-1\choose k-1} $

I have to prove this using a combinatorial proof $$ k{n \choose k} = n {n-1\choose k-1} $$ What's the standard procedure on doing this? The only thing I managed was to split it into: (by fixing one ...
6
votes
5answers
254 views

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

$$\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
146 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
1answer
62 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
2answers
106 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
24 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
130 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
70 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
86 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
82 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
110 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
91 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 $ = ...
2
votes
3answers
153 views

Prove this combinatorial identity

$${n \choose k}{k \choose 1}{k-1 \choose 1} = n(n-1){n-2 \choose k-2}$$
3
votes
1answer
145 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
403 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
101 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
144 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
1answer
79 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
137 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
60 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
243 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 ...