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.
1,100
questions
2
votes
0
answers
49
views
Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$.
Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$.
I got this problem from the double counting handout ( ...
- 4,039
2
votes
0
answers
49
views
Find all natural numbers $n$ such that $\binom{n+1}{k}$ is even $\forall~k=1,\dots,n$.
I want to study the parity of $\binom{n}{k}$. I know that there are several ways to do this for a given $n$ and a given $k$, such as Kummer's theorem or Lucas' theorem, which give a method to find the ...
- 1,606
0
votes
0
answers
53
views
${r + s \choose r + s - n} = \sum_{p,q,p',q'} {r \choose p} {s \choose q}$
I am fixing $m,n,r,s$ such that $m + n = r + s$ from the beginning. I have the following $4$ conditions that should be satisfied :
\begin{align*}
r &= p + p'\\
s &= q + q'\\
m &...
- 1,339
2
votes
2
answers
76
views
Prove combinatorially that: $\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$
Prove combinatorially that: $$\displaystyle {{n}\choose{k}} {{n}\choose{m}} = \sum^{k}_{i=0} {{n}\choose{m+i}}{{m+i}\choose{k}} {{k}\choose{i}}$$
I couldn't solve it by myself. it's to complicated ...
- 383
0
votes
1
answer
29
views
Proof of recursive relationship between binary permutations. [closed]
I'm tring to figure out a relationship between binary permutations.
I note $\sigma_{i, k} $ the set of all binary permutations with $i$ $0$ and $k-i$ $1$.
I think it is true to say that :
$$\sigma_{i, ...
- 151
3
votes
1
answer
75
views
Combinatorially proving $F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$, where $F_n$ is the $n$-th Fibonacci number [duplicate]
Prove the following combinatorially:
$$F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$$
So, I know that the Fibonacci number counts the number of ways to cover a $1 \times n$ ...
- 55
0
votes
0
answers
13
views
"halfthink sets" contain n and n+1
A problem: Georgina calls a 992-element subset $A$ of the set $S = \{1, 2, 3, . . . , 1984\}$ a halfthink set if
• the sum of the elements in $A$ is equal to half of the sum of the elements in $S$, ...
- 1
3
votes
0
answers
96
views
Inequality for triple product of Stirling numbers
Let ${n\brace k}$ be the Strirling number of the second kind, such that ${n+1\brace k} =k{n\brace k}+{n\brace k-1}$ with ${0\brace 0}=1$. Let $j,p,n$ integers such that $1 \le j \le p \le n$.
I ...
- 3,611
3
votes
1
answer
47
views
To prove that no perfect covers exist for the staircase board.
Let $S_n$ denote the staircase board with $1 + 2 + ... + n = $$n( n + 1)\over2$ squares. Prove that $S_n$ does not have a perfect cover with dominoes for any $n \ge 1$. This problem is provided in ...
- 709
2
votes
3
answers
72
views
Prove that if $2n$ points are colored red or blue, then we can always connect the red points to the blue points with non-intersecting line segments.
Take any set of 2n points in the plane with no three collinear, and then arbitrarily
color each point red or blue. Prove that it is always possible to pair up the red
points with the blue points by ...
- 709
-1
votes
1
answer
67
views
Show that player I can always win a Nim game in which the number of heaps with an odd number of coins is odd
Show that player 1 can always win a Nim game in which the number of heaps with an odd number of coins is odd. This question is provided in Richard A. Brauldi's book on Introductory Combinatorics. I ...
- 709
0
votes
1
answer
53
views
Combinatorial proof of $S(n,n-2)=\binom{n}{3}+\frac{1}{2}\binom{n}{2}\binom{n-2}{2}$ when $n \ge 4$ [duplicate]
$$ n\ge 4, S(n,n-2)=\binom{n}{3}+\frac{1}{2}\binom{n}{2}\binom{n-2}{2} $$
Proving this combinatorially. I understand what the LHS is doing. There are a couple of things I don't follow on the right-...
- 55
2
votes
0
answers
75
views
Proving $\sum_{1\le x\le y\le t}\frac{2^{t-x}}{xy}=\sum_{1\le x\le y\le t}\frac{C_t^0+C_t^1+\cdots+C_t^{y-1}}{xy}$ for positive integer $t$
Prove that
$$\sum\limits_{1\le x\le y\le t}\frac{2^{t-x}}{xy}=\sum\limits_{1\le x\le y\le t}\frac{\text C_t^0+\text C_t^1+\cdots+\text C_t^{y-1}}{xy},$$
where $t$ is a positive integer.
I think that ...
user1034536
0
votes
0
answers
89
views
IMO Combinatorics C2 proof check
We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are a and ...
- 135
1
vote
1
answer
57
views
Probability Coin Toss Game Never Ties in N tosses
Question
This question is a rewording of the Matching Pennies problem (Question 23) in Frederick Mosteller's "Fifty Challenging Problems in Probability". Here is my rewording:
Suppose to ...
- 483
1
vote
1
answer
47
views
average of pairs sitting next to each other - harder version
The Problem
This question comes from "50 Challenging Problems in Probability" By Mosteller. The question is:
Eight eligible bachelors and seven beautiful models happen randomly to have ...
- 483
0
votes
1
answer
60
views
Applications of the pigeonhole principle (strong form)
If $n \ge 25$ and $n = 8r_1 + 5r_2$ (with $r_1, r_2$ being natural numbers), prove that either $r_1 \ge 2$ or $r_2 \ge 2$. So is uttered the question which I found in a book on introductory ...
- 709
0
votes
2
answers
63
views
Combinatorics: A problem of 2 Discs
Two disks, one smaller than the other, are each divided into 200 congruent sectors. In the larger disk, 100 of the sectors are chosen arbitrarily and painted red; the other 100 sectors are painted ...
- 709
3
votes
1
answer
72
views
Proving the Pigeonhole Principle: Strong Form
I find my self struggling to understand this proof given by Richard A. Brauldi in his book on "Introductory Combinatorics". It is required to show that If $q_1 + q_2 + \dots + q_n – n + 1$ ...
- 709
2
votes
2
answers
66
views
lists with length $k$ with elements $b_1,b_2,\dots,b_k$ such that $|b_1|+|b_2|+···+|b_k| \le n$
Ivan and Alexander write lists of integers. Ivan
writes all the lists of length $n$ with elements $a_1,a_2,\dots,a_n$ such that $|a_1| +
|a_2|+\dots+|a_n| \le k$. Alexander writes all the lists with ...
- 1,546
1
vote
0
answers
27
views
Uniqueness of Radon point
For a set $A\subset\mathbb R^d$ of $d+2$ points, Radon's Lemma states that we find disjoint $B,C\subset A$ with $\mathrm{Conv}(B)\cap\mathrm{Conv}(C)\neq\emptyset$. Elements belonging to such ...
- 3,995
0
votes
1
answer
29
views
Consecutive Integer Sum of an m-member Sequence is Divisible by m Proof
This problem is found in Richard A. Brauldi's book on Introductory Combinatorics. It goes as follows:
Given m integers $a_1, a_2, ... ,a_m$, there exist integers $k$ and $l$ with $0 \le k \lt l \le m$ ...
- 709
2
votes
2
answers
60
views
Prove that $\Sigma_{i=0}^{n-1} (\Sigma_{j=i+1}^n(j(^nC_i) + i(^nC_j))) = n^22^{n-1}$ [duplicate]
I have tried setting
$$P=\Sigma_{i=0}^{n-1} (\Sigma_{j=i+1}^n(j(^nC_i) + i(^nC_j))$$
then
$$P=\Sigma_{i=0}^{n-1} (\Sigma_{j=i+1}^n((n-j)(^nC_i) + (n-i)(^nC_j))$$
now adding them both
$$2P=\Sigma_{i=0}^...
- 131
2
votes
1
answer
87
views
With sachets containing at most 13 seeds, given 2021 rose, jasmine or fennel seeds respectively what is the maximum number of rose seeds used?
I have taken a part of the problem which I did not understand its solution.
Basically, there are:
$2021$ rose seeds,
$2021$ jasmine seeds and
$2021$ fennel seeds.
So now, with sachets of at most size ...
3
votes
4
answers
193
views
How many different sets of positive integers $(a, b, c, d)$ are there such that $a \lt b \lt c \lt d$ and $a + b + c + d = 41$?
Is there a general formula which I can use to calculate this and if it's with proof or reasoning would be great as well. Even if you could please solve this $4$-variable ordered set of positive ...
2
votes
1
answer
49
views
Probability of getting an overlap of x or more elements drawn from two sets.
So I've got a question for which I was able to run a simulation and calculate the probability from this simulation in R (picture below, following a normal distribution) but now I was wondering if ...
1
vote
0
answers
49
views
Understanding the proof of Van der Waerden's theorem by Graham and Rothschild.
I am studying the proof of Van der Waerden's theorem by Graham and Rothschild. I have tried to understand each step, but I need to fill in some gaps. Van der Waerden's theorem says that:
$\forall k, r ...
- 11
0
votes
1
answer
39
views
Why $(n!)^m\cdot m!$ is divisor of $(mn)!$ [duplicate]
For natural number $m, n$, i found out that $\{\{\{a_1, a_2, \cdots a_n\},\{a_{n+1}, a_{n+2}, \cdots a_{2n}\}, \cdots \{a_{mn-n+1}, \cdots a_{mn}\}\}| \{a_1,a_2, \cdots a_{mn}\}=\{1,2, \cdots mn\}\}$ ...
- 9
1
vote
2
answers
49
views
What computational shortcut finds the sum all possible products given any list of n random real numbers taken r at a time? Here's what I tried...
I have the following computational shortcuts for any list of $n=4$ quantities taken r at a time. My goal is to do this for lists of any length. Taken r at a time, what function can similarly output ...
- 45
0
votes
0
answers
68
views
Possibly wrong Bolyai-tournament solution
Following problem:
"We have 100 metal balls, 51 of which are radioactive. Furthermore
we have a balance which is designed in such a way that one sphere fits on each of its two plates. If a ...
0
votes
1
answer
52
views
Paradox from graph theory
$\scriptsize\text{Though these incorrect contradictory statements aren't well received, I just want it explained.}$
Given graph $G=K_6$ where all edges are red, pick three points and change the color ...
user1034536
1
vote
1
answer
51
views
Combinatorial proof of binary partition function $b(n)$ is always even
For all integer $n$, let $b(n)$ be the number of partition of $n$ into power of two.
For instance, $b(4)=4$, since
\begin{align*}
4 &= 2^2 \\
&= 2^1+2^1 \\
&= 2^1+2^0+2^0 \\
&= 2^0+2^0+...
user1089451
2
votes
2
answers
76
views
Identity for Difference of Sum of Products of Binomial Coefficients
Problem Statement
I recently came across the following equation that I want to prove:
$$
\sum_{i=1}^{n}
\left[
\binom{n+i}{m}-\binom{n-i}{m}
\right]
\binom{2n}{n-i}
=
\sum_{i=1}^{m}\binom{n+i}{m}\...
- 9,345
7
votes
3
answers
162
views
Supplementary exercise 51, chapter 3 from 'A walk through combinatorics' 4th edition
I'm selfstudying 'A walk through combinatorics' by Miklós Bóna. This book has some supplementary exercises at the end of each chapter, no solution provided. I'm trying exercise 51, chapter 3.
...
- 4,266
4
votes
3
answers
92
views
Is there a natural bijective proof of the identity $(2^i)^j = (2^j)^i$?
As is well-known, iterating exponentials is a commutative operation. Assuming that $i$ and $j$ are positive integers, one way to view the integer $2^i$ is as the cardinality of the power set $2^{\{ 1 ,...
- 2,192
0
votes
2
answers
56
views
Derivation of Permutation Formula
I've been familiar with the formula of finding the $r$-permutation of an $n$-element set; but I've only been half-so familiar with deriving the formula. See, I know that to prove the truth of
$$
P(n,...
- 709
1
vote
3
answers
214
views
Show the following holds for $c\leq 1$: $e^{ck^2/n} \frac{(n!)^2}{(n+k)!(n-k)!} \leq M, \quad \text{for } k = 1, \dots, n.$ for some constant $M$
Show that the following inequality holds for $c\leq1$:
\begin{equation} \tag{1}
e^{ck^2/n} \frac{(n!)^2}{(n+k)!(n-k)!} \leq M, \quad \text{for $k = 1,
\dots, n$}
\end{equation}
for some constant $M$.
...
- 145
3
votes
1
answer
76
views
To prove an identity related to Gamma function
Question: How to prove the following identity for all positive integers $k$ and $n$:
\begin{align}\tag{1}
(k+1)(2k+1) \cdots (nk+1) = \sum_{i=1}^n & \binom{n}{i} \left( \frac{i}{n}(k+2)-1 \right) \...
- 1,803
4
votes
2
answers
162
views
Proving $\sum_{k=0}^{m}\binom{n+k}{k}(1-x)^kx^{n+1}=1-\sum_{k=0}^{n}\binom{m+k}{k}x^k(1-x)^{m+1}$ without calculus
How would you prove this without calculus?
$$\forall m,n\in\Bbb N,\ \forall x\in\Bbb R,\ \sum_{k=0}^{m}\binom{n+k}{k}(1-x)^kx^{n+1}=1-\sum_{k=0}^{n}\binom{m+k}{k}x^k(1-x)^{m+1}$$
In this post it is ...
- 447
1
vote
1
answer
62
views
Is the minimum spanning tree always the optimal solution of spanning tree polytope?
I was studying the proof of $1.5$-Approximate Path TSP problem and found a tiny wrinkle that I just can't get over it.
In the proof it says that the minimum spanning tree found by standard MST ...
0
votes
0
answers
36
views
bijective proof that $\sum_{k=0}^n {2k \choose k} {2(n-k)\choose (n-k)} = 4^n$ [duplicate]
Provide a combinatorial proof that $\sum_{k=0}^n {2k \choose k} {2(n-k)\choose (n-k)} = 4^n.$
It might be easier to find a non-combinatorial proof first (e.g. a proof by induction). For the bijective ...
- 1,689
0
votes
0
answers
49
views
Solving $\sum_{k = 0}^{n} \binom{n}{k} \frac{1}{k+1} = \frac{2^{n+1}-1}{n+1}$ combinatorially? [duplicate]
I have solved $\sum_{k = 0}^{n} \binom{n}{k} \frac{1}{k+1} = \frac{2^{n+1}-1}{n+1}$ using integrals as follows: $$(1+x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k.$$$$\frac{(2)^{n+1}}{n+1} - \frac{1}{n+1} = \...
- 39
2
votes
0
answers
126
views
Probability of runs with cyclical criteria in Bernoulli trials
I am considering an extension of a previously posed problem, for which I have a hand-wave solution. I would like to determine whether the solution is exact and if not, need help with a rigorous ...
-1
votes
1
answer
34
views
arranging p numbered balls in n indistinguishable boxes [closed]
let pDn the number of ways to arrange p numbered balls in n indistinguishable boxes such that p is greater than or = n and no box is empty how to calculate pDp-1.
(I tried to dissect the problem and I ...
7
votes
2
answers
189
views
Combinatorial Interpretation of a partition identity
I am working on the book "Number Theory in the Spirit of Ramanujan" by Bruce Berndt.
In Exercise $1.3.7$: He wants us to prove that
$$
np\left(n\right) = \sum_{j = 0}^{n - 1}p\left(j\right)\...
- 401
1
vote
0
answers
54
views
Bounding this combinatorial sum
I'm looking to find a closed form expression or to bound the following sum
$$
\sum_{\atop \LARGE j\ =\ \left(k + 1\right)/3\ +\ 1}
^{\LARGE 2\left(k + 1\right)/3 \atop}
{i - 1 \choose j - 1}{n - {\rm ...
- 163
2
votes
5
answers
89
views
Prove that $2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$ using double counting. [duplicate]
Using a combinatorial proof (counting the same thing in different ways), show that:
$$2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$$
I was thinking of having some set $A$ where $|A| = n$, and then ...
- 79
0
votes
1
answer
42
views
Number of ways to choose $m$ boys and $k$ girls from $n$ boys and $n$ girls?
Suppose there are $n$ boys and $n$ girls and we want to choose $m$ boys and $k$ girls such that $k \le m$. Then there are $\binom{n}{m} \binom{n}{k}$ ways to do it. Now, using counting in two ways, I ...
- 1,243
0
votes
1
answer
42
views
Ways to colour elements of matrix using two colours
Let $A$ be a $n \times n$ matrix and suppose we want to colour elements of this matrix using black and white colours. Since each element can be either white or black, so total number of ways are $2^{n^...
- 1,243
2
votes
3
answers
91
views
How to prove the binomial identity $\binom{n + 1}{a + b + 1} = \sum_{k = 0}^n \binom{k}{a}\binom{n - k}{b}$
Prove the identity:
$$\binom{n + 1}{a + b + 1} = \sum_{k = 0}^n \binom{k}{a}\binom{n - k}{b}$$
So far I understand the left side represents how many ways there are picking a+b+1 elements from a set (...
- 33