Combinatorial Interpretation
I am looking for a combinatorial interpretation to $f(n)=\sum\limits_{k=0}^{n}(-1)^{n-k}\binom{n}{k}g(k)$, where
1.) $g(n)=\binom{nr}{s}$
2.) $g(n)=\binom{\binom{n}{r}}{s}$
3.) $g(n)=2^{\binom{n}{2}}$
$\endgroup$ 31 Answer
$\begingroup$Hints:$$f(n)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}g(k)=\sum_{m=0}^{n}(-1)^{m}\binom{n}{m}g(n-m)$$ Try to use the Inclusion–exclusion principle: Find sets $A_1,...,A_n$ such that the intersection of any $m$ of them is of size $g(n-m)$. Give a combinatorial interpretation (as bad properties) to $A_1,...,A_k$, and then $f(n)$ is the amount of elements with no 'bad' properties.
For example:
In $(3)$ you can take $A_k$ to be the set of all labeled graphs on $n$ vertices in which the vertex $k$ is isolated (not connected to any other vertex). Then $f(n)$ will be the number of graphs on $n$ vertices without isolated vertices.
