اصل تناظر یک به‌یک

اصل دوسویگی یا تناظر یک به‌یک، یک اصل بسیار مهم در ترکیبیات شمارشی است که با استفاده از آن، برابر بودن تعداد اعضای دو مجموعه ثابت می‌شود.

تعریف اصل تناظر یک به‌یک

دو مجموعه‌ی متناهی $A, B$ را در نظر بگیرید. فرض کنید موارد زیر برقرار است:

  1. تناظر $f$ از $A$ به $B$ وجود دارد؛ یعنی تابعی مانند $f$ وجود دارد که به ازای هر $a \in A$، عضوی مانند $f(a)$ در $B$ وجود داشته باشد. $f(a)$ را عضو متناظر $a$ می‌نامیم.
  2. تناظر $g$ از $B$ به $A$ وجود دارد؛ یعنی تابعی مانند $g$ وجود دارد که به ازای هر $b \in B$، عضوی مانند $f(b)$ در $A$ وجود داشته باشد. $f(b)$ را عضو متناظر $b$ می‌نامیم.
  3. دو تناظر $f, g$ طوری هستند که به ازای هر $a \in A$ داشته باشیم $g(f(a))=a$ و به ازای هر $b \in B$ داشته باشیم $f(g(b))=b$. در واقع دو تناظر، طوری هستند که اگر $a$ متناظر $b$ باشد، $b$ نیز متناظر $a$ است.

اگر هر ۳ شرط بالا برقرار باشد، می‌گوییم یک دوسویگی یا تناظر یک به‌یک، بین مجموعه‌های $A, B$ برقرار است. توجه کنید شرط سوم هم حتمن باید برقرار باشد و تناظر، دوسویه باشد؛ در غیر این صورت نمی‌توان اصل تناظر یک به‌یک را به کار برد. اصل تناظر یک به‌یک بیان می‌کند:

چنان‌چه‌یک تناظر یک به‌یک بین دو مجموعه‌ی متناهی برقرار باشد، تعداد اعضای آن دو مجموعه با هم برابرند.

اصول دیگری شبیه اصل تناظر یک به‌یک مانند اصل‌های برون‌گستری و درون‌گستری، وجود دارند که در صفحات دیگر بررسی می‌شوند. برای مجموعه‌های نامتناهی نیز، اعداد کاردینال تعریف می‌شوند که این نیز در صفحات دیگر بررسی خواهند شد.

مثال: با استفاده از اصل دوسویگی، ثابت کنید: $$\binom{n}{r}=\binom{n}{n-r}$$

پاسخ

مجموعه‌ی $A$ را شامل تمام حالت‌های انتخاب $r$ نفر از $n$ نفر در نظر بگیرید. مجموعه‌ی $B$ را نیز شامل تمام حالت‌های انتخاب $n-r$ نفر از $n$ نفر تعریف می‌کنیم.

  1. تناظر ۱: یک عضو از $A$ مانند $a$ در نظر بگیرید. در این حالت، $r$ نفر انتخاب شده‌اند. حال، حالتی را در نظر بگیرید که $n-r$ نفر باقی‌مانده انتخاب شده باشند. این حالت یک عضو از $B$ است. این عضو را، عضو متناظر $a$ در نظر می‌گیریم.
  2. تناظر ۲: یک عضو از $B$ مانند $b$ در نظر بگیرید. در این حالت، $n-r$ نفر انتخاب شده‌اند. حال، حالتی را در نظر بگیرید که $r$ نفر باقی‌مانده انتخاب شده باشند. این حالت یک عضو از $A$ است. این عضو را، عضو متناظر $b$ در نظر می‌گیریم.
  3. متناظر متناظر هر عضو، خود آن عضو است. پس تناظرها دوسویه هستند.

پس اصل تناظر یک به‌یک، بین دو مجموعه‌ی $A, B$ برقرار است. پس $|A|=|B|$. از طرفی تعداد اعضای $A$ و $B$ به ترتیب $\binom{n}{r}$ و $\binom{n}{n-r}$ است. پس حکم ثابت شد.

