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
0
votes
1answer
32 views

How many different three-digit numbers can I make with three 3s, two 2s, and one 1?

How many different three-digit numbers can I make with three 3s, two 2s, and one 1? I'd like to use actual calculations instead of just counting them all. What I am curious about is how am I supposed ...
-2
votes
0answers
21 views

Combinatorial proof/Algebraic proof of these two binomial identities [duplicate]

$$\sum_{j=0}^{k}{(-1)^{k-j}\binom{n}{j}}=\binom{n-1}{k}$$ and $$\sum_{j=0}^{k}{(-1)^j\binom{n}{j}}=(-1)^k\binom{n-1}{k}$$ what i did was do induction to prove this ,but is there a proper ...
-1
votes
0answers
46 views

PNC Induction Question [closed]

Consider the number C( n , r) given by C( n , r ) = n ! / ( n − r ) ! · r !, where n and r are integers satisfying n ≥ 1 and n ≥ r ≥ 0 ( recall that 0 ! = 1 ). (i) Suppose that n ≥ 2 is an even ...
1
vote
1answer
57 views

number of factorization of a square-free number

Is there a way to count the number of factorizations of a square-free number $n$? A square-free number is defined as an integer which is divisible by no perfect square other than $1$
0
votes
1answer
30 views

Prove in a combinatorial way (for example using an argument with committees) for the Identity [duplicate]

$$\sum^{n}_{k=2}k(k-1)\binom{n}{k} =n(n-1)2^{n-2}$$ $$n \geq 2$$ I'm recently new learning combinatorics and having trouble understand the intuition behind this. I don't either know what's ...
0
votes
0answers
43 views

Finding Generating Function of Series, Coefficients Relate to Partitions

Let $\displaystyle p_{\leq c}(n)$ represent the number of partitions of $n$ into at most $c$ parts. What is the generating function of $\displaystyle\sum_{n \geq 0} p_{\leq c}(n)x^n$? I'm completely ...
-3
votes
1answer
30 views

How to proof $\sum_{k=1}^n k {n \choose k }=n 2^{n-1}$ [duplicate]

I have tried trying to find a pattern but i don't believe that the right way. If you help me it would be great.
5
votes
4answers
110 views

How to find $\sum_{r\ge 0} \binom{n}{r}\binom{n-r}{r} 2^{n-2r}$?

Problem was to find $$\sum_{r\ge 0} \binom{n}{r}\binom{n-r}{r} 2^{n-2r}.$$ My partial progress i tried to motivate such that upper term in binomial terms gets constant rather than variable , so i ...
0
votes
1answer
43 views

Show $\sum_{k \geq 0}\binom{n}k \left((-1)^k+1\right)x^k = 2\sum_{k \geq 0}\binom{n}{2k}x^{2k}$

Hello I am trying to understand the following proof: $$\begin{align*} (1-x)^n+(1+x)^n &= \sum_{k \geq 0}\binom{n}k (-1)^kx^k + \sum_{k \geq 0} \binom{n}k x^k\\ &= \sum_{k \geq 0}\binom{n}k \...
2
votes
0answers
24 views

How to prove that two Latin squares $P$ and $Q$ are orthogonal if and only if $P^{-1}Q$ is a Latin square?

