Articles of combinatorics

Dobble card game – mathematical background

This question already has an answer here: Covering with most possible equal size subsets having pairwise singleton intersections 2 answers

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is $0$ when $n$ is odd.) The nice expression on the right-hand side indicates that there should be a pretty combinatorial proof of this statement. The proof should […]

Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$

Prove that $$ \frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}. $$ I tried already by induction over $k$ but i have problems showing the statement holds for $k=0$ or $k=1$.

Proof of subfactorial formula $!n = n!- \sum_{i=1}^{n} {{n} \choose {i}} \quad!(n-i)$

Any hints about how to prove $$!n = n!- \sum_{i=1}^{n} {{n} \choose {i}} \quad!(n-i)$$ from Wikipedia’s article on derangements? Here, $!n$ is the number of derangements of a set with $n$ elements. I am not looking for proofs, just nudges in the right direction.

How to prove $\sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m$?

Question: How to prove the following identity? $$ \sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m. $$ I’m also looking for the generalization of this identity like $$ \sum_{s=k}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=? $$ Proofs, hints, or references are all welcome.

Famous uses of the inclusion-exclusion principle?

The standard textbook example of using the inclusion-exclusion principle is for solving the problem of derangement counting; using inclusion-exclusion (and some basic analysis) it can be shown that $D(n)=\left[\frac{n!}{e}\right]$ which I consider to be quite a beautiful example since it tackles a problem that does not seem to be solvable with such a closed formula […]

Binomial coefficients that are powers of 2

I would like a proof that $$ {{n}\choose{k}} = \frac{n!}{k!(n-k)!} = 2^m $$ for $n,k,m\in \mathbb{N}$, only if $k=1$ or $k=n-1$. It seems to me that this must be true since for other values of $k$ the numerator contains more factors that are not powers of 2 than the denominator. Furthermore, the numerator also contains […]

number of permutations in which no two consecutive numbers are adjacent

In how many ways can the natural numbers from 1 to 10 be arranged so that no two consecutive numbers are adjacent to each other, and how is the formula arrived at?

Partition an integer $n$ into exactly $k$ distinct parts

I know how to find the number of partition into distinct parts, which is necessarily equal to the number of ways to divide a number into odd parts. I also know how to partition n into exactly k parts. However, combining the two restrictions, if you limit the number of summands and also say that […]

Intuitive explanation for Derangement

The recurrence relation for Derangement is as follows: Let $D_n$ denote the number of derangements of a set $\{1,2,3…n\}$ $D_n=(n-1)D_{n-1}+(n-1)D_{n-2}$ Can someone give and intuitive explanation on how we come to find this result