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
0 answers
19 views

Help proving this combinatorics identity

Suppose $I_{N} := \{1,...,N\}$, $N \ge 1$, is a subset of $\mathbb{N}$ and $\mathcal{P}(I_{N})$ denotes the set of all subsets of $I_{N}$. Suppose we have a family of objects $\{f_{X}\}_{X\in \mathcal{...
user avatar
  • 1,429
3 votes
2 answers
524 views

$\sum_{A\in2^\Omega}P(A)=2^{|\Omega|-1}$ for probability space $(\Omega,2^\Omega,P)$ with finite $\Omega$

I'm looking for a combinatorial argument to complete a proof (below) of the following: Claim: If $(\Omega,2^\Omega,P)$ is a probability space with finite $\Omega,$ then $\sum_{A\in2^\Omega}P(A)=2^{|\...
user avatar
  • 12.6k
1 vote
1 answer
39 views

A combinatorial proof of a binomial coefficient summation identity. [duplicate]

$$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$ This is the exercise 3.3.6 of the book Invitation to Discrete Mathematics. The answer in book is Let M be an m-...
user avatar
0 votes
1 answer
49 views

Proving a Vandermonde-like combinatorial identity [duplicate]

I want to prove the identity $\sum\limits _{r=0}^{n} {{p+r} \choose {r}}\cdot {{q+n-r} \choose {n-r}}={{n+p+q+1} \choose n}$. I think induction does not work because replacing $n$ by $(n+1)$ we have $...
user avatar
4 votes
1 answer
224 views

Combinatorics explanation of Inclusion-Exclusion Principle Exactly-$m$ Properties Formula $E_m=\sum_{j=m}^n(-1)^{j-m}\color{blue}{{j\choose m}}S_j$

I'm trying to "explain" (I think this would not be a formal proof because I use a special case of the formula itself when I was "proving" it. So the tag I put might need to be ...
user avatar
0 votes
0 answers
39 views

An interesting case of regular family of regular functions.

I found this family of functions denoted by $W_{g,n}(z_1 , z_2, \ldots , z_n)$ which are regular appearances in the variable $a$ but I want to find a proof or argument for why this is happening. If ...
user avatar
  • 968
0 votes
1 answer
30 views

Periodicity of sub columns in Hadamard matrix

Let's consider the Hadamard transform $H_n$ where $H_{ij} = (-1)^{i.j}$. I want to count the number of repeated sub-columns of length $l$ in this matrix. Does it exist any formula or combinatorial ...
user avatar
1 vote
3 answers
64 views

finding a closed formula for $\sum_{k=0}^{n} k{2n \choose k}$

my attempt: $\sum_{k=0}^{n} k{2n \choose k}=\sum_{k=0}^{2n} k{2n \choose k}-\sum_{k=n+1}^{2n} k{2n \choose k}$ the first term in the right hand side suppose there are $2n$ poeple, we have to choose a ...
user avatar
1 vote
1 answer
60 views

How to prove that $1^2+2^2+\cdot\cdot\cdot+n^2=\frac{n(n+1)(2n+1)}{6}$ with a combinatorial proof [duplicate]

Prove that $1^2+2^2+\cdot\cdot\cdot+n^2=\frac{n(n+1)(2n+1)}{6}$ by using only Double Counting. (Hint: Count the triples of $(x,y,z)$ for some conditions) I can only prove the left side.
user avatar
1 vote
0 answers
30 views

Existing summation approach for computation of combination?

Recently, I bumped into an interesting approach to alternately calculate the combinations. But I am not sure if there is such theory already existing for generic combinations with arbitrary factorials....
user avatar
  • 613
0 votes
0 answers
50 views

Show that $\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n$ [duplicate]

I am trying to show that $$\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n.$$ I try $n=0$: $$ \sum_{k=0}^0 2^{-k}{k+n \choose k}=2^0{0 \choose 0}=1=2^0, $$ and $n=1$: $$ \sum_{k=0}^1 2^{-k}{k+n \choose k}=1+ 2^...
user avatar
0 votes
1 answer
40 views

To prove a condition on the contestants

A math contest consists of a Part-1 and a Part-2, with a combined total of 28 questions. Each contestant solved 7 problems altogether. For each pair of problems there were exactly two contestants who ...
user avatar
2 votes
1 answer
80 views

Show that $\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}$

I am trying to show that $$\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}.$$ When approaching these types of problems I always try to compute a few small, specific values myself just to get a better ...
user avatar
3 votes
2 answers
134 views

A double counting proof of a sum identity

