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

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

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

دو مجموعه‌ی متناهی $A, B$ را در نظر بگیرید. فرض کنید موارد زیر برقرار است:
  - تناظر $f$ از $A$ به $B$ وجود دارد؛ یعنی تابعی مانند $f$ وجود دارد که به ازای هر $a \in A$، عضوی مانند $f(a)$ در $B$ وجود داشته باشد. $f(a)$ را عضو متناظر $a$ می‌نامیم.
  - تناظر $g$ از $B$ به $A$ وجود دارد؛ یعنی تابعی مانند $g$ وجود دارد که به ازای هر $b \in B$، عضوی مانند $f(b)$ در $A$ وجود داشته باشد. $f(b)$ را عضو متناظر $b$ می‌نامیم.
  - دو تناظر $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$ نفر تعریف می‌کنیم.

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

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

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

===== سایر مثال‌ها =====

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

**مثال**:
  - یک مجموعه‌ی $n$-عضوی ($n\ge 1$) در نظر بگیرید. ثابت کنید تعداد زیرمجموعه‌های فرد-عضوی آن با تعداد زیرمجموعه‌های زوج-عضوی آن برابر است.
  - ثابت کنید:
$$\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$ را مجموعه‌ی تمام زیرمجموعه‌های فرد-عضوی تعریف می‌کنیم.

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

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

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

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

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

**مثال**:


===== مسائل نمونه =====