Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc. They avoid complicated algebraic manipulations.

learn more… | top users | synonyms

3
votes
1answer
45 views

Elementary proof for average number of tree components in a random forest of fixed size

In Flajolet's & Sedgewick's "Analytic Combinatorics" I found the statement that for a forest ("Catalan", i.e. collection of ordered trees) of size $n$, uniformly distributed, the number of tree ...
0
votes
1answer
51 views

What at the chances of getting 20 heads on a row if tossed 100 million times? [duplicate]

I understand that each toss has a 50% chance if it is a fair coin, but I have hard time grasping the law of great numbers and I would like to know how likely it is that I get 20 heads in a row in such ...
1
vote
0answers
46 views

Combinatorial analysis

There are $20$ children in a lost ship. They do not remember their birthdays but would like to be assigned with one. 1. In how many ways this can be done so that exactly $2$ children will get ...
7
votes
4answers
707 views

Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$

I recently came across a question while studying for an exam. I haven't been able to solve it. We had to prove: $$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$ We had to use counting techniques. This was ...
3
votes
1answer
55 views

Combinatorial proof for a non obvious binomial identity

I think I got some serious problem with those combinatorial proofs. Why would the following be true ($1\leq r\leq k\leq n$): $$\sum_\limits{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}?...
0
votes
2answers
68 views

Combinatorial identity $\sum_{k=0}^{n}\frac{n-k}{k+1}\binom{n}{k}^2 = \binom{2n}{n-1}$

I have an identity $$\sum_{k=0}^{n}\frac{n-k}{k+1}\binom{n}{k}^2 = \binom{2n}{n-1}$$ for which I'm looking for a combinatorial proof. Any ideas? I was thinking about separating $2n$ on boys and ...
0
votes
2answers
42 views

Counting arguments question about sums of binomial coefficients [duplicate]

Use counting arguments to prove these identities: I don't know how to type this: it is two numbers in brackets the first on top of the other, but there is no fraction line. Here is an image of both of ...
5
votes
1answer
66 views

Combinatorial proof of a certain alternating sum of binomial coefficients

The following identity appeared as a question earlier today $$\displaystyle\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = \begin{cases} 1\ \text{if}\ n=0 \\ 0\ \text{if}\ n>0 \end{...
4
votes
2answers
46 views

Must the number of people…

Must the number of people at the party who do not know an odd number of people be even? Describe a graph model and then answers the question. I'm confused because I do not understand the question. ...
0
votes
1answer
19 views

calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$

Is there any formula for calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$?
2
votes
1answer
42 views

Prove that $\sum_{a_1+a_2+a_3=n}{n \choose {a_1,a_2,a_3}} = 3^n$

I am trying to find a combinatorial proof for the following expression $$\sum_{a_1+a_2+a_3=n}{n \choose {a_1,a_2,a_3}} = 3^n.$$ I have been stuck on this for a while, is there anyone who can help ...
0
votes
3answers
59 views

Explanation of an Easy Proof of Variance of Bernoulli Trials

I am taking a course in Combinatorics, and I've got two proofs I can use to support the Bernoulli trial variance formula, $\operatorname{var}(X) = np(1-p)$, and I would like to use the one where I don'...
8
votes
2answers
113 views

How can I get f(x) from its Maclaurin series?

I know how to get a Maclaurin series when $f(x)$ is given. I have to find $\sum_{n=0}^{\infty}\frac{f^{(k)}(0)}{k!}x^k$. But how can I get $f(x)$ from its Taylor series? The problem is $$f(x) = \...
1
vote
2answers
37 views

Proving $\left(\binom{n}{k}\right)=\left(\binom{n-1}{0}\right)+\left(\binom{n-1}{1}\right)+\cdots+\left(\binom{n-1}{k}\right)$

Here, $\left(\binom{n}{k}\right)$ denotes the number of multisets in $N$ with length $k$. I can prove it using the fact that $\left(\binom{n}{k}\right) = \binom{n+k-1}{k}$ but I want another access. ...
-3
votes
2answers
75 views

Combinatorial proof of multiset coefficient identity: $\left(\!\left({n\atop k}\right)\!\right)= \left(\!\!\left({k+1\atop n-1}\right)\!\!\right)$ [closed]

I would like a combinatorial proof of this identity for multiset coefficients: $$\left(\!\left({n\atop k}\right)\!\right) = \left(\!\!\left({k+1\atop n-1}\right)\!\!\right)$$ It is not famaliar ...
0
votes
0answers
22 views

How can I prove that a function is 1-1 and onto in Combinatorial Proof

I studied the way of combinatorial proof for a=b. That is, 1) Find sets A and B such that |A|=a, |B|=b 2) Construct a bijection between A and B Then |A| = |B|. But I have a difficulty in proving a ...
0
votes
1answer
57 views

