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.

9
votes
1answer
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 ...
8
votes
1answer
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 ...
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 ...
2
votes
1answer
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 ...
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$. ...
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 ...
4
votes
0answers
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 ...
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
0answers
76 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}...
3
votes
0answers
85 views

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

A recurrence relation of $$S_n =\sum_{k=0}^{n} \frac{1}{\binom{n}{k}}$$ is $$ \frac{n+2}{\binom{n}{k}} - \frac{2n+2}{\binom{n+1}{k}} = \frac{n-k}{\binom{n}{k+1}} - \frac{n+1-k}{\binom{n}{k}}, \quad 0 ...
3
votes
0answers
134 views

A Combinatorial Geometry Problem With A Solution Using Extremal Principle

I have solved this following Combinatorial Geometry Problem using extremal principle.Please check whether this solution is correct or not.Also write if you have any other solution. Problem :- Let $...
3
votes
0answers
151 views

Proof of Binomial Sum via Double Counting

I have attempted to double count the following equivalence but to no avail. I'm unable to arrive at the Left Hand Side. $\displaystyle \sum_{k=0}^n \frac{(-1)^k}{k+3} \binom{n}{k} = \frac{2}{(n+1)(n+...
2
votes
0answers
104 views

Counting binary sequences satisfying a certain condition

We are given a binary sequence $x\in \{0,1\}^n$ and an integer $l\leq n$. Let $A$ denote the set of integer sequences $\alpha=(\alpha_1,\ldots,\alpha_l)$ satisfying $1\leq\alpha_1<\alpha_2<\...
2
votes
0answers
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. ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
59 views

How to prove that some combinatorical function has minimum on borders?

One maximum likelihood estimation is calculated according to equation: $$\widehat{\ell}=\operatorname*{argmin}_\ell\mathbb{E}f(\ell,k),$$ where $f(\ell,k)$ is a function of two variables: $$f(\ell,...
2
votes
0answers
96 views

Proving and generalizing a combinatorial identity

I've conjectured the following identity, which I can reason combinatorically. Assuming $M$ is even, then $$ \sum_{\text{even }m}^{M}\binom{M}{m}^2m!\ [(M-m-1)!!]^2\overset{?}{=}(2M-1)!!\,,$$ where ...
2
votes
0answers
136 views

Double counting proof of binomial theorem for positive integers $x,y$

I was thinking of a double counting proof of the binomial theorem for positive integers $x,y$. I want to verify if the following argument is correct: Argument: Let us consider a group of $n$ boys. We ...
2
votes
0answers
126 views

Combinatorial determinant & Vandermonde relation

I am trying to prove the following identity for a set of variable $\lbrace z_1,\dots,z_k\rbrace$, for $S_k$ the set of all permutations of $[1,k]$ and $(-1)^P$ the signature of a permutation P. $$\...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
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 ...
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 $...
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 ...
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+...
1
vote
0answers
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 ...
1
vote
0answers
87 views

Minimum capacity cut reduction from digraph with two edge weight sets

Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{...
1
vote
0answers
54 views

Changing coins in change-making problem

Assume I have coins of four different denominations $d_i$, say $1$, $2$, $5$ and $10$. One problem that could be asked is how many different ways there are to get to $20$ by adding up exactly $3$ of ...
1
vote
0answers
293 views

Tower Of Hanoi (4 Pegs)

In the Tower of Hanoi game, let $S_{n}$ denote the minimum number of moves needed to transfer $n$ disks from one tower to another tower when there are four towers. Show that $Sm \leq 2$ · $Sm−k + 2^{...
1
vote
0answers
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’...
1
vote
0answers
118 views

Euler Polynomial Generating Function Proof

The generating function for the Eulerian polynomials is $$\frac{t-1}{t-e^{(t-1)x}} = \sum_{n=0}^\infty A_n(x) \frac{t^n}{n!}$$ where $A_n(x)$ is the $n^{th}$ Euler polynomial and $$A_n(x) = \sum_{k=...
1
vote
0answers
64 views

Characterizing $n$-exceptions on the ring of symmetric polynomials

(Also in Mathoverflow: https://mathoverflow.net/questions/286473/characterizing-n-exceptions-of-the-ring-of-symmetric-polynomials) We say that an homogeneous symmetric polynomial $f(x_1,\ldots,x_n)$ ...
1
vote
0answers
58 views

Prove Eulerian Number using Combinatorics.

For any $n ≥ 1$ and $1 ≤ k ≤ n$, define the “Eulerian number” $e(n, k)$ to be the number of permutations of $\{1, 2, . . . , n\}$ with exactly $k −1$ descents. So $e(n, 1) = e(n, n) = 1$, and $e(n, k) ...
1
vote
0answers
65 views

Understanding TDI proof using Cramer's rule (Giles and Pulleyblank)

I am reading "Total dual integrality and integer polyhedra" by Giles and Pulleyblank (1979), and I don't understand the proof of theorem 3.2: Theorem 3.2 For any rational system $\mathbf{Ax}\leq\...
1
vote
0answers
99 views

Combinatorial analysis

There are $20$ children in a lost ship. They do not remember their birthdays but would like to be assigned with one. 1. In how many ways this can be done so that exactly $2$ children will get ...
1
vote
0answers
71 views

Isabelle 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
0answers
29 views

Special partitions for cubic 3-edge connected graphs

I'm trying to prove the following A cubic 3-edge connected graph $G = (V, E)$ allows partitions $T_{i}\subset E$ such that $G\setminus T_{i}$ is 2-edge connected, for $i = 1,\ldots, 5$. In other ...
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 ...
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}{(...
0
votes
0answers
66 views

What is the maximal value that we can have after 99 operations?

we begin with the numbers $1,\frac{1}2 ,\frac{1}3,\ldots \frac{1}{100}$ written in a board. We do the following operation : we delete $2$ numbers $a$ and $b$ from the board , and we remplace them with ...
0
votes
0answers
48 views

$k$-out-of-$n$ combinations, arranged as matrices, satisfying certain conditions

Notations. (i). $1^k:$ $k$ bits long string of $1's$. (ii). $f^{i_1,i_2,\dots,i_k}(x):$ Given $x \in \{0,1\}^n$, select the $k$ bits at indices $i_1,i_2,\dots,i_k$, in order, from $x$, to generate a ...
0
votes
0answers
61 views

A question on combination as a sum of series.

The first result follows directly from the definition of combination.The second result also follows if we partition $n$ in two parts, $k$ and $n-k$ and choose from there differently.But I can't get ...
0
votes
0answers
35 views

Double Induction about Fibonacci even terms and odd terms.

I am studying Fibonacci numbers using my number theory textbook, I saw this question and wondered if I can use double induction, I am not sure is this called "double induction" or not, I called it ...
0
votes
0answers
45 views

How many people do we need for seemingly random meet up of each other?

This is just out of curiosity. Let's say there is a group of people, $A$, that never met each other before. The size of $A$ is $|A|=N$. In $A$, there are people, $a_i$, where $1 \leq i \leq N$. Now, ...
0
votes
0answers
79 views

A Chess Tournament : All Time Same Number of Game Player

Let a Chess Tournament has $n$ participants. And any two players play one game against each other. Then in any point of time, there are two players who have finished the same number of games. Is it ...
0
votes
0answers
67 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 ...
0
votes
0answers
378 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). $k=0$....