I am trying to prove the following identity combinatorialy $$\sum_{k=0}^{n} \frac{(2n)!}{(k!)^2((n-k)!)^2}={2n \choose n}^2$$ The interpretation I have of the right side is that it was a $n \times n$ ...
user avatar
4 votes
1 answer
92 views

proof sum of power using Stirling number

question is prove $$ 1^{k} + 2^{k} + 3^{k} + \dots + n^{k} = \sum_{i=1}^{n} S(k,i) \cdot i! \cdot {{n+1}\choose{i+1}} $$ In my opinion, LHS means number of functions from X to Y (X has 'k' element and ...
user avatar
  • 53
0 votes
2 answers
63 views

Induction, combinatorics, inequality proof $\binom{2n}{n} < 2^{2n - 2}$ for all $n \geq 5$

Show that $\binom{2n}{n} < 2^{2n - 2}$ for all $n \geq 5$. Can I get some help please? I started by trying to prove this by induction, For the base case $n=5$, I showed the inequality is true. For ...
user avatar
12 votes
3 answers
375 views

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

Show : $$\sum_{k=0}^{n} k \binom{n+1}{k+1} n^{n-k} = n^{n+1}$$ for natural number $n$. I randomly discovered this identity, and managed to prove it using simple algebra. I tried a combinatorial proof ...
user avatar
  • 995
0 votes
0 answers
20 views

Proving the identity $\sum_{j = 0}^b(-1)^j{b \choose j}{n + j \choose 2b} = (-1)^b{n \choose b}$ [duplicate]

I want to prove the following identity: $$ \sum_{j = 0}^b(-1)^j{b \choose j}{n + j \choose 2b} = (-1)^b{n \choose b} $$ I know that the right-hand side is a weighted count of $b$-subsets of $n$. We ...
user avatar
  • 518
2 votes
3 answers
108 views

Probabilistic interpretation. Prove that $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^n$

Prove that $\sum_{k=0}^{n} \binom{n+k}{k} \frac{1}{2^k} = 2^n$ Well, the solution given on the book is as follows: We will solve this counting problem by a powerful and elegant interpretation of the ...
user avatar
  • 579
4 votes
2 answers
111 views

Proving the identity of $\sum_{k = 0}^n{4n \choose 4k} = 2^{4n - 2} + (-1)^n2^{2n - 1}$ combinatorially

I want to prove the following identity combinatorially: $$\sum_{k = 0}^n{4n \choose 4k} = 2^{4n - 2} + (-1)^n2^{2n - 1}$$ Here's my attempt so far: The left hand side is counting the number of teams ...
user avatar
  • 518
2 votes
1 answer
56 views

Minimal chain covering of all subsets of {$1,2,3,4,....,2n,2n+1$}

Let $n\in\mathbb{N^*}$ Let $M=${$1,2,3,....,2n,2n+1$} Let a chain be a family of $2n+2$ subsets of $M$ such that if $F=${$A_0,A_1,A_2,...A_{2n+1}$} is a chain, then $|A_i|=i$ for every $i\in${$0,1,2,.....
user avatar
  • 800
5 votes
3 answers
127 views

Combinatorial argument why is the following below true?

$\frac{12!}{2^6 \cdot 3! \cdot 3!} = {12 \choose 6} \cdot 5^2 \cdot 3^2 \cdot 1^2 $ I'm trying to formulate a combinatorial argument and have singled out a case of the two formulas above hoping to see ...
user avatar
  • 53
6 votes
1 answer
135 views

Combinatorial interpretation of a sum

I would like to know if there exists a way to interpret this sum by a combinatorial argument $$\sum _ { k = 0 } ^ { n } \frac { ( - 4 ) ^ { k } k ! } { ( 2 k + 1 ) ! ( n - k ) ! } = \frac { 1 } { ( 2 ...
user avatar
0 votes
1 answer
39 views

A combinatorial problem of counting path weights with a special symbolic binary tree

Consider two symbols, $X$ and $Y$. Symbol $X$ spawns $X$ and $Y$ -- think of the spawning as a binary tree rooted in $X$ with two leaves. The path weight for leaf $X$ is $a$ and that for leaf $Y$ is $...
user avatar
0 votes
1 answer
39 views

Number of distinct derivatives of order $n$ of an $m$-variable function

Advanced Calculus 2nd ed., by David Widder, says that the number of distinct (partial) derivatives of order $n$ of a (presumably smooth) function of $m$ variables is given by $$\binom{n+m-1}{n} = \...
user avatar
  • 1,316
1 vote
0 answers
46 views

Finding sum of Stirling numbers (signed) of the first kind $\sum_{k=0}^n s(n,k)$

Compute $\sum_{k=0}^n s(n,k)=\sum_{k=0}^n (-1)^{n-k}{n\brack k}$. From definition, it's clear than the sum of the unsigned Stirling numbers is: $$\sum_{k=0}^n {n\brack k}=n!$$ But I'm stucked at $\...
user avatar
-3 votes
2 answers
75 views

combinatorial proof of $\sum_{k=0}^n(1+(-1)^k)\binom{n}{k}4^{n-k}=5^n+3^n$ [closed]

$$\sum_{k=0}^n(1+(-1)^k)\binom{n}{k}4^{n-k}=5^n+3^n$$ I need to prove that the left side equals the right side and I'm not finding a head start for that, couldn't think of a way to start it or solve ...
user avatar
0 votes
0 answers
18 views

Proving $\sum_{i = 0}^k(-1)^i{n \choose i} = (-1)^k{n - 1 \choose k}$ combinatorially [duplicate]

I want to prove the following identity combinatorially: $$\sum_{i = 0}^k(-1)^i{n \choose i} = (-1)^k{n - 1 \choose k}$$ This question was asked Here but the presented proof was based on induction. I ...
user avatar
  • 518
0 votes
0 answers
27 views

Combinatorial interpretation of $(x+1)\binom{x+r}{x+1}=r\binom{x+r}{x}$ [duplicate]

Consider the identity: $(x+1)\binom{x+r}{x+1}=r\binom{x+r}{x}$ which is easy to verify algebraically. Is there a nice combinatorial proof of it? My thoughts were to reason as follows: Out of $x+r$ ...
user avatar
  • 9,807
3 votes
1 answer
202 views

XOR operation inner-product proof

Consider the binary power set $\underline{K}$ which contains binary strings of length $N$. Example: Let $N=3$, we then have $$\underline{K} = \big\{\{000\},\{100\},\{010\},\{001\},\{110\},\{101\},\{...
user avatar
2 votes
0 answers
42 views

Injection from tuples of subsets to others

Let $k$ be an integer and $[k] = \{1,2,...,k\}$. Let $\mathcal{A}$ be the set of tuples $(I_1, I_2, ..., I_{k+1})$ such that for all $j$, $I_j \subseteq [k]$ and $|I_j|$ is even. Also, let $\mathcal{...
user avatar
  • 519
0 votes
1 answer
50 views

Proof of $(n)_k = (n-1)_k + k(n-1)_{k-1}$ [duplicate]

I have to prove that this identity $(n)_k = (n-1)_k + k(n-1)_{k-1}$ is valid. I know that $(n)_k = \frac{n!}{(n-k)!}$, where should I look next?
user avatar
0 votes
2 answers
52 views

$k$-permutations combinatorial proof $P(n,k) = P(n-1,k) + k\cdot P(n-1,k-1).$

I'm currently working through Richard Hammack's Book of Proof. I'm a bit stumped on the combinatorial proof of $k$-permutations: Show that $$P(n,k) = P(n-1,k) + k\cdot P(n-1,k-1).$$ Can anyone give ...
user avatar
1 vote
2 answers
64 views

Proving the identity $\sum_{k = 1}^nk^2 {n \choose k}^2 = n^2{2n - 2 \choose n - 1}$ combinatorially

I want to prove the following identity combinatorially: $$\sum_{k = 1}^nk^2 {n \choose k}^2 = n^2{2n - 2 \choose n - 1}$$ We can introduce the following counting problem: How many ways are there to ...
user avatar
  • 518
0 votes
1 answer
44 views

Combinatorial argument for this problem:

Problem: find : $\sum_{r=0}^{21}\binom{42+r}{42}*\binom{42-r}{21}$ ,is there a combinatorial argument for this summation? My progress i realized that sum of upper terms in binomial is constant equal ...
user avatar
2 votes
2 answers
76 views

binomial identity: $\sum_{k=x+y}^{\infty}\binom{k-1}{y-1}\binom{k-y}{x}u^k = \binom{x+y-1}{y-1}\left(\frac{u}{1-u}\right)^{x+y}$?

I met a problem which gave me the left part, and I can compute left part and get right part by Mathematica. However, I don't know how to prove: $$\sum_{k=x+y}^{\infty}\binom{k-1}{y-1}\binom{k-y}{x}u^k ...
user avatar
1 vote
1 answer
63 views

Proving the identity $\sum_{k = r}^n {n \choose k}{k \choose r}2^k = {n \choose r}2^r3^{n - 2}$

I want to prove the following identity: $$\sum_{k = r}^n {n \choose k}{k \choose r}2^k = {n \choose r}2^r3^{n - 2}$$ I tried creating a counting problem: Suppose we have $2$ houses and $n$ people. But ...
user avatar
  • 518
0 votes
1 answer
38 views

Number of Subsets of Cardinality at most $k$ of a Finite Set

Let $I$ be a finite set, $k \in \mathbb{N}$ and $2 \leq k \leq \lvert I \rvert$. Then, the number of subsets of $I$ that have cardinality at most $k$ is bounded above by $\lvert I \rvert^k$, i.e. \...
user avatar
3 votes
2 answers
111 views

Integer partition generating functions problem

This is a homework question so I'd prefer to not receive a full solution but rather a hint. The question is that $r_3(n)$ denotes the number of partitions of an integer $n$ into parts that are not ...
user avatar
  • 286
2 votes
3 answers
70 views

Proving that ${n \choose 1} - 2{n \choose 2} + 3{n \choose 3} + \dots + (-1)^{n - 1}n{n \choose n} = 0$

I want to prove the following equality: $${n \choose 1} - 2{n \choose 2} + 3{n \choose 3} + \dots + (-1)^{n - 1}n{n \choose n} = 0$$ I tried taking the negative terms to the right hand side. The term $...
user avatar
  • 518
0 votes
0 answers
72 views

Elements of combinatorial analysis

How to use the given hint to answer this question? More Context for this question: This problem refers to the classical occupancy problem (Boltzmann-Maxwell statistics): that is, r balls are ...
user avatar
0 votes
1 answer
66 views

A giant cube is made of $n^3$ small cubes so that its dimensions are $nxnxn$. How many cubes of any size can be made of small cubes in the giant cube?

I am familiar with a similar problem that asks the number of squares that can be made in an $n x n$ chessboard. The answer was $\sum_{k=1}^{n} k^2$. I "feel" that the answer to the cube ...
user avatar
  • 43
0 votes
0 answers
18 views

Prove by counting in two ways: $\sum_{i=0}^{k} {m + k - i - 1 \choose k - i}{n + i - 1 \choose i} = {m + n + k - 1 \choose k}$ [duplicate]

$$\sum_{i=0}^{k} {m + k - i - 1 \choose k - i}{n + i - 1 \choose i} = {m + n + k - 1 \choose k}$$ I am familiar with proofs like this by simply substituting the choose values into the combination ...
user avatar
  • 43
-2 votes
2 answers
60 views

How can I prove $\Sigma ^{n-1} _{i=1} i = (^n _2)$? (n≥2) [closed]

// Through induction or combinatorial explanation, it doesn't matter. what I've done so far (through induction): Base: $\Sigma ^{2-1} _{i=1} i = 1 = (^n _2)$ Step: $\Sigma ^{n} _{i=1} i = (^n _2) + n ...
user avatar
1 vote
0 answers
47 views

Ballot problem but the probability that candidate B is ahead of candidate A

Alice and Bob are running for office. Alice receives a votes and Bob receives b votes, where a>b. The votes are counted one at a time. What is the probability that sometime during the counting Bob ...
user avatar
  • 43
4 votes
1 answer
112 views

Alternative way of writing the stars and bars formula where each bar is associated with at least one star.

I was looking for a different way of writing the formula of the number of different $k$-tuples of non-negative integers whose sum is equal to $n$ and I thought of this formula followed by this ...
user avatar
  • 51
1 vote
0 answers
34 views

Proving the identity $\sum_{i=0}^n{n + i \choose i}\frac{1}{2^i} = 2^n$ combinatorially [duplicate]

I want to prove the identity $\sum_{i=0}^n{n + i \choose i}\frac{1}{2^i} = 2^n$ combinatorially. I tried multiplying both sides of the equation by $2^n$ and obtained $\sum_{i=0}^n{n + 1 \choose i}2^{n ...
user avatar
  • 518
1 vote
1 answer
75 views

prove that $\sum_{k=0}^{n}S(n,k)(x)_k=x^n$

my attempt: assume there are a teacher decided to buy $n$ different types of chocolate and present it as a reward to the students who will give a correct answer to one of the questions. The number of ...
user avatar
3 votes
1 answer
98 views

${ n \choose k}={ n-1 \choose k-1}+{ n-2 \choose k-1}+{ n-3 \choose k-1}+...+{ k-1 \choose k-1}$

i tried to prove this by using the concept of composition ${ n \choose k}={ n-1 \choose k-1}+{ n-2 \choose k-1}+{ n-3 \choose k-1}+...+{ k-1 \choose k-1}$ my attempt: for explain my idea let's take $ ...
user avatar
2 votes
1 answer
35 views

Counting exactly 5 spades from 6 cards

In the question, we are given that the LHS of the equation (in the link above) is equivalent to the probability of drawing exactly 5 spades when drawing 6 cards from a standard 52 card deck, and we ...
user avatar
  • 23

1
2 3 4 5
20