The inspiration of my question comes from Henry B. Mann's 1942 paper The Construction of Orthogonal Latin Squares. My goal is to add rigor to Mann's explanation that two Latin squares $P = (P_1,P_2,......
5
votes
0answers
88 views

Prove that: $ \sum_{i = 0}^k {n \choose i} = \sum_{i = 0}^k {n - 1 - i \choose k - i}2^i $ [duplicate]

I've been stuck with problem for quite a while: Prove that: $$ \sum_{i = 0}^k {n \choose i} = \sum_{i = 0}^k {n - 1 - i \choose k - i}2^i $$ for $k$ in $\{0,\dots,n-1\}$. I would love to get a hint ...
4
votes
0answers
70 views

Reference request for an identity involving Catalan numbers

I am wondering if a bijective proof of the following identity involving Catalan generating functions has appeared anywhere in the literature. (It's not difficult to simply verify it for the functions ...
2
votes
2answers
76 views

Estimating alternating sum of product of binomial coefficients $\sum_{i=0}^{k-1} \binom{n}{m+i} \binom{m+i}{k} \binom{k-1}{i} (-1)^i$

I am interested in getting a lower bound on the expression $$\sum_{i=0}^{k-1} \binom{n}{m+i} \binom{m+i}{k} \binom{k-1}{i} (-1)^i .$$ for $1 \le k,m \le n$. In particular, $m = n/2 + C\sqrt{n}$ for ...
1
vote
1answer
54 views

Seeking a combinatorial proof $\binom{n}{2k-1}=\binom{n+2}{2k+1}-2\times\binom{n+1}{2k+1}+\binom{n}{2k+1}$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof that for all $n,k\in \mathbb{N}$, following holds $$\binom{n}{2k-1}=\binom{n+2}{2k+1}-2\times\...
0
votes
0answers
29 views

How do I prove combinatorically that $\binom{r}{r}+\binom{r+1}{r}+…+\binom{n}{r}=\binom{n+1}{r+1}$? [duplicate]

I tried counting subsets with r+1 elements from the set {1,2,....n, n+1} which gives RHS. However I could not come up with an answer corresponding to LHS. $$\binom{r}{r}+\binom{r+1}{r}+...+\binom{n}{r}...
2
votes
3answers
64 views

Show $S_n=-nS_{n-1}+n\sum_{k=0}^n (-1)^k\binom{n}{k}k^{n-1},\quad n\ge1$

I'm stuck in this question. It seems so easy, but I can't see it and at this point I spent too many time on it to be able to look at it with fresh eyes. For each $n\in N$, consider: $$S_n=\sum_{k=0}^n ...
10
votes
1answer
361 views

Length of continued fractions

Consider, for any pair of relatively prime positive integers $0 <j <n$, the expansion as a continued fraction of the quotient $\frac{n}{j}$ $$ \frac{n}{j}=b_1-\frac{1}{b_2-\dfrac{1}{\cdots-\...
0
votes
0answers
31 views

Would the solution to this counting problem be correct?

Suppose we have an inexhaustible amount of black beads, white beads, and $n-k$ other colors of beads (red, blue, green, etc., etc.) (By "inexhaustible" it is meant that "at least $k$ ...
-2
votes
2answers
53 views

Simplifying ${n \choose k} 2^k (n-k)_k$, where $(n)_i$ is the falling factorial [closed]

Is there a different way of writing $${n \choose k} 2^k (n-k)_k$$ where $(n)_i = n(n-1)(n-2)\cdots(n-i+1)$ is the falling factorial? One source says $$\frac{n!}{k!(k-1)!}2^k$$ and another says it is ...
3
votes
1answer
40 views

The number of binary sequences generated by a parity map from all integer partitions of $n$ and their permutations

Let $n$ be an integer and $n=(n_1,\dots,n_n)$ all its partitions. The partitions with less than $n$ integers (all but one) are padded by zeros from the left AND sorted such that first come even ...
0
votes
1answer
65 views

Simplifying binomial series

I am stuck with a series that I want to simplify- $${2n+1\choose 0} + {2n+1\choose 1} + {2n+1\choose 2} + \dots +{2n+1\choose n}$$ I think somehow the result $${n\choose 0} + {n\choose 1} + {n\choose ...
1
vote
1answer
34 views

deduce Fermat’s Little Theorem from combinatorial problem

• We wish to color p chairs arranged on a round carrousel using b colors. Two colorings are considered identical if one can be obtained from the other by rotating the carrousel. Compute the number of (...
0
votes
3answers
260 views

Combinatorial Proof (Wanting a Second Opinion)

Let's say we have $$\binom{n+1}{r+1} = \sum_{j=r}^{n}\binom{j}{r}$$ The story is going to be, We are choosing a group with a leader. The LHS is saying, out of $n+1$ people, we pick $r+1$ people to be ...
0
votes
1answer
33 views

Combinatorial Proof With a Story

I have $$\sum_{k=0}^n \binom{n}{k} = 2^n$$ I am proving this using a story, but I was wondering if my story is correct. Our story is going to be we choose $k$ people out of $n$ to be in a club. LHS: ...
1
vote
4answers
93 views

combinatorial argument that $ [\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}]^{2} = \sum_{k=0}^{2n}\binom{2n}{k}$

Give a combinatorial argument with double counting showing that $$ \Bigg[\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}\Bigg]^{2} = \sum_{k=0}^{2n}\binom{2n}{k}$$ I am unsure on how to approach this ...
1
vote
2answers
209 views

Prove that $\sum_{m=1}^{n} (-1)^{m+1} {n \choose m} \frac{1}{m+1} = \frac{n}{n+1}$

I'm trying to prove that: $$\sum_{m=1}^{n} (-1)^{m+1} {n \choose m} \frac{1}{m+1} = \frac{n}{n+1}$$ I've tried to prove this by induction and directly, without luck. Any help would be appreciated.
1
vote
3answers
40 views

How to count partitioned subsets of a binomial coefficient

I have been reading Dr. Carl Wagner's book Basic Combinatorics, and I cannot wrap my head around a particular theorem. Someone else has asked a very similar question and accepted an answer, but I'm ...
5
votes
2answers
166 views

Combinatorial identity on decreasing dice throws

Suppose I repeatedly throw fair $n$-sided dice until I throw a $1$, at which point I stop. I want to know the probability $p(n)$ that my sequence of throws will be decreasing, such as $5-4-2-1$ or ...
1
vote
2answers
79 views

How to count the number of subsets of $X$ of size $k$ that are disjoint from $A$?

Apologies if my formatting is incorrect, this is my first post. I'm currently taking Discrete Mathematics, but I'm struggling to understand more complicated uses of PIE. The only examples we've ...
2
votes
2answers
83 views

Binomial coefficients identity : $\sum_{k=1}^{n-m+1} k\binom{n-k+1}{m}=\binom{n+2}{m+2}$ [duplicate]

For any positive integer m&n.$n\ge m$ , let $\left( {\begin{array}{*{20}{c}} n\\ m \end{array}} \right) = {}^n{C_m}$. Prove that $\left( {\begin{array}{*{20}{c}} n\\ m \end{array}} \right) + 2\...
2
votes
1answer
52 views

How does this product over finite primes represents density of certain natural numbers?

Let $p_{i}$ be the $i^{th}$ prime. I read that the product $\prod_{i=1}^{n} \big( 1 - \frac{1}{p_{i}} \big)$ represents the density of primes that are not divisible by any of the $p_{1}, p_{2}, \ldots ...
1
vote
1answer
26 views

Conjugates of a partition $n$

Is there any easiest way finding of conjugate of a partition $n$ (Except using Ferrers diagram)? e.g I can find the conjugate of a partition $a=[4,4,1]$ using Ferrers diagram, and I obtain $a^*=[3,2,2,...
0
votes
2answers
38 views

How to prove something combinatorially [duplicate]

I'm being asked to prove $ 2 \cdot 3^0 + 2 \cdot 3^1 + 2 \cdot 3^2 + \ldots + 2 \cdot 3^{n-1} = 3^n - 1. $ combinatorially using the question "How many length-$n$ lists can we form using the ...
1
vote
2answers
37 views

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

I've been staring at this identity which appears in my textbook for a while. Plugging in numbers I can verify that this is true, however I have no idea how this was determined or proved? Is there a ...
1
vote
0answers
25 views

$ \sum_{i=0}^{M}\binom{M+N-i-2}{N-2}\alpha^{i}=?$

This is one step in my proof of a theorem. I get stuck here for a month. I know that $\sum_{i=0}^{M}\binom{M+N-i-2}{N-2}=\binom{M+N-i-1}{N-1}$. I also proved that $\sum_{i=0}^{M}\binom{M+N-i-2}{N-2}\...
0
votes
0answers
28 views

Number of Routes and Valid Routes within a 2D grid w/ obstacles

9x9 Grid w/ Start, Goal, and U-Shaped Obstacle Take this 9x9 grid with a start location (0, 0), goal location (9,9), and U-shaped obstacle at (2,3), (3,3), (4,3), (2,4), and (4,4), how would I tackle ...
7
votes
1answer
68 views

How many arrangements of red and blue balls are there so that, the number of red balls with: the ball immediately to the right is also red, is $9$.

The question is too long to fit in the title, but I tried. $50$ balls: $23$ indistinguishable red balls; $27$ indistinguishable blue balls. The balls are arranged in a line. How many distinct ...
2
votes
2answers
116 views

Notation for newton-like expansion

Is there a compact way of referring to the expression $$a^n + a^{n - 1}b + a^{n - 2}b^2 + \cdots + b^n\:?$$ Maybe some notation I do not know about it. Thanks!
0
votes
0answers
22 views

square od combinatprial in discrete math [duplicate]

I have the following question: I am trying to prove that $\sum_{k=0}^{n} {\binom{N}{k}}^2 = \binom{2N}{k}$. I tried proving by induction $\sum_{k=0}^{n} {\binom{N}{k}}^2$, so I substituted k = 0 , 1,2,...
1
vote
1answer
65 views

Combinatorial proof of a sum with binomial coefficients

I would like to prove $\sum_{k=0}^{n}{k {n \choose k}}=n2^{n-1}$ with a combinatorial proof, once I already know to prove it algebrically. I thought about it in the following way: Consider a set $S=\{...
0
votes
1answer
31 views

How can i prove this identity using the combinatorial method?

$$m\,C(n,m)=n\,C(n-1,m-1)$$ I tried something like how can we choose a group out of n people and then how many ways we can choose the leader , and it worked for the first side but not for the 2nd. ...
5
votes
1answer
127 views

A power series equality involving binomial coefficients

I believe the following identity holds for any non-negative integers $m,k$: $$\binom{m+k}{k}^2 = \sum_{n=0}^m \binom{k}{m-n}^2\binom{2k+n}{n}.$$ It seems like there should be a slick double counting ...
1
vote
2answers
98 views

Proof of $\sum_{k=0}^n{ \binom{2k}{k} 2^{2n-2k} } = (2n+1) \binom{2n}{n} = \frac{n+1}{2} \binom{2(n+1)}{n+1}$ [duplicate]

I found some combinatorial identities in my old notebooks, but I cannot recall how I derived them. Can anyone help provide the most elementary/elegant proofs for the following identity? Specifically, ...
1
vote
2answers
87 views

“Stars and Bars” summation identity

Can anybody help me solve this problem? I don't even know where to start or how to interpret this. Proof for all $1 \leq k \leq n$ that the folowing identity holds: \begin{equation*} \begin{pmatrix} n+...
5
votes
3answers
151 views

Find the number of positive integral solutions of the equation $x_1+x_2+x_3+x_4+x_5=x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5$

Find the number of positive integral solutions of the equation $x_1+x_2+x_3+x_4+x_5=x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5$ This is one of the questions from the Indian Institution of Technology ...
0
votes
0answers
41 views

Multivariate Vandermonde type of combinatorial identity

Is there a closed formula for $\sum\limits_{m_1+ m_2+ n_1+ n_2 = C } \binom{A}{m_1-n_1} \binom{B}{m_1+n_1} \binom{A+2n_1+1}{m_2-n_2}\binom{B-2n_1-1}{m_2+n_2}$ If it weren't for the additional ...
0
votes
1answer
221 views

How to simplify this combinatorial summation? [closed]

Expression: ${m}\choose{1}$${n-m}\choose{k-1}$ + ${m}\choose{3}$${n-m}\choose{k-3}$ + ... + ${m}\choose{k}$${n-m}\choose{0}$ (assuming k is odd) We could write it as ${n}\choose{k}$ if the even terms ...
2
votes
1answer
84 views

Prove the identity $k \choose 2$ + $k \choose k-2$ + $k^2$ = $2k \choose 2$, where $k\geq2$ using a combinatorial proof.

A combinatorial proof for an identity proceeds as follows: State a counting question. Then, answer the question in two ways: One answer must correspond to the left-hand side (LHS) of the identity. The ...
-1
votes
1answer
42 views

Combinatorial Proof Problem [closed]

Use a combinatorial proof to show that ${ n \choose 0} $ + ${ n \choose 2} $ +${ n \choose 4} $ +...=${ n \choose 1} $ +${ n \choose 3} $ +${ n \choose 5} $ +...
-2
votes
2answers
60 views

Discrete Math - Calculating $\sum_{k}^{n}$

I have a question regarding on how to calculate expressions like (I need to write it without $\sum$ and without $k$): $$\sum_{k=2}^{25}\binom{25}{k}\binom{k}{2}$$ And also like: $$\sum_{k=1}^{10}k\...

1
2 3 4 5
17