# 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.

354 questions
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. ...
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 ...
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)-...
20 views

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 ...
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$. ...
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 ...
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 ...
145 views

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 ...
63 views

43 views

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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
30 views

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$ ...
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 ...