تعداد توابع یکبهیک: انتخاب مرتب m عضو از مجموعهٔ مقصد n عضوی
تعریف تابع یکبهیک و تفاوت آن با توابع دیگر
تابع یکبهیک یا تابع تزریقی2 به تابعی گفته میشود که در آن هر عضو از دامنه به یک عضو منحصربهفرد از مجموعهٔ مقصد نگاشته میشود و هیچ دو عضوی از دامنه، تصویر یکسانی در مجموعهٔ مقصد ندارند. به عبارت سادهتر: اگر $f(a) = f(b)$ آنگاه حتماً $a = b$.
برای درک بهتر، تفاوت بین توابع یکبهیک، پوشا3 و دوسویی4 را در جدول زیر مقایسه میکنیم:
| نوع تابع | شرط اصلی | مثال با m=3 , n=4 |
|---|---|---|
| یکبهیک (تزریقی) | هر تصویر حداکثر یک بار استفاده میشود | $f(1)=a , f(2)=b , f(3)=c$ |
| پوشا (حتی) | هر عضو مقصد حتماً تصویر است | امکانپذیر نیست چون $m \lt n$ |
| دوسویی (بیژکتیو) | هم یکبهیک هم پوشا | نیاز به $m=n$ دارد |
اصل ضرب و انتخاب مرتب اعضا
برای شمارش توابع یکبهیک از یک دامنهٔ m عضوی به یک مجموعهٔ مقصد n عضوی ($m \le n$)، از اصل ضرب استفاده میکنیم. عضو اول دامنه میتواند به هر یک از n عضو مقصد برود. عضو دوم دامنه چون نمیتواند تصویر تکراری داشته باشد، فقط $n-1$ انتخاب دارد. عضو سوم $n-2$ انتخاب، و به همین ترتیب تا عضو m-اُم که $n-(m-1)$ انتخاب خواهد داشت.
این حاصلضرب دقیقاً همان تعداد جایگشتهای m از n است که با نماد $P(n,m)$ یا $_nP_m$ نشان داده میشود. فرمول فشردهٔ آن به کمک فاکتوریل5 به صورت زیر است:
مثالهای عددی گامبهگام با اندازههای متفاوت
در این بخش با چند مثال عددی، روند محاسبه را قدم به قدم دنبال میکنیم. فرض کنید دامنه $A = \{a_1, a_2, ..., a_m\}$ و مقصد $B = \{b_1, b_2, ..., b_n\}$ باشد.
مثال ۱:$m=2 , n=5$ (چند تابع یکبهیک میتوان از مجموعهٔ 2 عضوی به مجموعهٔ 5 عضوی تعریف کرد؟)
گام اول: برای $a_1$، $5$ انتخاب.
گام دوم: برای $a_2$، چون $a_1$ یک تصویر را اشغال کرده، $4$ انتخاب میماند.
مجموع: $5 \times 4 = 20$.
با فرمول: $P(5,2) = \frac{5!}{(5-2)!} = \frac{120}{6} = 20$.
مثال ۲:$m=3 , n=3$ (توابع یکبهیک روی یک مجموعهٔ 3 عضوی)
گام اول: $3$ انتخاب
گام دوم: $2$ انتخاب
گام سوم: $1$ انتخاب
مجموع: $3 \times 2 \times 1 = 6$ که همان $3!$ است. این توابع در واقع همان جایگشتهای مجموعهٔ 3 عضوی هستند.
| m (اندازهٔ دامنه) | n (اندازهٔ مقصد) | تعداد توابع یکبهیک $P(n,m)$ |
|---|---|---|
| 2 | 4 | 12 |
| 3 | 5 | 60 |
| 4 | 4 | 24 |
| 2 | 10 | 90 |
کاربرد عملی: رمزهای یکبارمصرف و کدهای تخفیف منحصربهفرد
یکی از کاربردهای مهم توابع یکبهیک در تولید کدهای تخفیف یا رمزهای یکبارمصرف است. فرض کنید یک فروشگاه اینترنتی میخواهد برای 1000 مشتری خود کد تخفیف 4 رقمی (از ارقام 0 تا 9) تولید کند، به شرط آنکه هیچ کدی تکراری نباشد. در اینجا دامنه مشتریان به اندازهٔ m = 1000 و مجموعهٔ مقصد تمام کدهای ممکن 4 رقمی با $n = 10^4 = 10000$ عضو است. از آنجا که $m \le n$ است، میتوان یک تابع یکبهیک تعریف کرد. تعداد کل توابع یکبهیک ممکن برابر است با:
که عددی بسیار بزرگ است و امکان تخصیص یک کد منحصربهفرد به هر مشتری را فراهم میکند. این اصل در طراحی سیستمهای احراز هویت و تولید شناسههای یکتا کاربرد گستردهای دارد.
چالشهای مفهومی
۱) چه تفاوتی بین تعداد توابع یکبهیک و تعداد انتخابهای نامرتب وجود دارد؟
در توابع یکبهیک، ترتیب اعضای دامنه اهمیت دارد چون هر عضو مبدأ یک تصویر مشخص میگیرد. در انتخابهای نامرتب (ترکیبها)، فقط زیرمجموعهٔ مقصد مهم است. رابطهٔ بین این دو به صورت $P(n,m) = C(n,m) \times m!$ است، یعنی هر انتخاب نامرتب از m عضو از n را میتوان به $m!$ طریق به یک تابع یکبهیک تبدیل کرد.
۲) اگر $m \gt n$ باشد، چه اتفاقی میافتد؟
در این حالت به دلیل اصل لانهکبوتری6، حداقل دو عضو دامنه به یک عضو مقصد نگاشته میشوند. بنابراین هیچ تابع یکبهیکی وجود ندارد و پاسخ برابر $0$ است. فرمول $\frac{n!}{(n-m)!}$ برای $m \gt n$ تعریف نشده (فاکتوریل عدد منفی معنی ندارد).
۳) چرا نمیتوانیم از فرمول $n^m$ برای توابع یکبهیک استفاده کنیم؟
فرمول $n^m$ تعداد تمام توابع (نه حتماً یکبهیک) را نشان میدهد. در آنجا هر عضو دامنه آزادانه میتواند به هر عضوی از مقصد برود، حتی اگر تکراری باشد. تفاوت کلیدی در قید عدم تکرار در توابع یکبهیک است که باعث کاهش تعداد از $n^m$ به $P(n,m)$ میشود. برای مثال با $n=3 , m=2$ داریم $3^2=9$ تابع کل، در حالی که توابع یکبهیک $3 \times 2 = 6$ عدد است.
تعداد توابع یکبهیک از یک مجموعهٔ m عضوی به یک مجموعهٔ n عضوی (با شرط $m \le n$) برابر است با $P(n,m) = n \times (n-1) \times ... \times (n-m+1) = \frac{n!}{(n-m)!}$. این مفهوم پایهای در ترکیبیات، معادل «انتخاب مرتب m عضو از n عضو» است و در مسائل تخصیص منابع، رمزنگاری، و طراحی الگوریتمها کاربرد فراوانی دارد. به خاطر داشته باشید که اگر $m \gt n$ باشد، هیچ تابع یکبهیکی وجود نخواهد داشت.
پاورقی
1 جایگشت (Permutation): هر ترتیب خطی از اعضای یک مجموعه که در آن ترتیب قرار گرفتن اعضا مهم است.
2 تابع تزریقی (Injective Function): تابعی که در آن هر عضو از مجموعهٔ مقصد حداکثر یک بار به عنوان تصویر ظاهر میشود.
3 تابع پوشا (Surjective Function): تابعی که در آن هر عضو از مجموعهٔ مقصد حداقل یک بار به عنوان تصویر ظاهر میشود.
4 تابع دوسویی (Bijective Function): تابعی که هم یکبهیک و هم پوشا باشد؛ در چنین حالتی اندازهٔ دامنه و مقصد برابر است.
5 فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی از 1 تا n که به صورت $n!$ نمایش داده میشود. مثلاً $4! = 4 \times 3 \times 2 \times 1 = 24$.
6 اصل لانهکبوتری (Pigeonhole Principle): اگر تعداد اشیاء بیشتر از تعداد لانهها باشد، حداقل یک لانه شامل دو یا چند شیء خواهد بود.