گاهی تناظرها و دوسویه بودن آن‌ها مانند بالا آن‌قدر بدیهی هستند که می‌گوییم «فلان چیز» با «فلان چیز» متناظر است و نیازی به نوشتن هر ۳ مرحله نیست؛ اما گاهی این ۳ مرحله بدیهی نیستند و کاملن باید بیان شوند.

سایر مثال‌ها

توجه: ابتدا به اندازه‌ی کافی روی مسائل فکر کنید و سپس به پاسخ مراجعه کنید.

مثال:

  1. یک مجموعه‌ی $n$-عضوی ($n\ge 1$) در نظر بگیرید. ثابت کنید تعداد زیرمجموعه‌های فرد-عضوی آن با تعداد زیرمجموعه‌های زوج-عضوی آن برابر است.
  2. ثابت کنید:

$$\binom{n}{0}+\binom{n}{2}+…+\binom{n}{2\lfloor \frac{n}{2} \rfloor} = \binom{n}{1}+\binom{n}{3}+…+\binom{n}{2\lceil \frac{n}{2} \rceil - 1}$$

پاسخ

برای پاسخ قسمت اول، مجموعه‌ی $A$ را مجموعه‌ی تمام زیرمجموعه‌های زوج-عضوی و مجموعه‌ی $B$ را مجموعه‌ی تمام زیرمجموعه‌های فرد-عضوی تعریف می‌کنیم.

  1. تناظر ۱: یک عضو از $A$ مانند $a$ را در نظر بگیرید. $a$ خود یک زیرمجموعه است. اگر این زیرمجموعه، $a_1$ را نداشت، a_1 را به آن اضافه کنید و اگر $a_1$ را داشت، $a_1$ را از آن حذف کنید. به این ترتیب یک زیرمجموعه‌ی دیگر به دست می‌آید که قطعن فرد-عضوی است. این زیرمجموعه را زیرمجموعه‌ی متناظر $a$ در نظر می‌گیریم.
  2. تناظر ۲: مانند تناظر نخست عمل می‌کنیم و هر زیرمجموعه‌ی فرد-عضوی را به‌یک زیرمجموعه‌ی زوج-عضوی متناظر می‌کنیم.
  3. تناظرهای ما دوسویه هستند و متناظر متناظر یک زیرمجموعه، خود آن زیرمجموعه می‌شود.

پس بین $A, B$ یک تناظر یک به‌یک برقرار است. پس $|A|=|B|$ و حکم ثابت شد.

برای پاسخ قسمت دوم، دقت کنید سمت چپ تساوی، تعداد زیرمجموعه‌های زوج-عضوی و سمت راست تساوی، تعداد زیرمجموعه‌های فرد-عضوی است. با توجه به قسمت اول حکم ثابت می‌شود.

مثال: مجموعه‌ی $\{1, 2, …, n\}$ را در نظر بگیرید. یک زیرمجموعه از این مجموعه را فرد گوییم، اگر مجموع اعضایش فرد باشد و در غیر این صورت آن را زوج می‌نامیم. ثابت کنید تعداد زیرمجموعه‌های فرد با تعداد زیرمجموعه‌های زوج، برابر است.

پاسخ

مجموعه‌ی $A$ را مجموعه‌ی تمام زیرمجموعه‌های فرد و مجموعه‌ی $B$ را مجموعه‌ی تمام زیرمجموعه‌های زوج تعریف می‌کنیم. یک تناظر بین اعضای $A, B$ برقرار می‌کنیم. یک عضو $A$ یا $B$ را در نظر می‌گیریم. این عضو، خود یک زیرمجموعه از مجموعه‌ی مسئله است. اگر این زیرمجموعه ۱ را داشت، به آن اضافه می‌کنیم و اگر نداشت، ۱ را از آن حذف می‌کنیم. با این کار، زوجیت زیرمجموعه تغییر می‌کند و هر عضو $A$ با یک عضو $B$ و هر عضو $B$ با یک عضو $A$ متناظر می‌شود. از طرفی تناظر ما دوسویه است و متناظر متناظر هر زیرمجموعه، خود آن زیرمجموعه خواهد بود. پس $|A|=|B|$ و حکم ثابت شد.

مثال:

مسائل نمونه