فرمول جایگشت با تکرار: تعداد چینش n شیء با گروه‌های تکراری

بروزرسانی شده در: 18:57 1405/02/17 مشاهده: 43 دسته بندی: کپسول آموزشی

فرمول جایگشت با تکرار: ترتیب‌دهی اشیا در گروه‌های تکراری

مفهوم فاکتوریل، گروه‌های یکسان، و فرمول $ \frac{n!}{n_1! \times n_2! \times \dots \times n_k!} $ همراه با مثال‌های گام‌به‌گام

در این مقاله می‌آموزیم که چگونه تعداد چینش‌های ممکن برای $ n $ شیء را وقتی برخی از اشیا با هم تکراری هستند، محاسبه کنیم. فرمول جایگشت با تکرار $ \frac{n!}{n_1! \times n_2! \times \dots \times n_k!} $ کاربرد گسترده‌ای در رمزنگاری، آمار، و مسائل روزمره مانند چیدن حروف یک کلمه دارد. در این مقاله با زبانی ساده و مثال‌های ملموس، این مفهوم را گام به گام بررسی می‌کنیم.

۱. جایگشت بدون تکرار در مقابل جایگشت با تکرار

در حالت عادی، اگر $ n $ شیء متمایز داشته باشیم، تعداد راه‌های چینش آن‌ها برابر $ n! $ (فاکتوریل $ n $) است. اما اگر برخی از اشیا تکراری باشند (مثلاً چند توپ همرنگ یا حروف تکراری در یک کلمه)، دیگر نمی‌توانیم همه چینش‌ها را با $ n! $ محاسبه کنیم، زیرا جابه‌جایی اشیای تکراری با یکدیگر چینش جدیدی ایجاد نمی‌کند.

مثال ساده: فرض کنید می‌خواهیم حروف کلمه «سَر» را به ترتیب‌های مختلف بنویسیم. هر سه حرف متمایز هستند، بنابراین تعداد حالت‌ها $ 3! = 6 $ است. اما اگر کلمه «سَگ» را در نظر بگیریم که حرف «س» تکرار شده، بسیاری از چینش‌ها یکسان به نظر می‌رسند. برای حل این مسئله، باید تعداد جایگشت‌های تکراری را محاسبه کنیم.

فرمول اصلی جایگشت با تکرار به این صورت است: $ \text{تعداد چینش‌ها} = \frac{n!}{n_1! \times n_2! \times \dots \times n_k!} $ که در آن:

$ n $ = تعداد کل اشیا
$ n_1, n_2, \dots, n_k $ = تعداد هر گروه تکراری

۲. گام‌های محاسبه با یک مثال گام‌به‌گام

فرض کنید می‌خواهیم تعداد روش‌های چیدن $ 5 $ کارت شامل $ 2 $ کارت قرمز (نشانه $ R $)، $ 2 $ کارت آبی (نشانه $ B $) و $ 1 $ کارت سبز (نشانه $ G $) را محاسبه کنیم.

مرحله ۱: تعداد کل اشیا: $ n = 5 $
مرحله ۲: شناسایی گروه‌های تکراری: $ n_1 = 2 $ (قرمز)، $ n_2 = 2 $ (آبی)، $ n_3 = 1 $ (سبز)
مرحله ۳: محاسبه فاکتوریل‌ها: $ 5! = 120 $، $ 2! = 2 $، $ 1! = 1 $
مرحله ۴: اعمال فرمول: $ \frac{120}{2! \times 2! \times 1!} = \frac{120}{2 \times 2 \times 1} = \frac{120}{4} = 30 $
مرحله ۵: نتیجه: $ 30 $ چینش متمایز وجود دارد.

مثال	تعداد کل اشیا	گروه‌های تکراری	تعداد چینش‌ها
کلمه $ AAB $	$ n=3 $	$ n_A=2, n_B=1 $	$ \frac{3!}{2!1!}=3 $
کلمه $ MISSISSIPPI $	$ n=11 $	$ n_M=1, n_I=4, n_S=4, n_P=2 $	$ \frac{11!}{1!4!4!2!}=34650 $
چیدن $ 4 $ سکه (۳ یک ریالی، ۱ دو ریالی)	$ n=4 $	$ n_{1ریال}=3, n_{2ریال}=1 $	$ \frac{4!}{3!1!}=4 $

