Stack Exchange Network

Stack Exchange network consists of 174 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.

7
votes
0answers
59 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$. ...
0
votes
2answers
38 views

How to make any natural numbers (placed in the chessboard cells) divisible by 10 by using the given tools [closed]

The original condition is: In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a ...
3
votes
1answer
64 views

Combinatorial Proof that $p(n)/(1+\epsilon)^n \to 0$

I was thinking this morning about the identity $ \prod_{n=1}^{\infty} \left( \frac{1}{1-q^n} \right) = \sum_{n=0}^{\infty} p(n) q^n$. The product on the left converges for $|q|<1$, which implies ...
3
votes
2answers
138 views

Identity involving difference of binomial coefficients

I am trying to prove the following identity but not sure how to prove it. [The followings are equivalent forms of the original equality I asked.] $$ \binom{m+n}{s+1} - \binom{n}{s+1} = \sum_{i=0}^s \...
0
votes
2answers
8 views

Combinatorial proof that the number of even cardinality subsets is equal to the number of odd cardinality subsets

Given a set of cardinality $n\geq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality I am looking for a combinatorial proof of this statement- I know ...
2
votes
2answers
53 views

Proving $\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$

Use any method to prove that $$\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$$ My Try: Base case: Let $m=1$ LHS$$\binom{n+1+m}{n+1}=\binom{n+2}{n+1}=(n+2)$$ RHS$$\sum_{k=0}^m(k+1)\binom{n+...
0
votes
1answer
24 views

Pigeonhole Principle: Proof that in an isosceles triangle with both side lengths 2 amongst 5 random points within there's two with distance $d < 1$

We're tasked to prove using the pigeonhole principle that, given an isosceles triangle with the two equal side lengths being $l = 2$, you can always choose $5$ random points of which two will have a ...
1
vote
3answers
60 views

value of $k$ in binomial expression

If $\displaystyle \binom{404}{4}-\binom{4}{1}\cdot \binom{303}{4}+\binom{4}{2}\cdot \binom{202}{4}-\binom{4}{3}\cdot \binom{101}{4}=(101)^k.$ Then $k$ is Iam trying to simplify it $\displaystyle \...
1
vote
1answer
26 views

Words of weight 5 in in Ternary Golay Code

I'm not really good at doing this type of exercices. But I'd like to know how to prove that ther are 132 words of weight 5 in the Ternary Golay Code. I am not allowed to use the weight enumerator. I ...
3
votes
0answers
44 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
3answers
41 views

Is it possible to show ${k\choose 2} \ge \sum_{i } {x_i\choose 2} $ such that $\sum_i x_i =k$

I want to know if this problem can be verified or rejected. ${k\choose 2} \ge \sum_i {x_i\choose 2 }$ such that $\sum_i x_i =k$ and $x_i, \;k\in \mathbb N.$ For example $2+3=5$ and ${5 \choose 2}...
1
vote
1answer
54 views

Show that $1= \sum_{k=0}^{m} (-1)^k {m \choose k}2^{m-k}$ using sign reversing involution

Using the sign reversing involution, how can I show that $$1= \sum_{k=0}^{m} (-1)^k {m \choose k}2^{m-k}.$$ I have been trying to figure out the what the signed sets are namely $S^{ +}$ and $S^{ -}$. ...
1
vote
2answers
28 views

Proving that these two finite alternating series are equal.

For all natural numbers $n$, prove that $$ \sum_{r=0}^n \left( \frac{ (-1)^r {n \choose r} } {2r+1} \right) = 4^n \sum_{r=0}^n \left( \frac{ (-1)^r {n \choose r} } {n+r+1} \right)$$ I have tried to ...
0
votes
0answers
321 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}{(...
2
votes
1answer
21 views

How many ways 3 persons A, B , C can be put in a row of six empty chair such that A nd B don't sit together

How many ways 3 persons A,B and C can seat in a row of six empty chairs such that A and B don't sit together? My Attempt Let us introduce three more persons D, E and F. Then these six persons can be ...
18
votes
2answers
321 views

Is there a combinatorial proof that $e$ is finite?

I'm looking for an integer $N$ and a combinatorial proof either that $(n+1)^n<Nn^n$ or that $\sum_{k=0}^n \frac{n!}{k!}<N\cdot n!$. By "combinatorial proof of $a<b$" I mean exhibiting ...
1
vote
0answers
77 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+...
0
votes
1answer
58 views

Combinatorial proofs of several binomial sums

I would like to ask if you know of any combinatorial (double counting) arguments for finding a closed formula for the following sums: $\sum_{k=m}^n{k\choose m}{n\choose k}$, where ${n\choose k} = 0$ ...
2
votes
2answers
82 views

Lower Bound on God's Number in the Rubik's Cube

I'm trying to write a project about the Rubik's Cube, and althought it's easy to find out the lower bound (using half turns) is 18, finding a precise proof hereof seems impossible. How does one proof ...
1
vote
0answers
48 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 ...
4
votes
0answers
107 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 ...
2
votes
1answer
35 views

Using the Langrange Inversion Formula

I am currently going through the proof of the Theorem $5.4.2$ on page 38 of Enumerative Combinatorics Vol $2$ by R. Stanley and I think I understand the proof. The proof of Corollary $5.4.3$ as shown ...
2
votes
3answers
134 views

Proving If $k \le \left\lfloor \frac{n}{2} \right\rfloor$ then $\binom{n}{k-1} < \binom{n}{k}$

So I'm trying to do a proof for this problem: If $\displaystyle{k \le \left\lfloor \frac{n}{2} \right\rfloor}$ then $$\displaystyle{\binom{n}{k-1} < \binom{n}{k}}$$ I can do it algebraically but ...
0
votes
0answers
28 views

Combinatorial identity $\sum_{j=i}^n \begin{pmatrix} j-1 \\ i-1 \end{pmatrix} = \begin{pmatrix} n \\ i \end{pmatrix}$ [duplicate]

prove $$\sum_{j=i}^n \begin{pmatrix} j-1 \\ i-1 \end{pmatrix} = \begin{pmatrix} n \\ i \end{pmatrix}$$ What I am doing now is to time $i$ on both side and try to argue out of this: $$\sum_{j=i}^n i \...
3
votes
0answers
69 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}...
6
votes
2answers
216 views

Combinatorial meaning of $L_m=S_m-{m\choose m-1}S_{m+1}+{m+1\choose m-1}S_{m+2}\mp\dots+(-1)^{n-m}{n-1\choose m-1}S_n$

I want to understand the meaning behind the coefficients of the following formula, $L_m$: Let $U$ be a finite set, and there are $n$ properties defined on it: $a_1,a_2,\dots,a_n,$ and let $S_m$ ...
1
vote
1answer
43 views

How to seat guests in circles of chairs if each one wants to have free seats to his left and right?

This is a task I saw in a programming competition. So, you're given a list of guests. Each $i$th guest wants to have $l_i$ free spots to his left and $r_i$ free spots to his right, because they are ...
4
votes
2answers
192 views

Proving formula sum of product of binomial coefficients

I have to proof the following formula \begin{align} \sum_{k=0}^{n/2} {n\choose2k} {2k\choose k} 2^{n-2k} = {2n\choose n} \end{align} I tried to use the fact that ${2n\choose n} = \sum_{k=0}^{n} {n\...
1
vote
1answer
54 views

Derangement with constraints

$9$ letters and $9$ envelopes are denoted by $\{A, B, C, D, \ldots, I\}$ and $\{a, b, c, \ldots, i\}$ respectively. To find the number of ways so that no letter goes into right envelope but given ...
0
votes
1answer
86 views

Combinatorics contest math question [closed]

James has a red jar,a blue jar and a pile of 100 pebbles.Initially both jars are empty. A move consists of moving a pebble from the pile into one of the jars or returning a pebble from one of the jars ...
4
votes
4answers
103 views

Proof of a combination identity: $\sum\limits_{i=0}^m\sum\limits_{j=0}^m\binom{i+j}{i}\binom{2m-i-j}{m-i}=\frac {m+1}2\binom{2m+2}{m+1}$

I'm studying the special case of question Finding expected area enclosed by the loop when $m=n$ and $A=2n$. I found $f_{n,n}(2n)=S(n-2)$, where $S$ is defined as $$S(m)=\sum_{i=0}^m\sum_{j=0}^m\...
1
vote
1answer
80 views

How can I represent following series as a formula?

(This is not an assignment question. It is part of my research, and while solving my case, I come with the following. This analytical thing proves with my simulation. But to write a paper, I need to ...
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 ...
5
votes
2answers
64 views

Proving that $\sum_{n=0}^r (-1)^n \binom{r}{n} (s+r-n-1)!/(s-n)! = 0$ without Taylor expansion

Let $0<r\leq s$ be two integers. I would like to prove that the sum $$\sum_{n=0}^r(-1)^n \binom{r}{n} \frac{(s+r-n-1)!}{(s-n)!}$$ is equal to zero. One possible way to prove this is to use the ...
2
votes
0answers
82 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 ...
0
votes
0answers
46 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 ...
2
votes
1answer
55 views

How can I deduce (3.6) from (3.5)?

My attempt:- I could verify the above formula for $f\in A_2(V) $ and $g\in A_1(V)$ and vise versa. I know the fact that number of even permutation in $S_{k+l}$ is $\frac{(k+l)!}{2}$. So, sgn($\...
2
votes
0answers
99 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
1answer
55 views

All distinct k-permutations of length n, with repetitions

Given $n$ elements and an integer $k > 0~(k \leq n)$, find the number of all distinct strings of length $n$, formed by any $k$-out-of-$n$ distinct symbols (i.e., $k$-permutations of length $n)$. ...
1
vote
1answer
56 views

Number of distinct strings 'covering' all strings of same length, with restricted index selection.

A string $x \in n^n$ 'covers' another string $y \in n^n$ if $x$ contains all the symbols that constitute $y$. For eg., $x = abcdeb$ covers $y = aaacbc$. The problem is to derive a formula to count the ...
0
votes
1answer
94 views

The VC dimension of convex d-gons

The VC dimension of convex $d$-gons is $2d+1$. To show that, I can prove the lower bound is $2d+1$. however, I don't know how to prove the upper bound in a rigorous way. For low bound, I construct a ...
1
vote
2answers
69 views

Choosing 80 from 100

First question, i hope i follow the rules accordingly I tried choosing 80 numbers from the ${{1,...,100}}$ set in two ways: The first is 100 choose 80: $$\binom{100}{80} = 535983370403809682970$$ ...
0
votes
1answer
30 views

Find a recurrence relation that gives a formula for the number of arrangements of wins and losses for aN (you stop playing at 3 losses in a row).

Problem Since it’s a wise idea to have a stopping condition when gambling, a gambler decides to play a game until they lose three times in a row. Let W and L denote wins and losses respectively, and ...
4
votes
3answers
126 views

Spivak's Calculus: Proofs concerning Pascal's Triangle

Problem 3 of Chapter 2 in Spivak's Calculus poses 5 problems associated with Pascal's Triangle. The first of these asks you to prove that $\binom{n+1}{k}$ = $\binom{n}{k-1} + \binom{n}{k}$ which was ...
1
vote
2answers
93 views

Sum of coefficients of even powers of x in $(1+x)^5 (1+x^2)^5$?

the exact question is asking the sum of coefficients of even powers of x in the expansion of $(1+x+x^2+x^3)^5$ and in the solution this expression is simplified to $(1+x)^5(1+x^2)^5$. The solution to ...
5
votes
2answers
202 views

Combinatorial proof of $\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}} = {{n+p} \choose p}^2$

(Valid for $n\geq p \geq 1$) Basically, I'd like to exhibit two sets, one with cardinality ${{n+p} \choose p}^2$, another one with cardinality $\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}}$ ...
0
votes
0answers
49 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 ...
1
vote
4answers
101 views

Finding value of $\sum^{10}_{k=2}\binom{k}{2}\binom{12-k}{2}$ [closed]

Finding value of $$\sum^{10}_{k=2}\binom{k}{2}\binom{12-k}{2}$$ Solution I tried: $$(1+x)^{10}=1+\binom{10}{1}x+\binom{10}{2}x^2+\cdots +\binom{10}{10}x^{10}$$ $$(x+1)^{10}=x^{10}+\binom{10}{1}x^9+...
0
votes
1answer
111 views

British Maths Olympiad (BMO) 2003 Round 1 Question 4 what is wrong with this approach, can it be fixed?

The questions states: A set of positive integers is defined to be $wicked$ if it contains no three consecutive integers. We count the empty set, which contains no elements at all, as a $wicked$ ...
0
votes
0answers
31 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 ...