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.

Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
20 views

Configuration of high-dimensional spheres

Let $S = \{S_1, \dots ,S_n\}$ be a finite set of $d$-dimensional spheres, and let $E$ be a combination of intersections between them, where an intersection is a rule of the form $S_i \cap S_j \subset ...
-1
votes
0answers
37 views

Prove that the number of solutions to $e_1 + · · · + e_n = k$ is $C(n+k-1,k)=C(n+k-1,n-1)$

Why is the number of solutions to $e_1 + · · · + e_n = k$, $C(n+k-1,k)=C(n+k-1,n-1)$? I understand that this can be proved using a stars and bars approach, however is there another approach using the ...
1
vote
2answers
73 views

Explain why the coefficient of $x^n$ in the Euler product is equal to the number of partitions of n?

The Euler product is $\prod_{k=1}^{\infty}\frac{1}{1-x^k}=\prod_{k=1}^{\infty}(1 + x^k + x^{2k} + x^{3k} + ...)$ Why does the coefficient $x^n$ equal the number of partitions of n from the Euler ...
0
votes
0answers
37 views

Combinatorial proof that $2^{n+1}-1=1+2+4+\dots+2^n$ [duplicate]

Let $S_k$ be a set with $k$ elements. Then $S_k$ has $2^k$ subsets. So the formula $2^{n+1}-1 = \sum_{k=0}^n 2^k$ can be translated to $$\text{number of *nonempty* subsets of $S_{n+1}$} = \sum_{k=0}^n\...
0
votes
0answers
40 views

A permutation π on $[n]$ is said to be even-dominated if $\phi_{2i−1}< \phi_{2i}> \phi_{2i+1} \ for \ all 1 ≤ i < n/2 $

Let a be the number of even-dominated permutations on $[n]$. Let $a(x)$ be the exponential generating the function of $(a_n)_{n≥0}$.
2
votes
0answers
80 views

Explain why $4$ cannot be replaced by $5$ in part a)

a) Construct a Latin square of order $8$ in which the submatrix formed from the first $4$ rows and $4$ columns is the addition table for $Z_4$. b) Explain why $4$ cannot be replaced by $5$ in part a) ...
0
votes
0answers
38 views

Prove combinatorially: $\sum_{r=0}^n (-1)^r \binom{n}{r}CC^{k-r}_n = 0$

$n > k > 0$. $n,k \in \mathbb{N}$ Prove combinatorially (without algebric manipulation): $\sum_{r=0}^n (-1)^r \binom{n}{r}CC^{k-r}_n = 0$ Note: $CC^{k}_n$ is the number of options to ...
0
votes
1answer
54 views

Using 'tiling' proof technique to create combinatoric proofs about number relationships. [closed]

The number of ways of tiling a $1\times n$ rectangle with $1\times 1$ and $1\times 2$ tiles is $F_{n+1}$. (a) Use a tiling argument to give a combinatorial proof that $$F_n^2+F_{n+1}^2=F_{2n+1}\;.$$...
2
votes
0answers
29 views

How many ways are there to permute the elements of the set [7] so that an even number is in the first position?

As the title asks, how many ways are there to permute the elements of the set $[7]$ so that an even number is in the first position? This is a question from "A Walk Through Combinatorics" by Bano. ...
2
votes
3answers
157 views

Combinatorial explanation of ${n\choose r}={n-1\choose r-1}+{n-1\choose r}$

${n\choose r}={n-1\choose r-1}+{n-1\choose r}$ (4.1) Equation(4.1)may be proved analytically or by the following combinatorial argument:Consider a group of $n$ objects, and fix attention on some ...
1
vote
1answer
91 views

Given positive integers $n, k, i,$ prove $\binom{n}{k} = \sum_{j=i}^{n-k+i}\binom{j-i}{i-1}\binom{n-j}{k-i}$