۳. کاربرد عملی: رمزهای عبور و چیدمان کاراکترها

فرض کنید یک سیستم رمز عبور ۶ رقمی فقط از دو رقم $ 0 $ و $ 1 $ استفاده می‌کند، اما دقیقاً $ 4 $ بار عدد $ 1 $ و $ 2 $ بار عدد $ 0 $ باید تکرار شود. تعداد رمزهای ممکن برابر است با جایگشت با تکرار $ 6 $ شیء با دو گروه تکراری: $ \frac{6!}{4! \times 2!} = \frac{720}{24 \times 2} = \frac{720}{48} = 15 $. این محاسبه در طراحی کدهای تشخیص خطا و نظریه اطلاعات کاربرد فراوان دارد.

مثال روزمره دیگر: اگر یک فروشنده بخواهد $ 8 $ قفسه کتاب را با $ 5 $ جلد همرنگ آبی و $ 3 $ جلد همرنگ سبز بچیند، بدون در نظر گرفتن تفاوت بین جلدهای همرنگ، تعداد چیدمان‌ها برابر $ \frac{8!}{5!3!} = 56 $ خواهد بود.

۴. چالش‌های مفهومی و رفع ابهامات

چالش ۱: چرا نمی‌توانیم از فرمول $ n! $ ساده استفاده کنیم؟
پاسخ: استفاده از $ n! $ فرض می‌کند همه اشیا متمایز هستند. هنگامی که اشیای تکراری داریم، جابه‌جایی آن‌ها چینش جدیدی پدید نمی‌آورد. فرمول جایگشت با تکرار، این جابه‌جایی‌های اضافی را با تقسیم بر فاکتوریل تعداد هر گروه حذف می‌کند.

چالش ۲: اگر بیش از دو گروه تکراری داشته باشیم، آیا فرمول به همین سادگی کار می‌کند؟
پاسخ: بله. فرمول $ \frac{n!}{n_1! n_2! \dots n_k!} $ برای هر تعداد گروه تکراری معتبر است. فقط کافی است حاصلضرب فاکتوریل همه گروه‌ها را در مخرج قرار دهیم.

چالش ۳: آیا ترتیب گروه‌ها در مخرج تأثیری در نتیجه دارد؟
پاسخ: خیر، چون ضرب اعداد جابجایی‌پذیر است. برای مثال $ 2! \times 3! $ همان $ 3! \times 2! $ است. مهم این است که همه گروه‌ها لحاظ شوند.

جمع‌بندی

فرمول جایگشت با تکرار $ \frac{n!}{n_1! \times n_2! \times \dots \times n_k!} $ ابزاری قدرتمند برای محاسبه تعداد چینش‌های ممکن در شرایطی است که برخی از اشیا غیرقابل تمایز هستند. با درک مفهوم فاکتوریل و شناسایی گروه‌های تکراری، دانش‌آموزان دبیرستانی می‌توانند مسائل متنوعی از جمله چینش حروف کلمات، چیدمان اشیای همرنگ و حتی مسائل پایه‌ای رمزنگاری را حل کنند. نکته کلیدی این است که همیشه ابتدا تعداد کل اشیا و فراوانی هر شیء تکراری را مشخص کنیم، سپس با رعایت ترتیب عملیات (محاسبه فاکتوریل‌ها، ضرب در مخرج و سپس تقسیم) به پاسخ برسیم.

پاورقی

¹ فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی از $ 1 $ تا $ n $ که با نماد $ n! $ نمایش داده می‌شود. مثال: $ 4! = 4 \times 3 \times 2 \times 1 = 24 $.

² جایگشت (Permutation): هر ترتیب خطی ممکن از مجموعه‌ای از اشیا. در حالت با تکرار، ترتیب‌هایی که تنها با جابه‌جایی اشیای تکراری حاصل شوند، یکسان در نظر گرفته می‌شوند.

³ گروه تکراری (Repeated Group): مجموعه‌ای از اشیای غیرقابل تمایز در یک مسئله جایگشت. تعداد اعضای هر گروه در مخرج فرمول ظاهر می‌شود.