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

597 questions
Filter by
Sorted by
Tagged with
25 views

### Limit in Proving Brouwer's Fixed Point using Sperner's Lemma

I'm trying to understand the proof of Brouwer's Fixed Point Theorem using Sperner's Lemma. For example, pg.10-11 in A Combinatorial Approach to The Brouwer Fixed Point Theorem. I was able to follow ...
32 views

### Prove the equation combinatorially [full answer provided] - I need explanation for the answer

For every $N ∈ r, n$ $P(n,r) = \sum_{k=0}^{r}\binom{r}{k}P(n-m,k)P(m,r-k)$ Prove this combinatorially. Answer: The class has m boys and n - m girls. In what ways can r students be selected ...
20 views

38 views

### Double Counting(combinatorial proof) for $1^2\binom{n}{1} + 2^2\binom{n}{2}+3^2\binom{n}{3}+…+n^2\binom{n}{n}$ = $n(n+1)2^{n-2}$

can anyone help me with double-counting proof for this equation: $1^2\binom{n}{1} + 2^2\binom{n}{2}+3^2\binom{n}{3}+...+n^2\binom{n}{n}$ = $n(n+1)2^{n-2}$ I tried this example: we have n+1 bits and ...
36 views

### Why does $\sum_{i=1}^{n-1} {n-1 \choose i} {m+1 \choose i+1} = \frac{(m+n)!}{m!n!}$

For context, I was trying to find in how many differnt ways one could join two lists of length m and n whilst preserving their internal order. So, for example, a list of length 1 $\langle 1 \rangle$ ...
125 views

82 views

### Prove combinatorically that $\sum_{i=1}^{n}2^{i-1}3^{n-i}=3^n-2^n$.

Prove combinatorically that $$\sum_{i=1}^{n}2^{i-1}3^{n-i}=3^n-2^n\,.$$ For the right expression I was thinking about the problem "amount of $n$-long ternary vectors with at least one '$2$'", but I ...
21 views

### Catalan numbers - finding an one-to-one and onto matching between two sequences [duplicate]

I'm trying to solve the following question: How many sequences $(a_1,a_2,\dots,a_n)$ with the following requiremnts exists: $a_i\in\Bbb{Z}$ $0\le{a_1}\le\dots\le{a_n}$ $a_i<i$ ...
54 views

### A summation involving stirling numbers of the first kind

I'm finding a probability related to graphs (It's $\frac{Q(n)}{n}$). $$Q(n) = 1 + \frac{n-1}{n} + \frac{(n-1)(n-2)}{n^2}+ ... + \frac{(n-1)(n-2)...1}{n^{n-1}} = \sum_{k=1}^n \frac{n!}{(n-k)! n^k}$$ ...
86 views

### I Need help creating an intuitive answer to the sum of $1(1!) + 2(2!) + 3(3!) +\cdots+ n(n!)$

Given the sum $1+\sum_{i=1}^n i(i)! = (n+1)!$, is there an intuitive way to think about this sum? I understand the algebraic manipulation to get to that answer, and also how to use induction to prove ...
51 views

### Stirling number of the first kind summation

I'm calculating some probability and confronted such an exotic summation: $$\sum_{k=1}^{n} \begin{bmatrix} k+c\\ k \end{bmatrix}$$ where $\begin{bmatrix} k+c\\ k \end{bmatrix}$ is unsigned ...
47 views

### The number of pairs $(m,n)$ of coprime positive integers that divide $k$ is $d(k^2)$, where $d$ is the divisor counting function.

I recently found somewhere that, if $k$ is a fixed integer.Then the number of ordered pairs of positive integers $(m,n)$ such that they are coprime and both of them divide $k$ is $d(k^2)$, where $d$ ...
185 views

### Let $x^2=y^2=1$ and $xy\neq yx$. There are $\binom{2n}{n}$ expressions of length $2n$ in $x$ and $y$ that are equal to $1$.

This question is motivated by this link. The statement is as follows. (Edit: Even if there are already two great answers, I would love to have a couple more answers. Especially, I would like to see ...
81 views

### Identity of binomial coefficients: $\binom{n+1}{k+1}=\sum_{i=m}^{n+m-k}{\binom{n-i}{k-m}\binom{i}{m}}$

I came across this equation when solving another combinatorics problem. I needed to prove the following identity:  \begin{aligned} \binom{n+1}{k+1}&=\sum_{i=m}^{n+m-k}{\binom{n-i}{k-m}\binom{i}{...
61 views

### A type of Combinatorial equality：$\sum_{k=0}^{n}\binom{n}{k} \cos\frac{k}{2}\pi=2^{\frac{n}{2}}\cos\frac{n}{4}\pi.$

When computing the Taylor series of the function $f(z)=e^z\cos z,$ I use two methods: On the one hand, using Cauchy product, \begin{align*} e^z\cos z &=\left(\sum_{n=0}^{\infty}\frac{z^n}{n!}\...
35 views

### combinatorial proof for an identity with generating functions

i'm trying to prove $\frac{1}{(1-x)^n} = \sum_{r=0}^\infty{r+n-1 \choose r}x^r$ with a combinatorial proof using integer solution problems and generating functions, but I can't think of any integer ...
40 views

### Power Set and String Bijection (Proof Verification)

I'm practicing my proof-writing and was hoping you could let me know if this proof looks good. I would like to know if the proof is incorrect, if there are parts that are overly wordy/complicated, or ...
71 views

### Prove $6\begin{Bmatrix} n\\ 3 \end{Bmatrix}+6\begin{Bmatrix} n\\ 2 \end{Bmatrix}+ 3\begin{Bmatrix} n\\ 1 \end{Bmatrix}=3^n$ [closed]

Prove $6\begin{Bmatrix} n\\ 3 \end{Bmatrix}+6\begin{Bmatrix} n\\ 2 \end{Bmatrix}+ 3\begin{Bmatrix} n\\ 1 \end{Bmatrix}=3^n$ I need a combinatorial proof of this identity. The right hand side must be ...
Give a combinatorial proof of: $\binom{n+1}{k+1} = \binom{n}{k} + \binom{n-1}{k}+\dots+ \binom{k}{k}$ Give a combinatorial proof of: $k^2 = \binom{k}{1} +2\binom{k}{2}$ Show that \$1^2 +2^2+\dots+n^...