Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
vote
2answers
22 views

Partitions of a set with n elements (proof)

I was reading a textbook about combinatorial mathematic which claimed that we can calculate the exact possible partitions of a set with n elements . I searched it on wikipedia and I read about bell ...
4
votes
1answer
44 views

Combinatorial proof for $\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$

I am trying to give a combinatorial proof for: $$\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$$ Where $p$ and $n$ are natural numbers. We could easily see that if $p=n$ this reduces ...
2
votes
1answer
48 views

Combinatorial proof of fibonacci

I need to proof this expression combinatorially $f_{2n+1}= \sum_{i \geq 0} \sum_{j\geq 0} \binom{n-i}{j} \binom{n-j}{i}$ for all $n \geq 0$. As $f_1 = 1, f_2=2$ I dont know how to start combinatorial ...
3
votes
3answers
71 views

Combinatorics Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$

Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$ I am trying to generate a combinatorics proof of this identity, but have been stuck for hours. I've been trying to think of someway to ...
4
votes
1answer
49 views

Combinatorial proof $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$

Give a combinatorial proof (double counting) that $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$ There was a hint that maybe $n$ bit binary numbers without 01 may help. (eg. 1001,...
0
votes
1answer
39 views

Prove your identity using a block-walking argument.

Prove that $\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2=\binom{2n}{n}$ by using a block-walking argument. I found the identity but I wasn't able to find a block-walking argument. Could ...
2
votes
1answer
42 views

Combinatorial proof of $\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$

Give a combinatorial proof for this identity for nonnegatif integer $k$ and $n$ such that $0 \leq k < n$ $\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$ My attempt: I tried to ...
1
vote
1answer
22 views

Proof by induction: summation inductive step

Disclaimer: This question is just a practice question and is not for marks. I am trying to prove the following statement (I'm skipping right to the inductive step here since the base case is trivial):...
6
votes
1answer
192 views

Prove: $[k+y-1-v]{v \choose k}\geq \sum_{j=0}^a(-1)^j \left( \sum_{i=0}^k{v-i \choose k-i}r_i(j)\right)+\epsilon(a,k,p)$

I'm studying the ramsey numbers, especially $R(3,6)=18$ for Graver and Jackel, and i have tried to understand the theorem $2$ for quite some time but I have not succeeded. Theorem 1: Let $G$ be a ...
7
votes
1answer
93 views

Combinatorial proof of $\binom{nk}{2}=k\binom{n}{2}+n^2\binom{k}{2}$

This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good ...
0
votes
0answers
81 views

Partial Matching and Augmenting Paths of Length 1

$$ \begin{array}{l}{\text { Let } M \text { be a partial matching in } G=(V, E) . \text { Prove that the following two conditions are }} \\ {\text { equivalent. }}\end{array} $$ $$ \text { (i) There ...
2
votes
2answers
83 views

Solving combinatorial problems with symbolic method and generating functions

I am trying to solve the following problems: a) Let $\mathcal{F}$ be the family of all finite 0-1-sequences that have no 1s directly behind each other. Let the weight of each sequence be its length. ...
1
vote
0answers
33 views

Combinatorial argument for solution of recursion behaving similarly as Pascals triangle?

Given the following recursion: $$ F(n,d) = F(n-1,d) + F(n-1,d-1) + 1 $$ With initial conditions $F(0,d)=1,F(n,1)=1$ and $n\in\mathbb N_0, d\in\mathbb N$. I noticed that it holds (By writing out the ...
3
votes
2answers
38 views

Finding the generating polynomial for this string-counting combinatorial identity

The combinatorial identity goes as follows: $$ \sum_{k=0}^\ell {n+k-1 \choose k} {n-k-1 \choose {\ell-k}} = {2n-1 \choose \ell } \ ,\ell \leqslant n-1 $$ Intuitively, the RHS counts all (0,1)-...
1
vote
0answers
21 views

Combinatorial proof of Hamiltonian paths on the rook graph

We can be sure that number of Hamiltonian paths on the rook graph for any single cell on $n\times2$ chessboard equals $$ H(n+1) = \sum_{k=0}^{n} \binom{n}{k} \binom{k}{\lfloor{\...
1
vote
0answers
64 views

Special case of Wolstenholme's theorem true for p=3?

Is the identity $$\binom{p^k}{jp^{k-2}}\equiv \binom{p^2}{j} \;\mathrm{mod}\,p^3$$ true for all $k\geq 2$ and $j=1,\dots,p^2$ when $p=3$? By Wolstenholme's theorem, we know it is true for all primes $...
0
votes
2answers
36 views

How do I solve this combinatorial proof involving factorial (n)_k?

Let $n$ and $k$ be positive integers with $n \ge k$. Give a combinatorial proof that $$n_k = (n-1)_k + k(n-1)_{k-1},$$ where $n_k$ is a falling factorial: $n_k$ = $n(n-1)(n-2)\ldots(n-k+1)$. I know ...
1
vote
0answers
33 views

Combinatorial proof of the formula for hook-length

Let $\lambda=(\lambda_1,...,\lambda_n)$ be a partition. My goal is to prove the following formula $$\sum\limits_{x\in\Lambda}(h(x)^2-c(x)^2)=|\lambda|^2,$$ where for $x=(i,j)\in\Lambda:=\{(i,j)\in\...
1
vote
0answers
20 views

How to compute $T'=\{n + 1 - i : i \in T \}$ for lexicographic ordering?

I have a question that came up during one of my combinatorial algorithm lectures, and could use some help. One of the theorems our book provides states that: Let $S$ consist of all $k$-element ...
-2
votes
1answer
39 views

Prove formula by combinatorially [closed]

$$ \binom{r}{r} + \binom{r+1}{r}+\binom{r+2}{r} + \cdots + \binom{n}{r}=\binom{n+1}{r+1}$$ I knew that I had to prove from RHS and LHS RHS simply like: take $r+1$ out of $n+1$ elements But How can I ...
4
votes
0answers
84 views

Collection of less well-known, non-trivial, elegant story proofs (ie, “double counting proofs”) of combinatorial identities

By story proof I mean proving a combinatorial identity by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. The ...
0
votes
1answer
58 views

Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$ where $n\geq2$ using a combinatorial proof.

Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$, where $n\geq2$, using a combinatorial proof. I've tried to think of it in terms of a counting problem. I think that for the ...
-1
votes
3answers
120 views

Choosing 2 squares on an $8 \times 8$ ($64$ square) chessboard

On an $8 \times 8$ ($64$ square) chessboard, how many ways can we choose pairs of squares such that each pair doesn't have the same colors? Each pair should consist of a white and black square.
0
votes
1answer
137 views

number of ways of splitting the tree such that every tree thus formed has a given xor value. [closed]

Find the number of ways of splitting the tree such that every tree thus formed has a given xor value. Number of ways to remove zero or more edges from this tree in such a way that each individual tree ...
0
votes
1answer
63 views

Swapping elements to form a specific permutation - Formal Proof

Considering a permutation of [1, 2, ..., n], it is fairly obvious that on doing n/2 swaps we arrive at the permutation [n, n-1, ..., 1]. This can be achieved by swapping the first element with the ...
1
vote
2answers
58 views

Is $2\binom{d}{k} \le \binom{2d}{k}$ true?

I am quite certain that $2\binom{d}{k} \le \binom{2d}{k}$ holds for every positive integers $k,d$, where $1 \le k \le d$. Is there a simple proof? A combinatorial proof ? An immediate combinatorial ...
7
votes
2answers
72 views

Is it valid to define $\binom{n}{n+k} = 0$

Is it valid to define $$\binom{n}{n+k} = 0$$ where $k$ is an integer in $\{k < -n\}\cup\{k > n\}$ ? I couldn't find anything on this notation via a quick google search, but I ran into it in ...
0
votes
1answer
52 views

prove that $a_n=\sum_{k=1}^{n}\binom{n-1}{k-1}(k-1)!a_{n-k}\rightarrow a_n=n!$

I try to prove that: Given $a_n=\sum_{k=1}^{n}\binom{n-1}{k-1}(k-1)!a_{n-k},a_0 = a_1 = 1$. Prove that $a_n=n!$ for any natural $n$, by finding a combinatorics problem that fits both. any solution (...
1
vote
1answer
49 views

Combinatorial proof of ${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$

Give a combinatorial proof of $${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$$ In first of all, I know how to proof directly. We move all terms to left hand side of ...
0
votes
1answer
31 views

Proving an Identity using Combinatorial Arguments

I'm working on this question: For integers $n\geq1$, define $A_{n}$ to be the set of all ordered pairs of subsets of ${1,\dots,n}$, i.e. $$A_{n}=\{(S_{1},S_{2}) \mid S_{1},S{2} \subseteq \{1,\dots,...
1
vote
1answer
78 views

Evaluate $4^n = \sum_{k=0}^{n} {n \choose k} 3^k$

Prove $4^n = \sum_{k=0}^{n} {n \choose k} 3^k$, using a combinatorial proof of the set $S = \{(a_1, a_2)| a_1, a_2 \in \{1...n\}\}$. I'm having trouble figuring out how to prove $4^n$(LHS) using the ...
8
votes
0answers
91 views

Binomial sum which adds to $2^n n!$

I'm looking for a combinatorial interpretation for the identity $$ \sum_{k=0}^n\binom nk (2k-1)!!\,(2n - 2k - 1)!! = 2^n n! $$ where $(2n - 1)!! = (2n - 1)(2n - 3) \cdots 5 \cdot 3 \cdot 1$. ...
0
votes
2answers
42 views

How to make any natural numbers (placed in the chessboard cells) divisible by 10 by using the given tools [closed]

The original condition is: In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a ...
3
votes
1answer
73 views

Combinatorial Proof that $p(n)/(1+\epsilon)^n \to 0$

I was thinking this morning about the identity $ \prod_{n=1}^{\infty} \left( \frac{1}{1-q^n} \right) = \sum_{n=0}^{\infty} p(n) q^n$. The product on the left converges for $|q|<1$, which implies ...
3
votes
2answers
147 views

Identity involving difference of binomial coefficients

I am trying to prove the following identity but not sure how to prove it. [The followings are equivalent forms of the original equality I asked.] $$ \binom{m+n}{s+1} - \binom{n}{s+1} = \sum_{i=0}^s \...
0
votes
2answers
13 views

Combinatorial proof that the number of even cardinality subsets is equal to the number of odd cardinality subsets

Given a set of cardinality $n\geq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality I am looking for a combinatorial proof of this statement- I know ...
2
votes
2answers
59 views

Proving $\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$

Use any method to prove that $$\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$$ My Try: Base case: Let $m=1$ LHS$$\binom{n+1+m}{n+1}=\binom{n+2}{n+1}=(n+2)$$ RHS$$\sum_{k=0}^m(k+1)\binom{n+...
0
votes
1answer
33 views

Pigeonhole Principle: Proof that in an isosceles triangle with both side lengths 2 amongst 5 random points within there's two with distance $d < 1$

We're tasked to prove using the pigeonhole principle that, given an isosceles triangle with the two equal side lengths being $l = 2$, you can always choose $5$ random points of which two will have a ...
1
vote
3answers
65 views

value of $k$ in binomial expression

If $\displaystyle \binom{404}{4}-\binom{4}{1}\cdot \binom{303}{4}+\binom{4}{2}\cdot \binom{202}{4}-\binom{4}{3}\cdot \binom{101}{4}=(101)^k.$ Then $k$ is Iam trying to simplify it $\displaystyle \...
1
vote
1answer
31 views

Words of weight 5 in in Ternary Golay Code

I'm not really good at doing this type of exercices. But I'd like to know how to prove that ther are 132 words of weight 5 in the Ternary Golay Code. I am not allowed to use the weight enumerator. I ...
3
votes
0answers
54 views

Is there a combinatorial proof that the Catalan number $C_n$ satisfies $(n+1)C_n={2n \choose n}$?

I saw this question and thought that may be it is possible to prove that the $n^{\text{th}}$ Catalan number $C_n$ equals $\frac{1}{n+1}{2n\choose n}$ by taking a set $A$ of size $n+1$ and another set $...
3
votes
3answers
43 views

Is it possible to show ${k\choose 2} \ge \sum_{i } {x_i\choose 2} $ such that $\sum_i x_i =k$

I want to know if this problem can be verified or rejected. ${k\choose 2} \ge \sum_i {x_i\choose 2 }$ such that $\sum_i x_i =k$ and $x_i, \;k\in \mathbb N.$ For example $2+3=5$ and ${5 \choose 2}...
1
vote
1answer
72 views

Show that $1= \sum_{k=0}^{m} (-1)^k {m \choose k}2^{m-k}$ using sign reversing involution

Using the sign reversing involution, how can I show that $$1= \sum_{k=0}^{m} (-1)^k {m \choose k}2^{m-k}.$$ I have been trying to figure out the what the signed sets are namely $S^{ +}$ and $S^{ -}$. ...
1
vote
2answers
30 views

Proving that these two finite alternating series are equal.

For all natural numbers $n$, prove that $$ \sum_{r=0}^n \left( \frac{ (-1)^r {n \choose r} } {2r+1} \right) = 4^n \sum_{r=0}^n \left( \frac{ (-1)^r {n \choose r} } {n+r+1} \right)$$ I have tried to ...
0
votes
0answers
325 views

Prove using Stirling's approximation that for all integers n1 ≥ d1 ≥ 0…

Prove using Stirling's approximation that for all integers n1 ≥ d1 ≥ 0, and all integers n2 ≥ d2 ≥ 0, the following inequality holds: $\binom{n_1}{d_1}$*$\binom{n_2}{d_2}$$\leq$ $(\frac{(n_1+n_2)*e}{(...
2
votes
1answer
24 views

How many ways 3 persons A, B , C can be put in a row of six empty chair such that A nd B don't sit together

How many ways 3 persons A,B and C can seat in a row of six empty chairs such that A and B don't sit together? My Attempt Let us introduce three more persons D, E and F. Then these six persons can be ...
18
votes
2answers
327 views

Is there a combinatorial proof that $e$ is finite?

I'm looking for an integer $N$ and a combinatorial proof either that $(n+1)^n<Nn^n$ or that $\sum_{k=0}^n \frac{n!}{k!}<N\cdot n!$. By "combinatorial proof of $a<b$" I mean exhibiting ...
1
vote
0answers
114 views

Sum of multinomial coefficients

It is well-known (using for example the Vandermonde's convolution identity) that $$\sum\limits_{j=0}^n{n \choose j}^2={2n \choose n}.$$ During my calculation I got the following sum $$\sum\limits_{k_1+...
0
votes
1answer
61 views

Combinatorial proofs of several binomial sums

I would like to ask if you know of any combinatorial (double counting) arguments for finding a closed formula for the following sums: $\sum_{k=m}^n{k\choose m}{n\choose k}$, where ${n\choose k} = 0$ ...
2
votes
2answers
121 views

Lower Bound on God's Number in the Rubik's Cube

I'm trying to write a project about the Rubik's Cube, and althought it's easy to find out the lower bound (using half turns) is 18, finding a precise proof hereof seems impossible. How does one proof ...