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

1,233 questions
Filter by
Sorted by
Tagged with
55 views

### Correctness of Solution for Forming a Committee with More Democrats than Republicans

I recently encountered a problem and derived a solution, but I am uncertain about its correctness. Here's the problem: At a congressional hearing, there are 2n members present. Exactly n of them are ...
12 views

305 views

1 vote
50 views

### Bijection between permutations of even length cycles and pairs of factors

I was trying to solve Exercise 3.13.15 in Cameron's Combinatorics: Topics, Techniques, Algorithms. It goes like this: (a) Let $n = 2k$ be even, and $X$ a set of $n$ elements. Define a factor to be a ...
• 3,579
1 vote
99 views

### Combinatoric identity

I'm trying to get a combinatorial proof of the following identity by making up some story. $$\sum_{k=1}^n {k \choose j}k = {n+1 \choose j+1}n - {n+1 \choose j+2}$$ I can do it, by simplifying the ...
• 682
20 views

### Computing maximum of a ratio defined on the grid graph

Consider an $n \times n$ grid graph $G$. Define the following quantity $$m(G) = \text{max}\bigg\{\frac{|E|_{H'}}{|V|_{H'}},~ H' \subseteq G, ~~|V|_{H'} > 0 \bigg\},$$ ...
54 views

### Is my logic correct? A bit string of n with more 0s than 1s

I am learning about combinatorial and bit strings. I decided to use combinatorial reasoning and wanted to see if my logic made sense. The question: How many bit strings of length n contain more 0’s ...
• 51
22 views

### How many bit strings of length n contain more 0’s than 1’s? [duplicate]

To solve this, I think we need to use combinatorial reasoning.= Consider a bit string of length ( n ). There are ( 2^n ) possible bit strings of this length because each bit can independently be ...
• 51
58 views

### Prove combinatoric equation: $\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$

Prove the equation: $$\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$$ My solution: We have $n+1$ players numbered from $1$ to $n+1$. We want to play a team game that ...
• 1,379
37 views

### find number of disjoint subsets

For my discrete maths course i did the following exercise: Let M be a finite set with n elements, find $|\{(U,V)|U,V\subseteq M , U \not = V,U\cap V= \emptyset \}|$ I did it the following way: choose ...
• 41
172 views

• 643
86 views

### Evaluate using combinatorial argument or otherwise :$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$

Evaluate using combinatorial argument or otherwise $$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$$ My Attempt By plugging in values of $i=0,1,2,3$ I could observe that ...
• 9,220
71 views

### The number of relations over a set

I need to calculate the number of relations over $A$, when the size of $A$ is $n$, and want to understand why my approach is not correct. I denoted $A_i$ as subset of $A$, and I said general relation ...
• 217
51 views

### On the probleme des menages solution on Titu Andreescu book

The probleme des menages consists of the following: How many ways can $n$ married couples si at a round table in such a way that there is one man between every two women and no man is seated next to ...
• 603
102 views

### Story proofs in Combinatorics/Probability [closed]

I have been recently been going through Blitzstein in an attempt to put my probability on a stronger foundation then it currently is. There is a large emphasis on the use of "story" proofs/...
• 1,680
91 views

### Prove that there are $n! - (n-1)(n-1)!$ ways to arrange $n$ objects in a circular arrangement.

Prove that there are $n! - (n-1)(n-1)!$ ways to arrange $n$ objects in a circular arrangement. I have tried algebraic proofs by equating it to $\frac{n!}{n}$ and to $(n-1)!$ but can't think of a way ...
• 49