A combinatorial proof of an identity involving Euler’s $ \phi $-function.

My assignment is to prove this: Problem. For an integer $ n \geq 1 $, show that $ \displaystyle n = \sum_{d|n} \phi \! \left( \frac{n}{d} \right) $. I have a hint: Define an equivalence relation ...
2
votes
1answer
62 views

Combinatorial proof of an identity between restricted counts of permutations and derangements

In an answer to Counting permutations with given condition, I showed that the number of permutations of $k$ elements that satisfy $\sigma(i+1)\ne\sigma(i)+1$ is $\frac{!(k+1)}k$, which is the number ...
6
votes
1answer
60 views

Combinatorial argument for $1+\sum_{r=1}^{r=n} r\cdot r! = (n+1)!$ [duplicate]

Combinatorial argument for $$1+\sum\limits_{r=1}^{r=n} \ r\cdot r! = (n+1)!$$ The algebraic proof is easy as $r=(r+1)-1$.
4
votes
4answers
114 views

Can anyone give a combinatorial proof of the identity ${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+…+(n-m+1){m \choose m}={n+2 \choose m+2}$

Can anyone give a combinatorial proof of the identity $${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+\ldots+(n+1-m){m \choose m}={n+2 \choose m+2}$$ I am finding difficult as $n$ is varying ...
22
votes
1answer
347 views

Two interview questions

I recently came across two interview questions for admission in B.Math at an university. I gave the two questions a try and want to know if my solutions are correct or not. Q1: Given that $x^4-4x^3+...
11
votes
1answer
217 views

Does the functional equation $p(x^2)=p(x)p(x+1)$ have a combinatorial interpretation?

A recent question asked about polynomial solutions to the functional equation $p(x^2)=p(x)p(x+1)$. Subsequently, Robert Israel posted an answer showing that solutions are necessarily of the form $p(x)=...
1
vote
3answers
64 views

n(n+1)/2 combinatorial proof (details in description)

Find the number of $2$-lists $(π‘Ž, 𝑏)$ we can form using the numbers $0,1,2,...,𝑛$ with $π‘Ž < 𝑏$. a. Show that the number is $𝑛(𝑛 + 1)/2$ by considering the number of $2$-lists $(π‘Ž, 𝑏)$ in ...
1
vote
0answers
21 views

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$ [duplicate]

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$. Typically to combinatorially prove something we need to show that the LHS indeed counts the same ...
1
vote
2answers
63 views

Proof with Combinatorial Argument $\sum_{i = 1}^{n} (i-1) = nC2$

I am trying to prove below equation with combinatorial argument but I have no idea how this works. $$\sum_{i = 1}^{n} (i-1) = nC2$$ Can anyone give me a clue?
4
votes
2answers
127 views

Seeking non-inductive, combinatorial proof of the identity $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

How do you prove $$1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}$$ without induction? I'm looking for a combinatorial proof of this.
0
votes
0answers
24 views

CoQ and “Method of Coefficients”

I have been trying to use the Method of Coefficients in some combinatorial arguments. Since the result ended up being more complicated than I am comfortable with I would like to know if there is ...
1
vote
2answers
107 views

What is a combinatorial proof exactly?

It almost seems as though a combinatorial proof is "Explain the intuition behind this relationship (using normal words) to explain why it is true." I'm a little lost as to how this is a proof ...
7
votes
2answers
234 views

Combinatorial proof that $\frac{({10!})!}{{10!}^{9!}}$ is an integer

I need help to prove that the quantity of this division : $\dfrac{({10!})!}{{10!}^{9!}}$ is an integer number, using combinatorial proof
4
votes
1answer
79 views

Calculating the value of $\lfloor(1+\sqrt{2})^{2n}\rfloor$

Problem: Calculate the value of $\lfloor(1+\sqrt{2})^{2n}\rfloor$ where $n$ is an arbitrary non-negative integer and $\lfloor x\rfloor$ indicates the largest integer not greater than $x$. What I ...
4
votes
2answers
94 views

closed form of $\sum_{k=0}^n {2n\choose 2k}2^k$

Is it possible to find a closed form for the expression below? $$\sum_{k=0}^n {2n\choose 2k}2^k$$ I have tried counting in two ways but made no progress. And I don't know any combinatorial ...
5
votes
3answers
145 views

Combinatorial argument for an identity

Consider the following equation: $x_1 + x_2 + \cdots + x_r = n,~~$ where $~~0\leq x_{i}\leq n, \forall i$ The number of integral solutions to the above equation = ${n+r-1 \choose r-1}$. Consider ...
1
vote
1answer
98 views

Seeking a combinatorial proof $\sum _{k=0}^n (n-2k)^3\binom{n}{k}=0$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$ $$\sum _{k=0}^n (n-2 k)^3 \binom{n}{k}=0$$
2
votes
2answers
82 views

Prove this binomial identity using the following equality:

Use the equation $\frac{(1-x^2)^n}{(1-x)^n} = (1+x)^n$ to prove the following identity: $\displaystyle \sum_{k=0}^\frac{m}{2}(-1)^k{n\choose k}{n+m-2k-1\choose n-1}={m\choose n}$, $m\leqslant n$ and $...
3
votes
2answers
77 views

Combinatorics Identity about Catalan numbers.

I need to prove this identity: $\sum_{k=0}^n \frac{1}{k+1}{2k \choose k}{2n-2k \choose n-k}={2n+1 \choose n}$ without using the identity: $C_{n+1}=\sum_{k=0}^n C_kC_{n-k}$. Can't figure out how to....
0
votes
1answer
143 views

Prove combinatorial Identity using a combinatorial argument. [duplicate]

I have proved by induction on k that : $$ \binom{n}{n} + \binom{n+1}{n} + \binom{n+2}{n}+ ... + \binom{n+k}{n} = \binom{n+k+1}{n+1} $$ But now, I need to prove it using a combinatorial argument. ...
0
votes
2answers
28 views

Need help in following problems related to combinatorial analysis.

How many motorcycle number plates can be made if each plate contains 2 different letters followed by 3 different digits? How many four code words are possible using the letters in COMPUTE if (a) the ...
1
vote
3answers
204 views

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$.

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$ using the Pigeonhole principle. I am supposed to identify the pigeons and the pigeonholes. ...
0
votes
2answers
60 views

Deduce formula for $\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}$

