Questions tagged [combinatorial-proofs]

Question 1

This is a proof for the hermite identity: $$\sum_{k=0}^{n-1} \left\lfloor x + \frac{k}{n} \right\rfloor=\lfloor nx \rfloor$$ Combinatorial Interpretation of the RHS Let $S$ be the set of positive ...

Question 2

Give a combinatorial proof that \begin{eqnarray*} \sum_{i+j+k=n} \binom{2i}{i} \binom{2j}{j} \binom{2k}{k} = (2n+1) \binom{2n}{n}. \end{eqnarray*} Where did this come from ? ... In this question (...

Question 3

Let $(a_n)_{n\ge 0}$ be defined by the tribonacci recurrence $$ a_n = a_{n-1}+a_{n-2}+a_{n-3}\qquad (n\ge 3). $$ I am looking for purely combinatorial proofs (no induction) of the following bounds: ...

Question 4

While playing with the Shapiro's convolution identity, I came up with the following identity: $$ \sum_{k=0}^{n} \frac{(2k)!(2n-2k)!}{k!(n-k)!n!} = \sum_{k=0}^{n} \binom{2k}{k}2^{n-k}. \tag{*} $$ This ...

Question 5

Consider two sets $A$ and $B$. Let $A$ be the set of all strings of length $2n$ with exactly $n$ $(-1)$'s and $n$ $(1)$'s. Let $B$ be the set of all strings of length $2n$ having each character to be ...

Question 6

Let $P(n,k)=\frac{n!}{(n-k)!}$ denote the $k$-permutation of $n$. Suggest a combinatorial proof of $$P(n+1,k)=k\sum_{i=k-1}^nP(i,k-1).$$ This identity relates the $k$-permutation of $n+1$ to the ...

Question 7

I'm looking for a combinatorial or probabilistic proof for the following beautiful identity involving the Catalan numbers $C_n$: $$ \sum_{k=0}^n C_{2k}C_{2n-2k}=2^{2n}C_n, \tag{1} $$ This has a simple ...

Question 8

Context: Mircea Dan Rus's 2025 paper Yet another note on notation (a spiritual sequel to Knuth's 1991 paper Two notes on notation) introduces the syntax $x^{\{n\}}=x!{n\brace x}$ to denote the number ...

Question 9

I was studying a general way to solve problems like choose 4 words from word 'parallel' , or more generally choose r words from n words (where it may be distinct or identical ) and I came across r ...

Question 10

Let $A$ and $B$ be two totally ordered finite sets having, respectively, $|A|=p$ and $|B|=q$ elements with $p > q$. The set $B^{A}$ of all functions $f\colon A \to B$ has $|B^{A}|=q^{p}$ elements, ...

Question 11

Given an unlabeled plane rooted tree whose vertices only have $0,1$ or $3$ child nodes, and the number of the vertices that have $0$ or $1$ child node is $n$. Find the number $H(n)$ of trees with ...

Question 12

I'm trying to figure out the value of the following sum, $S_n$. It's defined over a set $H_n$ which contains integer partitions of $n$ using only parts of size 2 or greater. Here are the definitions: $...

Question 13

prove the following binomial identities $$ \sum_{k=0}^{n-r} \binom{r+k}{r} = \binom{n+1}{r+1}$$ $$ \sum_{k=0}^{m} \binom{m}{m-k} \binom{n}{r+k} = \binom{m+n}{m+r} $$ With n ≥ r +m $$ \sum_{k = n-s}^{r-...

Question 14

In the proof of Theorem 4.1 of the book Random Graphs by B. Bollobas. Where it is written that Suppose the graph $A$ and $B$ are such that $B$ is an $H$-graph and it has exactly $t$ vertices not ...

Question 15

The binomial formula $(x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}y^{n-k}$ could be interpreted, when $x,y$ are positive integers, as a two-way counting of "words" of length $n$ which use ...

Stack Exchange Network

Questions tagged [combinatorial-proofs]

Question regarding a combinatorial map between two sets for proving hermite identity

Proof of a formula involving central binomial coefficients.

Combinatorial (no induction) proof: $a_n\le 2^{n-1}$ for $(1,1,1)$ and $a_n<2^{n+1}$ for $(0,1,2)$?

Combinatorial Interpretation of $\sum_{k=0}^{n}\frac{(2k)!(2n-2k)!}{k!(n-k)!n!}=\sum_{k=0}^{n}\binom{2k}{k}2^{n-k}$?

Bijection between two sets of strings of length $2n$ [duplicate]

Combinatorial proof of $P(n+1,k)=k\sum_{i=k-1}^nP(i,k-1)$ [closed]

Combinatorial or probabilistic proof of $\sum_{k=0}^n C_{2k}C_{2n-2k}=2^{2n}C_n$

bijective proof of identity coefficient-extracted from negative-exponent Vandermonde identity, and the upper-triangular Stirling transforms

combinatorics (multi-multi-choose-k)

Relationship between the the total number of functions $A \to B$ and the number of surjections $A \twoheadrightarrow B$

Is my derivation for the problem about k-Catalan numbers correct?

How to prove this sum over integer partitions is equal to the number of derangements?

Proving binomial identities with the pointer method

Proof explanation: theorem 4.1 from the book Random graphs Bollobas

Combinatorial interpretation of the sign-alternating binomial formula

Hot Network Questions