Ask Question
Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc. They avoid complicated algebraic manipulations.
990 questions- Bountied 0
- Unanswered
- Frequent
- Score
- Unanswered (my tags)
Exponential generating function of the relation $B(n,k)=B(n-1,k-1)+(n-1)B(n-2,k-1)$ —just over $n$—
Let $B(n,k)$ the number of permutations of the set $[n]=\{1,\ldots,n\}$ that are decomposable in $k$ disjoint cycles of order $1$ or $2$. For example, $\mu=(1,3)(2,5)(4)(6,7)(8)$ is counted by $B(8,5)$... combinatorics generating-functions combinatorial-proofs- 119
Combinatorial proof of a simple inequality
I want to prove the following inequality combinatorialy $$\left(\frac{n+1}{2}\right)^n \ge n! ,n \in \mathbb{N} $$ my attempts in this direction so far have been $$\left(\frac{n+1}{2}\right)^n \ge n! \... combinatorics inequality combinatorial-proofs- 221
How to interpret these combinatorics equations' combination meanings
Let$$S_n:=\sum_{i=0}^n\frac{(-1)^i}{2i+1}\binom ni\\ H_n:=\sum_{i=0}^n\frac{(-1)^i}{2i+3}\binom ni$$then$$\begin{align}S_{n+1}-S_n&=\sum_{i=1}^n\frac{(-1)^i}{2i+1}\binom{n}{i-1}+\frac{(-1)^{n+1}}{... combinatorics combinations combinatorial-proofs- 39
Understanding binomial theorem with negative integer of n [duplicate]
I’m a student studying mathematics and I understood how the binomial theorem with positive integer of n works. But I couldn’t really understand the progress of how the binomial theorem with negative ... proof-writing binomial-theorem combinatorial-proofs negative-binomial- 11
Picking balls out of a bag intuition - "Rearranging the combinatorial tree"
This question is about the intuition behind the classic "picking the balls out of a bag" problem. It feels like it flattens out time, which is what I want to understand. First i will layout ... probability bayes-theorem combinatorial-proofs- 77
Colouring $n$ balls with $k$ colours
How many ways to colour $n$ balls with $k$ colours? Repeating and omitting colours is fine, and order is not important. $$\sum_{i=1}^k \binom{n-1}{i-1} \binom{k}{i} $$ This is what I came up with. It ... combinatorics combinatorial-proofs- 848
$6S(n,3)+6S(n,2)+3S(n,1)=3^n$
Find a simple proof for the following identity- $$6S(n,3)+6S(n,2)+3S(n,1)=3^n$$ where $S(n,k)$ is the Stirling numbers of second kind representing the number of partitions of $[n]$ into $k$ nonempty ... combinatorics combinations combinatorial-proofs stirling-numbers- 5,593
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{... combinatorics combinatorial-proofs set-partition- 1,453
$\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^{|\... probability combinatorics probability-theory combinatorial-proofs- 12.7k
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-... combinatorics binomial-coefficients combinatorial-proofs- 13
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 $... combinatorics combinatorial-proofs- 33
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 ... combinatorics solution-verification inclusion-exclusion combinatorial-proofs- 1,462
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 ... combinatorics mathematical-physics computational-mathematics combinatorial-proofs- 968
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 ... combinatorics matrices fourier-transform combinatorial-proofs hadamard-matrices- 1
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 ... combinatorics solution-verification binomial-coefficients combinatorial-proofs15 30 50 per page12345…66 Next
