فرض کنید که مجموعه‌های $r$ عضوی $A_1,A_2,...,A_n$ و $B_1,B_2,...,B_n$ به گونه‌ای هستند که: $A_i \cap B_j = \varnothing$ اگر و تنها اگر $i=j$.

فرض کنید که مجموعه‌ی $X$ از اجتماع تمام این مجموعه‌ها تشکیل شده باشد (یعنی $X= \bigcup_{i=1} (A_i \cup B_i)$). هر جای‌گشتی از اعضای $X$ را به صورت $<x_1,...,x_m>$ نشان می‌دهیم (یک جای‌گشت از یک مجموعه‌ یک ترتیب از اغضای آن است که هر عضوی از مجموعه‌ دقیقاً یک بار در آن ظاهر شده است.)

اگر $A$ و $B$ هر دو زیرمجموعه‌ی $X$ و مجزا از یکدیگر باشند (یعنی $A \cap B= \varnothing$)٬ تعریف می‌کنیم که جای‌گشت $P= <x_1,...,x_m>$ از $X$٬ زوج‌مرتب $(A,B)$ را تقسم می‌کند٬ اگر و تنها اگر به ازای هر $a \in A$ و هر $b \in B$٬ جایی که $a$ در $P$ ظاهر شده است قبل از جایی باشد که $b$ ظاهر شده است (یعنی اگر $x_i= a$ و $x_j = b$ در آن صورت $i \lt j$).

الف) ثابت کنید که امکان ندارد $i$ و $j$ وجود داشته باشند که $i \neq j$ باشد و جای‌گشت $P$ از اعضای $X$ یافت شود به طوری که جای‌گشت $P$ زوج‌مرتب‌های $(A_i,B_i)$ و $(A_j,B_j)$ را تقسیم کند.

ب) ثابت کنید $n \le {2r \choose r}$

• سوال بعد
• سوال قبل