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

1
vote
0answers
17 views

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$ [duplicate]

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$. Typically to combinatorially prove something we need to show that the LHS indeed counts the same ...
1
vote
2answers
44 views

Proof with Combinatorial Argument $\sum_{i = 1}^{n} (i-1) = nC2$

I am trying to prove below equation with combinatorial argument but I have no idea how this works. $$\sum_{i = 1}^{n} (i-1) = nC2$$ Can anyone give me a clue?
3
votes
2answers
103 views

Seeking non-inductive, combinatorial proof of the identity $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

How do you prove $$1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}$$ without induction? I'm looking for a combinatorial proof of this.
0
votes
0answers
16 views

CoQ and “Method of Coefficients”

I have been trying to use the Method of Coefficients in some combinatorial arguments. Since the result ended up being more complicated than I am comfortable with I would like to know if there is ...
1
vote
2answers
84 views

What is a combinatorial proof exactly?

It almost seems as though a combinatorial proof is "Explain the intuition behind this relationship (using normal words) to explain why it is true." I'm a little lost as to how this is a proof ...
7
votes
2answers
217 views

Combinatorial proof that $\frac{({10!})!}{{10!}^{9!}}$ is an integer

I need help to prove that the quantity of this division : $\dfrac{({10!})!}{{10!}^{9!}}$ is an integer number, using combinatorial proof
4
votes
1answer
75 views

Calculating the value of $\lfloor(1+\sqrt{2})^{2n}\rfloor$

Problem: Calculate the value of $\lfloor(1+\sqrt{2})^{2n}\rfloor$ where $n$ is an arbitrary non-negative integer and $\lfloor x\rfloor$ indicates the largest integer not greater than $x$. What I ...
4
votes
2answers
76 views

closed form of $\sum_{k=0}^n {2n\choose 2k}2^k$

Is it possible to find a closed form for the expression below? $$\sum_{k=0}^n {2n\choose 2k}2^k$$ I have tried counting in two ways but made no progress. And I don't know any combinatorial ...
5
votes
3answers
138 views

Combinatorial argument for an identity

Consider the following equation: $x_1 + x_2 + \cdots + x_r = n,~~$ where $~~0\leq x_{i}\leq n, \forall i$ The number of integral solutions to the above equation = ${n+r-1 \choose r-1}$. Consider ...
1
vote
1answer
81 views

Seeking a combinatorial proof $\sum _{k=0}^n (n-2k)^3\binom{n}{k}=0$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$ $$\sum _{k=0}^n (n-2 k)^3 \binom{n}{k}=0$$
2
votes
2answers
62 views

Prove this binomial identity using the following equality:

Use the equation $\frac{(1-x^2)^n}{(1-x)^n} = (1+x)^n$ to prove the following identity: $\displaystyle \sum_{k=0}^\frac{m}{2}(-1)^k{n\choose k}{n+m-2k-1\choose n-1}={m\choose n}$, $m\leqslant n$ and ...
3
votes
2answers
63 views

Combinatorics Identity about Catalan numbers.

I need to prove this identity: $\sum_{k=0}^n \frac{1}{k+1}{2k \choose k}{2n-2k \choose n-k}={2n+1 \choose n}$ without using the identity: $C_{n+1}=\sum_{k=0}^n C_kC_{n-k}$. Can't figure out how ...
0
votes
1answer
119 views

Prove combinatorial Identity using a combinatorial argument. [duplicate]

I have proved by induction on k that : $$ \binom{n}{n} + \binom{n+1}{n} + \binom{n+2}{n}+ ... + \binom{n+k}{n} = \binom{n+k+1}{n+1} $$ But now, I need to prove it using a combinatorial argument. ...
0
votes
2answers
21 views

Need help in following problems related to combinatorial analysis.

How many motorcycle number plates can be made if each plate contains 2 different letters followed by 3 different digits? How many four code words are possible using the letters in COMPUTE if (a) the ...
1
vote
3answers
178 views

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$.

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$ using the Pigeonhole principle. I am supposed to identify the pigeons and the pigeonholes. ...
0
votes
2answers
58 views

Deduce formula for $\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}$

I am working on the following problem: For each $m$ we have found the values of $$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$ for polynomials of degree at most m. Use a combinatorial story to ...
0
votes
0answers
33 views

Can we simplify this factorial summation $\sum_{i=0}^{n-1} i!(n-i)!$?

I've just solved a combinatorics problem but my answer is stuck here: $$\sum_{i=1}^{n-1} i!(n-i)!$$ Is there any way to simplify this summation? I've thought about combinatorial proof but there's no ...
4
votes
2answers
146 views

Seeking a combinatorial proof $\sum _{k=0}^n (n-2k)^2\binom{n}{k}=n\times 2^n$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$ $$\sum _{k=0}^n (n-2 k)^2 \binom{n}{k}=n\times 2^n$$
4
votes
1answer
62 views

Prove $\sum_{k=0}^n\binom{2n+1}{2k}=4^n$

I once had to show that $\cos(x)\sin(x)=\frac{1}{2}\sin(2x)$ using the Cauchy product and relied on $$\sum_{k=0}^n\binom{2n+1}{2k}=4^n.$$ However I never came up with a proof why this is true - is ...
3
votes
2answers
70 views

$\binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$

Prove combinatorially (using inclusion-exclusion) that$ \binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$ Hi, everyone. I'm at a loss here. I've been trying ...
0
votes
1answer
46 views

Combinatorial Proof of $Q_n = D_n + D_{n-1}$ [duplicate]

Let $Q_n$ be the number of permutation of $n$ integers $\{1, 2, \cdots, n \}$ such that, in the permutation, every $i$ is not succeeded by $i+1$ and let $D_n$ be the number of derangement of $n$ ...
-3
votes
1answer
82 views

Show that $\binom{n}{k}$ equals to $\binom{n-1}{k}\cdot\frac{n-k+1}{k}$. [closed]

It should be solved by using combinatorial proofs.
4
votes
4answers
120 views

Permutation of multiset

How many 8-permutation are there of the letters of the word 'ADDRESSES'? My textbook suggests that we should divide the situation into cases where a different letter is removed. In other words, ...
2
votes
4answers
204 views

prove the combinatorial identity: $ {2n \choose n} + {2n\choose n-1} = (1/2){2n + 2 \choose n + 1}$

So the first thing I did was to multiply and then isolate the left-most term. That leaves me with $$ 2{2n \choose n} ={2n + 2\choose n + 1} - 2{2n \choose n -1} $$ No specific reasoning except that ...
4
votes
3answers
182 views

Algebraic and combinatorial proof of an identity

For any two integers $2 \le k \le n-2$, there is the identity $$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$$ a) Give an algebraic proof of this identity, writing the binomial ...
5
votes
4answers
246 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
57 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
150 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
74 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
50 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
50 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 ...
2
votes
1answer
156 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
10 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
106 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
96 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). ...
9
votes
3answers
170 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
14 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
37 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
122 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
141 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 ...
4
votes
4answers
228 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
105 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
68 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
46 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: ...
3
votes
2answers
184 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
47 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
42 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
73 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.