فرض کنید $G$ یک گراف دوبخشی باشد به طوری که هر بخش دقیقا $n$ راس داشته باشد و دنباله‌ی درجه‌های راس‌های یک بخش $r_1,r_2,…,r_n$ باشد. قضیه‌ برگمن بیان می‌دارد که تعداد تطابق‌های کامل این گراف کم‌تر یا مساوی است با

$$\prod_{i=1}^n (r_i!)^{ \frac{1}{ r_i }}$$

$(a)$ شما باید با استفاده از قضیه‌ی برگمن تعمیم زیر را اثبات کنید:

فرض کنید $G$ یک گراف دوبخشی باشد به طوری که بخش $X$ دقیقا $m$ راس و بخش $Y$ دقیقا $n\geq m$ راس داشته باشد. اگر دنباله‌ی درجه‌های راس‌های بخش $X$‌به صورت $r_1,r_2,…,r_ m$ باشد، آن‌گاه تعداد تطابق‌های با اندازه‌ی $n$‌کم‌تر یا مساوی است با:

$$\frac{n!^{ \frac{n-m}{n}}}{(n-m)!} \prod_{i=1}^n (r_i!)^{ \frac{1}{ r_i }}$$

$(b)$ فرض کنید $S$ یک زیرمجموعه از خانه‌های یک مربع $n\times n$ باشد به طوری که دقیقا $r_i$ خانه در سطر $i$ام و $c_j$ خانه در ستون $j$ ام داشته باشد. با استفاده از قضیه‌ای که در قسمت قبل اثبات کردید ثابت کنید: تعداد مربع‌های لاتین جزیی که می‌توان در $S$ قرار داد کم‌تر یا مساوی است با:

$$\biggl( \prod_{i=1}^n (n!)^{ \frac{n-r_i}{ n }} \frac{1}{(n-r_i)!} \biggl) \biggl(\prod_{i=1}^n \prod_{j=0}^{c_i-1} (n-j)!^{ \frac{1}{(n-j)!}} \biggl)$$

• سوال قبل