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.

66 questions
166 views

What branch of math studies $g(\mathbf x) \leq g(\sigma \cdot \mathbf x)$?

Let $\mathbf{x} = (x_1, \cdots, x_n) \in \mathbb{R}^n$ such that $x_1 \leq \cdots \leq x_n$ and $g: \mathbb{R}^n \to \mathbb{R}$. I'm trying to prove a theorem which requires me to prove that my ...
162 views

Bijection between perfect matchings permutations with even cycles

It is possible to proof that the number of perfect matching on a set of $2n$ elements is $n!!$, and on the other hand, it is also possible to proof that the number of permutations $\varphi$ of a set ...
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 ...
86 views

Combinatorial proof of an identity between restricted counts of permutations and derangements

In an answer to Counting permutations with given condition, I showed that the number of permutations of $k$ elements that satisfy $\sigma(i+1)\ne\sigma(i)+1$ is $\frac{!(k+1)}k$, which is the number ...
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$. ...
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 ...
112 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 ...
54 views

151 views

85 views

count pairs of non-crossing partitions that differ by one transposition

Problem: $\sigma$ and $\delta$ are non-crossing partitions of $(1,2,\cdots,n)$. They only differ only by a single transposition. In another words, $\sigma \delta^{-1}$ is a single transposition. ...
112 views

Prove this conjecture for $k = 4$ i.e. prove that whatever moves $A$ can come up with, $B$ can always reply such that, in the end, $A$ has no moves.

Two players $A$ and $B$ are playing the Eat the set game. The game is the following: • The game starts with a set $S$ of $k$ elements i.e. $S = \{1, 2, . . . , k\}.$ Players have to choose subsets of ...
122 views

Combinatorical method proving Euler's theorem

If this a duplicate question than I apologize. How would you prove Euler's theorem using combinatorics? The theorem goes: $x^{\phi(n)}\equiv 1 \pmod n$ where $(x, n)=1$ I can only come up with ...
59 views

106 views

Is there a combinatorial interpretation for the following sum?

Let $a(n,t)= \sum_{k=0}^n \binom{n}{k}^2t^k.$ Using generating functions it is easy to show that $$\sum_{k=0}^n a(k,t) a(n-k,t)=1/2 \sum_{k=0}^n \binom{2n+2}{2k+1}t^k.$$ Is there also a ...
241 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 ...
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 ...
21 views

72 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 ...
87 views

135 views

Combinatorial proof of $\sum_{k} \binom{2r}{2k-1}\binom{k-1}{s-1}=2^{2r-2s+1}\binom{2r-s}{s-1}\ \ r,s\in \mathbb{N}_0$

Give a combinatorial proof of the identity $$\sum_{k} \binom{2r}{2k-1}\binom{k-1}{s-1}=2^{2r-2s+1}\binom{2r-s}{s-1}\ \quad r,s\in \mathbb{N}_0.$$ Obviously the identity is true when $r<s$ so let’...