Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

تبدیل‌ها

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

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

فرمول تبدیل

می‌خواهیم فرمولی برای تبدیل r از n یا همان Pnr بیابیم. برای جایگشت r نفره‌ی خود، r جایگاه در نظر می‌گیریم. در جایگاه اول، به n طریق یک نفر می‌تواند قرار بگیرد. در جایگاه دوم، به n1 طریق، یک نفر می‌تواند قرار بگیرد. به همین ترتیب تعداد حالت‌های جایگاه‌های بعدی نیز مشخص می‌شوند. پس: Pnr=n(n1)(n2)...(nr+1) =n(n1)(n2)...(nr+1)×(nr)×(nr1)×...×1(nr)×(nr1)×...×1 پس: Pnr=n!(nr)!

به ویژه: Pnn=n!0!=n!

یک مثال

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

پاسخ

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

سایر مثال‌ها

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

مثال: در چند جایگشت <a1,a2,...,a9> از اعداد 1,2,...,9، شرط a1<a2<a3 برقرار است؟

پاسخ

ابتدا اعداد a4,a5,...,a9 را به P96 طریق انتخاب می‌کنیم و جایگشت می‌دهیم. ۳ عدد باقی‌مانده به صورت یکتا از کوچک به بزرگ باید در ۳ مکان باقی‌مانده قرار بگیرند. پس پاسخ برابر P96×1=9!3! است.

در روشی دیگر می‌توان گفت به ازای هر جایگشتی که پاسخ مسئله باشد، ۶ جایگشت خطی از اعداد 1,2,...,9 وجود دارد (با جایگشت دادن a1,a2,a3). پس پاسخ 16 تعداد جایگشت‌های ۹ عنصره و برابر 9!6 است.

مثال: ثابت کنید: Pnr=nPn1r1

پاسخ

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

مسائل نمونه


ابزار صفحه