# 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.

807 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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$
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 ...
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 ...
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.
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 ...
43 views

29 views

361 views

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 (...
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 ...
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: ...
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 ...
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.
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 ...
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 ...
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 ...
83 views

26 views

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 ...
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 ...
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!
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,...