المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:تبدیل‌ها

تبدیل‌ها

فرض کنید $n$ نفر داریم. می‌خواهیم $r$ تا از آن‌ها را انتخاب کنیم و به آن‌ها جایگشت دهیم. این کار، یک تبدیل $r$ تایی از $n$ نفر به ما می‌دهد.

تبدیل $r$ از $n$ با نماد $P_r^n$ یا $P(n, r)$ نشان می‌دهیم. حرف $P$ از کلمه‌ی permutation می‌آید.

فرمول تبدیل

می‌خواهیم فرمولی برای تبدیل $r$ از $n$ یا همان $P_r^n$ بیابیم. برای جایگشت $r$ نفره‌ی خود، $r$ جایگاه در نظر می‌گیریم. در جایگاه اول، به $n$ طریق یک نفر می‌تواند قرار بگیرد. در جایگاه دوم، به $n-1$ طریق، یک نفر می‌تواند قرار بگیرد. به همین ترتیب تعداد حالت‌های جایگاه‌های بعدی نیز مشخص می‌شوند. پس: $$P_r^n=n(n-1)(n-2)...(n-r+1)$$ $$=n(n-1)(n-2)...(n-r+1) \times \frac{(n-r)\times(n-r-1)\times...\times1}{(n-r)\times(n-r-1)\times...\times1}$$ پس: $$P_r^n=\frac{n!}{(n-r)!}$$

به ویژه: $$P_n^n=\frac{n!}{0!}=n!$$

یک مثال

مثال: چند عدد ۳ رقمی با ارقام متمایز از ارقام $1, 2, ..., 8$ وجود دارد؟

پاسخ

پاسخ برابر انتخاب کردن ۳ رقم از ۸ رقم موجود و جایگشت دادن آن‌هاست که برابر $P_3^8$ است.

سایر مثال‌ها

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

مثال: در چند جایگشت $<a_1, a_2, ..., a_9>$ از اعداد $1, 2, ..., 9$، شرط $a_1<a_2<a_3$ برقرار است؟

پاسخ

ابتدا اعداد $a_4, a_5, ..., a_9$ را به $P_6^9$ طریق انتخاب می‌کنیم و جایگشت می‌دهیم. ۳ عدد باقی‌مانده به صورت یکتا از کوچک به بزرگ باید در ۳ مکان باقی‌مانده قرار بگیرند. پس پاسخ برابر $$P_6^9\times1=\frac{9!}{3!}$$ است.

در روشی دیگر می‌توان گفت به ازای هر جایگشتی که پاسخ مسئله باشد، ۶ جایگشت خطی از اعداد $1, 2, ..., 9$ وجود دارد (با جایگشت دادن $a_1, a_2, a_3$). پس پاسخ $\frac{1}{6}$ تعداد جایگشت‌های ۹ عنصره و برابر $\frac{9!}{6}$ است.

مثال: ثابت کنید: $$P_r^n=nP_{r-1}^{n-1}$$

پاسخ

$$nP_{r-1}^{n-1}=n\times \frac{(n-1)!}{((n-1)-(r-1))!}$$ $$=\frac{n!}{(n-r)!}=P_r^n$ در بخش دوگانه‌شماری و اتحادهای ترکیبیاتی، روش‌هایی بهتر برای اثبات نیز خواهیم یافت.

مسائل نمونه


ابزار صفحه