فهرست مندرجات
تبدیل‌ها
فرض کنید $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$ در بخش دوگانه‌شماری و اتحادهای ترکیبیاتی، روش‌هایی بهتر برای اثبات نیز خواهیم یافت.
مسائل نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
