组合数学 (Fall 2023)/Problem Set 2: Difference between revisions
Created page with "Let <math>S=\{P_1,...,P_n\}</math> be a set of properties, and let <math>f_k</math> (respectively, <math>f_{\geq k}</math>) denote the number of objects in a finite set <math>U</math> that have '''exactly''' <math>k</math> (respectively, '''at least''' <math>k</math>) of the properties. Let <math>A_i</math> denote the set of objects satisfies <math>P_i</math> in <math>U</math>, for any <math>I\subseteq\{1,...,n\}</math>, we denote <math>A_I=\bigcap_{i\in I}A_i</math> wi..." |
No edit summary |
||
| Line 1: | Line 1: | ||
== Problem 1 == | |||
Let <math>S=\{P_1,...,P_n\}</math> be a set of properties, and let <math>f_k</math> (respectively, <math>f_{\geq k}</math>) denote the number of objects in a finite set <math>U</math> that have '''exactly''' <math>k</math> (respectively, '''at least''' <math>k</math>) of the properties. | Let <math>S=\{P_1,...,P_n\}</math> be a set of properties, and let <math>f_k</math> (respectively, <math>f_{\geq k}</math>) denote the number of objects in a finite set <math>U</math> that have '''exactly''' <math>k</math> (respectively, '''at least''' <math>k</math>) of the properties. | ||
Let <math>A_i</math> denote the set of objects satisfies <math>P_i</math> in <math>U</math>, for any <math>I\subseteq\{1,...,n\}</math>, we denote <math>A_I=\bigcap_{i\in I}A_i</math> with the convention that <math>A_\emptyset=U</math>. | Let <math>A_i</math> denote the set of objects satisfies <math>P_i</math> in <math>U</math>, for any <math>I\subseteq\{1,...,n\}</math>, we denote <math>A_I=\bigcap_{i\in I}A_i</math> with the convention that <math>A_\emptyset=U</math>. | ||
Revision as of 12:47, 13 April 2023
Problem 1
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]