组合数学 (Fall 2023)/Problem Set 2

Problem 3

Let [math]\displaystyle{ S=\{P_1,...,P_n\} }[/math] be a set of properties, and let [math]\displaystyle{ f_k }[/math] (respectively, [math]\displaystyle{ f_{\geq k} }[/math]) denote the number of objects in a finite set [math]\displaystyle{ U }[/math] that have exactly [math]\displaystyle{ k }[/math] (respectively, at least [math]\displaystyle{ k }[/math]) of the properties. Let [math]\displaystyle{ A_i }[/math] denote the set of objects satisfies [math]\displaystyle{ P_i }[/math] in [math]\displaystyle{ U }[/math], for any [math]\displaystyle{ I\subseteq\{1,...,n\} }[/math], we denote [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math] with the convention that [math]\displaystyle{ A_\emptyset=U }[/math]. Show that

[math]\displaystyle{ f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i }[/math] and [math]\displaystyle{ f_{\geq k}=\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}g_i }[/math]

where [math]\displaystyle{ g_i=\sum_{I\subseteq\{1,...,n\},|I|=i }|A_I| }[/math]