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.

2
votes
2answers
60 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
25 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
32 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
20 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
55 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
34 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
31 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
38 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
81 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
54 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
101 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
135 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
56 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
57 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
51 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
48 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
77 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
88 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
70 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
145 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
10 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
30 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
63 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
29 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
53 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
69 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
324 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
23 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
325 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
104 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
60 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
111 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 ...
1
vote
0answers
65 views

A combinatorial proof of determinant as the hyper-volume bounded by vectors?

There are many proofs that the determinant of a 2x2 matrix is $ad - bc$ which is the area of a parallelogram bounded by the row (or column) vectors of the matrix. They come in many forms: plain ...
4
votes
0answers
111 views

On the Catalan Numbers

I have been able to prove the following using the snake oil method: $$\sum_{k \ge 0} C_k {{n-2k} \choose {l-k}} = {{n+1} \choose {l}}$$ where $l,n$ are positive integers and $C_k$ is the $k$-th ...
2
votes
1answer
43 views

Using the Langrange Inversion Formula

I am currently going through the proof of the Theorem $5.4.2$ on page 38 of Enumerative Combinatorics Vol $2$ by R. Stanley and I think I understand the proof. The proof of Corollary $5.4.3$ as shown ...
2
votes
3answers
147 views

Proving If $k \le \left\lfloor \frac{n}{2} \right\rfloor$ then $\binom{n}{k-1} < \binom{n}{k}$

So I'm trying to do a proof for this problem: If $\displaystyle{k \le \left\lfloor \frac{n}{2} \right\rfloor}$ then $$\displaystyle{\binom{n}{k-1} < \binom{n}{k}}$$ I can do it algebraically but ...
0
votes
0answers
30 views

Combinatorial identity $\sum_{j=i}^n \begin{pmatrix} j-1 \\ i-1 \end{pmatrix} = \begin{pmatrix} n \\ i \end{pmatrix}$ [duplicate]

prove $$\sum_{j=i}^n \begin{pmatrix} j-1 \\ i-1 \end{pmatrix} = \begin{pmatrix} n \\ i \end{pmatrix}$$ What I am doing now is to time $i$ on both side and try to argue out of this: $$\sum_{j=i}^n i \...
3
votes
0answers
75 views

A combinatorial inequality $\binom {2n}{k} + \binom {2n}{n-k} \ < \ \binom{2n}{n} + \binom{2n}{0} \ \ \text{for} \ \ k<n \ \ $

I am struggling some math problems. Fighting some problems, I find out a rule. $$$$ Could you please see the table below? HERE is my question! I (may) found out the inequality $$$$ $$\binom {2n}...
6
votes
2answers
229 views

Combinatorial meaning of $L_m=S_m-{m\choose m-1}S_{m+1}+{m+1\choose m-1}S_{m+2}\mp\dots+(-1)^{n-m}{n-1\choose m-1}S_n$

I want to understand the meaning behind the coefficients of the following formula, $L_m$: Let $U$ be a finite set, and there are $n$ properties defined on it: $a_1,a_2,\dots,a_n,$ and let $S_m$ ...
1
vote
1answer
56 views

How to seat guests in circles of chairs if each one wants to have free seats to his left and right?

This is a task I saw in a programming competition. So, you're given a list of guests. Each $i$th guest wants to have $l_i$ free spots to his left and $r_i$ free spots to his right, because they are ...
4
votes
2answers
228 views

Proving formula sum of product of binomial coefficients

I have to proof the following formula \begin{align} \sum_{k=0}^{n/2} {n\choose2k} {2k\choose k} 2^{n-2k} = {2n\choose n} \end{align} I tried to use the fact that ${2n\choose n} = \sum_{k=0}^{n} {n\...
1
vote
1answer
54 views

Derangement with constraints

$9$ letters and $9$ envelopes are denoted by $\{A, B, C, D, \ldots, I\}$ and $\{a, b, c, \ldots, i\}$ respectively. To find the number of ways so that no letter goes into right envelope but given ...
0
votes
1answer
89 views

Combinatorics contest math question [closed]

James has a red jar,a blue jar and a pile of 100 pebbles.Initially both jars are empty. A move consists of moving a pebble from the pile into one of the jars or returning a pebble from one of the jars ...