خوش آموز درخت تو گر بار دانش بگیرد، به زیر آوری چرخ نیلوفری را


ترکیب و جایگشت (Combination and Permutation)

ترکیب و جایگشت (Combination and Permutation)
نویسنده : امیر انصاری
ترکیب ها (Combinations) و جایگشت ها (permutations) روش ها و فرمول هایی برای شمارش چیزها هستند. شما ممکن است فکر کنید که در شمردن چیزها هم اکنون کاملاً مسلط هستید، اما آیا واقعاً می خواهید به شیوه هایی که در زیر آمده است، شمارش کنید؟

سیستم یکپارچۀ سازمانی راهکار



  • اگر برنامه داشته باشید در سفر بعدی تان به سه ایالت (استان) مختلف بروید، چند تا تعطیلات متفاوت می توانید بروید؟
  • به چند روش مختلف می توانید حروف موجود در کلمه "smart" را بازچینش کنید - و چند تا از این بازچینش ها واقعاً کلمات معناداری تولید می کنند؟
  • به چند روش مختلف می توانید \(6\) عدد را از \(54\) انتخاب کنید، و آیا می توانید \($1\) شرط ببندید که در هر مجموعه از این \(6\) عدد می توانند بخت آزمایی (lottery) را ببرند؟

شما می توانید شروع به ساختن این لیست ها با روش های مختلفی کنید تا مسأله های اشاره شده را به انجام برسانید، اما خیلی زود در حجم زیاد کارهایی که باید انجام دهید غرق خواهید شد و شاید اندکی هم خسته شوید. جبر با چند فرمول شمارش به داد شما می رسد، این فرمول ها ترکیب ها و جایگشت ها نامیده می شوند.

شمارش معکوس با فاکتوریل (factorial)


عملیات اصلی در ترکیب ها و جایگشت ها، عملیات فاکتوریل (factorial) می باشد. این واقعاً یک عملیات شسته و رفته می باشد. این عملیات تنها یک عدد را دریافت می کند تا کارش را انجام دهد. نماد عملیات فاکتوریل، یک علامت تعجب \( (!) \) می باشد. عملیات فاکتوریل به شکل زیر انجام می شود:
$$ 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 =720 $$
$$ 4! = 4 \times 3 \times 2 \times 1 = 24 $$
قوانین جبر: فاکتوریل هر عدد صحیح مثبت برابر است با حاصلضرب آن عدد در هر عدد طبیعی (counting number) که از آن کوچکتر می باشد:
$$ n!=n(n-1)(n-2)(n-3) ... 3 \cdot 2 \cdot 1 $$
یادتان باشد: اعداد طبیعی یا اعداد شمارشی (counting numbers) عبارتند از:
$$ 1,2,3,4,5,...$$
فاکتوریل زمانی کار می کند که \(n\) یک عدد صحیح مثبت یا صفر باشد. به این معنا که شما می توانید ازاعداد زیر استفاده کنید:
$$0,1,2,3,4,5,...$$
نکات فنی: یک سورپرایز برای شما داریم و آن \(0!\) می باشد. سعی کنید در ماشین حسابی که عملیات فاکتوریل دارد این عملیات را انجام بدهید. در کمال تعجب خواهید دید \(0!=1\) . مقدار \(0!\) در واقع استثناء می باشد و در قاعدۀ فرمول فاکتوریل نمی گنجد. \(0!\) به نحوی تعریف شده است که همواره برابر با \(1\) باشد.

شمارش روی ترکیب ها


ترکیب ها (Combinations) به شما می گویند به چند روش مختلف می توانید چند آیتم را از کل یک گروه از آیتم ها انتخاب کنید. شما می توانید:

  • حساب کنید به چند روش مختلف سه ایالت را برای بازدید انتخاب کنید.
  • حساب کنید چند روش برای انتخاب \(6\) عدد از بین \(54\) عدد ممکن، وجود دارد.
  • حساب کنید چگونه \(8\) فضانورد را از بین \(40\) داوطلب انتخاب کنید.

ترکیب ها به شما نمی گویند در هر کدام از این انتخاب ها چه چیزی وجود دارد، اما به شما می گویند چند روش برای این انتخابها وجود دارد. اگر شما در حال ایجاد لیست ها هستید، و اگر بدانید چه تعداد باید در لیست باشد، می دانید چه زمانی باید متوقف شوید.

قوانین جبر: تعداد ترکیب های \(r\) آیتم که از مجموع امکان پذیر \(n\) آیتم گرفته می شوند، برابرند با:
$$ _nC_r = {n! \over r!(n-r)!} $$
زیرنویس ها در \(C\) دو چیز را می گویند:
  • زیرنویس سمت چپ، \(n\) ، نشان می دهد، روی هم رفته چه تعداد آیتم موجود هستند.
  • زیرنویس سمت راست، \(r\) ، بیان می کند چند تا از کل موجود انتخاب گشته اند.
محاسبه شامل پیدا کردن \(n\) فاکتوریل تقسیم بر حاصلضرب \(r\) فاکتوریل در تفاضل بین \(n\) و \(r\) فاکتوریل می باشد.

