1
$\begingroup$

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}}$

  • 0
    You might find the answers to [this question](http://math.stackexchange.com/q/55659/2370) helpful.2012-11-23

1 Answers 1

2

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.

  • 0
    Thank you, Dennis. However, I do not have much experience with combinatorics so I am stuck with coming up with ideas for the other two. I know that 1.) it is choosing $s$ elements out of a $(n-m)r$-set and 2.) choosing $r$ elements from a $n-m$-set and then choosing $s$ elements from those. Still I dont see how this can be intersections of sets with bad properties.2012-11-26