I am working on the following problem: For each $m$ we have found the values of $$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$ for polynomials of degree at most m. Use a combinatorial story to ...
0
votes
0answers
38 views

Can we simplify this factorial summation $\sum_{i=0}^{n-1} i!(n-i)!$?

I've just solved a combinatorics problem but my answer is stuck here: $$\sum_{i=1}^{n-1} i!(n-i)!$$ Is there any way to simplify this summation? I've thought about combinatorial proof but there's no ...
4
votes
2answers
174 views

Seeking a combinatorial proof $\sum _{k=0}^n (n-2k)^2\binom{n}{k}=n\times 2^n$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$ $$\sum _{k=0}^n (n-2 k)^2 \binom{n}{k}=n\times 2^n$$
4
votes
1answer
65 views

Prove $\sum_{k=0}^n\binom{2n+1}{2k}=4^n$

I once had to show that $\cos(x)\sin(x)=\frac{1}{2}\sin(2x)$ using the Cauchy product and relied on $$\sum_{k=0}^n\binom{2n+1}{2k}=4^n.$$ However I never came up with a proof why this is true - is ...
3
votes
2answers
71 views

$\binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$

Prove combinatorially (using inclusion-exclusion) that$ \binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$ Hi, everyone. I'm at a loss here. I've been trying ...
0
votes
1answer
54 views

Combinatorial Proof of $Q_n = D_n + D_{n-1}$ [duplicate]

Let $Q_n$ be the number of permutation of $n$ integers $\{1, 2, \cdots, n \}$ such that, in the permutation, every $i$ is not succeeded by $i+1$ and let $D_n$ be the number of derangement of $n$ ...
-4
votes
1answer
84 views

Show that $\binom{n}{k}$ equals to $\binom{n-1}{k}\cdot\frac{n-k+1}{k}$. [closed]

It should be solved by using combinatorial proofs.
4
votes
4answers
164 views

Permutation of multiset

How many 8-permutation are there of the letters of the word 'ADDRESSES'? My textbook suggests that we should divide the situation into cases where a different letter is removed. In other words, ...
2
votes
4answers
438 views

prove the combinatorial identity: $ {2n \choose n} + {2n\choose n-1} = (1/2){2n + 2 \choose n + 1}$

So the first thing I did was to multiply and then isolate the left-most term. That leaves me with $$ 2{2n \choose n} ={2n + 2\choose n + 1} - 2{2n \choose n -1} $$ No specific reasoning except that ...
4
votes
3answers
335 views

Algebraic and combinatorial proof of an identity

For any two integers $2 \le k \le n-2$, there is the identity $$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$$ a) Give an algebraic proof of this identity, writing the binomial ...
5
votes
4answers
274 views

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$ [duplicate]

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant ...
1
vote
1answer
58 views

On an estimation of binomial coefficient

On page 14 of the book 'Proofs from THE BOOK', there is an estimation presented as: $$\binom{2n}{n}\le \prod_{p\le \sqrt{2n}}\ 2n. \prod_{\sqrt{2n}<p\le \frac{2}{3}n}\ p. \prod_{n<p\le 2n}\ p, $...