مثال: تعداد روش های مختلف انتخاب \(3\) ایالت از میان \(50\) ایالت را پیدا کنید. تعداد مجموع ایالت ها، \(n\)، برابر با \(50\) می باشد. تعداد ایالت هایی که می خواهید از بین \(50\) ایالت انتخاب کنید، \(r\)، برابر با \(3\) می باشد. بنابراین:
$$ _{50}C_3 = {50! \over 3!(50-3)!} $$
برای انجام این محاسبات نیاز به یک ماشین حساب دارید:
$$ _{50}C_3 = {50! \over 3!(50-3)!} = {50! \over 3!47!} = 19,600 $$
اگر شما بخواهید سه ایالت مختلف را به تمامی روش های ممکن بازدید کنید، \(19,600\) تعطیلات مختلف نیاز دارید. من برای شما این حالتهای مختلف را لیست می کنم:
Alabama, Alaska, and Arizona; Alabama, Alaska, and Arkansas; Alabama, . . .
اوکی، کافی است. زیاد طول نمی کشد تا متوجه شوید این کار چقدر سخت است. و حتی ترتیب (order) بازدید ایالت ها در اینجا به حساب آورده نشده است. اگر ترتیب را نیز لحاظ می کردیم تعداد روش های مختلف شش برابر می شد - و البته در جایگشت که در ادامه به آن می پردازیم به این شکل است.

مثال: چند روش برای انتخاب \(6\) عدد از بین \(54\) عدد ممکن، وجود دارد؟
$$ _{54}C_6 = {54! \over 6!(54-6)!}={54! \over 6!48!}=25,827,165 $$
اگر این مثال در ارتباط با یک بلیط بخت آزمایی و بررسی تمامی حالتهای ممکن باشد تعداد بلیط ها بسیار زیاد می شود.

مثال: چند روش برای انتخاب \(8\) فضانورد از بین \(40\) نفر وجود دارد؟
$$ _{40}C_8={40! \over 8!(40-8)!}={40! \over 8!32!}=76,904,685 $$
این اعداد همگی بسیار بزرگ هستند. نظرتان در مورد چند مثال منطقی تر چیست؟

مثال: چند روش برای انتخاب دو کتاب از یک قفسه که در آن هفت کتاب هست، وجود دارد؟
$$ _7C_2={7! \over 2!(7-2)!}={7! \over 2!5!}={5,040 \over 240}=21 $$
اوکی، این یکی بهتر بود.

جایگشت ها (permutations)


جایگشت ها قدری شبیه ترکیب ها هستند. تفاوت اصلی در اینست که در جایگشت ها ترتیب مهم است. اگر شما یک تعطیلات را انتخاب کنید که شامل مسافرت به ایالت های Alabama ، Alaska ، و Arizona گردد، به شش روش مختلف می توانید ترتیب این سه ایالت را چینش کنید:
Alabama, Alaska, Arizona
Alabama, Arizona, Alaska
Alaska, Arizona, Alabama
Alaska, Alabama, Arizona
Arizona, Alaska, Alabama
Arizona, Alabama, Alaska

درست مانند ترکیب ها، پیدا کردن تعداد جایگشت ها به شما نمی گوید که آنها چه هستند، بلکه به شما می گوید چه زمانی میتوانید لیست کردن را خاتمه بدهید.

قوانین جبر: تعداد جایگشت های \(r\) آیتم که از بین \(n\) آیتم ممکن انتخاب شده باشند، برابر است با:
$$ _nP_r = {n! \over (n-r)!} $$
زیرنویس های \(P\) دو چیز را بیان می کنند. زیر نویس سمت چپ، \(n\) ، نشان می دهد روی هم رفته چند آیتم داریم. زیرنویس سمت راست، \(r\) ، بیان می کند چند انتخاب از بین تعداد کل قرار است صورت پذیرد. توجه داشته باشید که تنها تفاوت بین این فرمول و فرمول ترکیب اینست که \(r!\) که در فرمول ترکیب وجود داشت در فرمول جایگشت وجود ندارد. این منجر می شود تا مخرج عدد کوچکتری گردد و پاسخ نهایی عدد بزرگتری شود. هنگامی که آیتم ها در ترتیب خاصی قرار بگیرند، روش های بیشتری برای انجام این کار وجود خواهد داشت.

مثال: در صورتی که ترتیب انتخاب حائز اهمیت باشد، چند روش برای انتخاب دو کتاب از بین هفت کتاب موجود در یک قفسه وجود دارد؟
$$ _7P_2={7! \over (7-2)!}={7! \over 5!}=42 $$
\(42\) روش مختلف برای انتخاب این دو کتاب وجود دارد.

مثال: چند آرایش (چینش) مختلف برای حروف موجود در کلمه "smart" وجود دارد؟ در کلمه "smart" پنج حرف وجود دارد و تمامی این پنج حرف در انتخاب ها لحاظ می گردند. بنابراین:
$$ _5P_5 = {5! \over (5-5)!}= {5! \over 0!} = {120 \over 1}=120 $$
\(120\) چیدمان مختلف برای این پنج حرف ممکن است.



نمایش دیدگاه ها (1 دیدگاه)

دیدگاه خود را ثبت کنید:

انتخاب تصویر ویرایش حذف
توجه! حداکثر حجم مجاز برای تصویر 500 کیلوبایت می باشد.