I am trying to solve this challenge question, but I cannot seem to figure out how to approach this: Given $n, k,$ and $i$ positive integers with $1 \leq i \leq k \leq n$, $$\binom{n}{k} = \sum_{j=i}^...
0
votes
1answer
41 views

In how many different ways can we place $k$ elements in $n$ boxes in which each box has a fixed maximum capacity?

I've been reading and studying about Permutations, Dispositions and Combinations recently. The problem I've facing since yesterday (and I've not been able to find a solution either in my own or on the ...
0
votes
0answers
43 views

Combinatorics Proof 3kCk

I have trouble solving combinatorics proofs. I've looked at a bunch of textbook examples, but I never seem to figure out how to solve one on my own. Right now, I am stuck with this one: $\binom{3k}{...
2
votes
2answers
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 ...
0
votes
0answers
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$ ...
3
votes
2answers
125 views

Unexpected formulas for “exactly $k$ sets” and “at least $k$ sets” variations of the principle of inclusion-exclusion

There are two formulas that I have derived, and the difference between them is puzzling me. Let $n$ be a positive integer and $A_1,A_2,\ldots, A_n$ be finite sets, and let $k$ be an integer such that $...
0
votes
1answer
23 views

Choosing objects from different sized groups group wise [closed]

Suppose there are k+1 room.And in Room 1 there are r+0 students and in Room 2 there are r+1 so on then number of ways of choosing r students from only one room . For Example; all r student can be ...
0
votes
1answer
13 views

How to proceed with Vandermonde's formula when it's multipled with iterating variable?

I was solving one problem where I am stuck in the middle... Plz kindly suggest some ways to proceed further.. So the problem is: The value of $$\frac{\sum_{i=0}^{100}{{k}\choose{i}}{{m-k}\choose{...
0
votes
1answer
45 views

Use combinatorial reasoning to show that Stirling number

Use combinatorial reasoning to show $\begin{Bmatrix} n\\ n-2 \end{Bmatrix} = \binom{n}{3} + 3\binom{n}{4}.$ The Stirling number is the number of permutation of n into $n-2$ parts.
1
vote
1answer
30 views

Combinatorial proof of $1+2(\sum_{i=0}^n 3^i)=3^{n+1}$

I have this workbook of proofs that I've been trying to finish for a couple of months now. There is this problem in it that requires me to prove $1+2(\sum_{i=0}^n 3^i)=3^{n+1}$ using combinatorial ...
2
votes
1answer
48 views

Combinatorial proof of $\sum_{k=n}^{q-m} \binom{k}{n} \binom{q-k}{m} = \binom{q+1}{m+n+1}$

I have been trying to see how to combinatorially prove equation (6.97) from this document, which states that $$\sum_{k=n}^{q-m} \binom{k}{n} \binom{q-k}{m} = \binom{q+1}{m+n+1}$$ My first thought ...
-1
votes
2answers
35 views

combinatorial proof of $\sum_{k=1}^{n} k\binom{n}{k}^2 = n\binom{2n-1}{n-1} $ [closed]

Some one can help me to proof this equation please? I thought about the numbers of ways to choose a group of $n$ from $n$ boys and $n$ girls when the "CEO" must be a boy. But I don't really know how ...
3
votes
2answers
49 views

Prove combinatorics equality?

Assume $j$ is fixed, prove the following: $$\sum_{i}\binom{n}{i, j, n-i-j} = 2^{n-j}\binom{n}{j}$$ So the left hand side reminds me the multinomial theorem and we can think of a long sequence word ...
7
votes
1answer
160 views

Help with this problem about a constructed number, that is from an arbitary n numbers, and that is divisible by a prime

Let $p$ be a prime number, and $n$ be an integer such that $n \geq p$. Let $a_1,...,a_n$ be arbitrary integers. Let $s_0 = 1$, and for every $k \ge 1$, let $$s_k=|\{B \subset \{1,2,...,n\} : p\mid\...
2
votes
2answers
74 views

Connected path of diagonals across an $n\times n$ grid, and Lemma of Sperner

Given an $n\times n$ grid where we draw at random one diagonal in each of the 1×1 unit squares. Then we can always find a connected path using these small diagonals that goes from one side of the grid ...
1
vote
1answer
55 views

$\sum_{k=1}^{n} \frac{k}{k !} \sum_{i=0}^{n-k} \frac{(-1)^{i}}{i !}=1$

Prove that $\sum_{k=1}^{n} \frac{k}{k !} \sum_{i=0}^{n-k} \frac{(-1)^{i}}{i !}=1$ There were no significant progress on the task.
0
votes
4answers
70 views

How to prove ${n+2 \choose 3}=1\cdot n + 2 \cdot (n - 1) + \ldots + n \cdot 1$?

I saw this problem as an exercise in Combinatorial Identities :- Prove that $${n+2 \choose 3}=1\cdot n + 2 \cdot (n - 1) + \ldots + n \cdot 1\,.$$ After giving some time to this, I think that it ...
1
vote
0answers
43 views

Combinatory Explanation for $ \sum_{k=1}^{100} {{100} \choose {k}}2^k=3^{100}-1 $ [duplicate]

How do I Explain this Combinatory? $$ \sum_{k=1}^{100} {{100} \choose {k}}2^k=3^{100}-1 $$
0
votes
0answers
20 views

Is there any combinatorial identity that can help me evaluate this? [duplicate]

I need help to find a way to evaluate this: $$\sum_{k=0}^n {k+m \choose k} \space\text{given that m} \gt 0$$
4
votes
3answers
185 views

Combinatorial proof that $\sum_0^n {n+k \choose n}{2n-k-1 \choose n-1} = {3n \choose n}$

I am trying to derive combinatorial proof of the following: $$\sum_{k=0}^n {n+k \choose n}{2n-k-1 \choose n-1} = {3n \choose n}$$ I attempted the construction of argument of type "split the $3n$ ...
3
votes
1answer
82 views

A Conceptual Intepretation of the identity

I came across the identity $$\sum_{k = 0}^{n}\frac{(-1)^{k}\binom{n}{k}}{2k+1} = \frac{2^{2n}(n!)^2}{(2n+1)!}$$ I tried it using the binomial theorem and integration and was able to prove it provided ...
2
votes
2answers
68 views

Can we simplify this summation involving factorials?

The sum is as follows: $$\sum_{k=1}^n\frac{1}{(k!)^2(2n-2k)!}\frac{1}{2^{2k}}$$ Can we compute this to an expression without summation?
1
vote
1answer
73 views

Use generating functions to prove that the number of partitions of a positive integer n into parts, each part at most 2, is [n/2] + 1

Use generating functions to prove that the number of partitions of a positive integer n into parts, each part at most 2, is ⌊n/2 ⌋ + 1 What I have: since each part is at most 2, I have p(x) = (1+x+x^...
0
votes
3answers
47 views

Binomial Coefficient Intuition

Because every number in Pascal's Triangle is the sum of the two numbers above it, and because each number in the triangle is a combination of the form $\binom{n}{k}$, this implies the formula $\binom{...
2
votes
2answers
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 ...
0
votes
0answers
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$ ...
1
vote
0answers
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}$$ ...
9
votes
1answer
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 ...
1
vote
0answers
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 ...
6
votes
2answers
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$ ...
4
votes
2answers
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 ...
4
votes
0answers
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}{...
1
vote
2answers
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!}\...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
2answers
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 ...
-1
votes
3answers
60 views

Give a combinatorial proof such that [closed]

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^...
0
votes
0answers
14 views

Partitions and Generating Functions

I am struggling with a question with a question on partitions and generating functions for combinatorics. If someone could possibly help me with this question that would be great. The question is as ...

1
2 3 4 5
12