On the number of SDR of a (t,n)-family (Q1119579)

A system of distinct representatives of a family \({\mathcal F}=A_ 1,...,A_ n)\) is a sequence \((a_ 1,...,a_ n)\) of distinct elements with always \(a_ i\) in \(A_ i\). Write N(\({\mathcal F})\) for the number of different such systems for the family \({\mathcal F}\). The family \({\mathcal F}\) is said to be a (t,n)-family if \(| \cup \{A_ i;i\in I\}| \geq | I| +t\) for all non-empty subsets I of \(\{\) 1,...,n\(\}\). Lt \(M(t,n)=\min \{N({\mathcal F})\); \({\mathcal F}\) is a (t,n)-family\(\}\). Thus Hall's classic theorem on distinct representatives asserts that M(0,n)\(\geq 1\). In this paper it is shown that \(M(1,n)=n+1\) and \(M(2,n)=n^ 2+n+1\). For \(0\leq t\leq 2\), the (t,n)-families \({\mathcal F}\) with N(\({\mathcal F})=M(t,n)\) are determined.