Processing math: 5%

فهرست مندرجات

جایگشت‌های باتکرار

گاهی جایگشت‌هایی داریم که عناصر آن‌ها همگی متمایز نیستند. در این صفحه، چنین جایگشت‌هایی را بررسی می‌کنیم.

یک مثال

فرض کنید ۴ توپ قرمز، ۳ توپ آبی و ۲ توپ سبز داریم و می‌خواهیم این توپ‌ها را در یک ردیف بچینیم. توجه کنید توپ‌های هم‌رنگ، یک‌سان هستند و تمایزی ندارند. تعداد روش‌های این کار قطعن 9! نیست زیرا برخی از اشیاء ما متمایز نیستند و حق نداریم با فرمول جای‌گشت‌های خطی مسئله را حل کنیم. پس باید به دنبال راه حل دیگری باشیم.

ما ۹ جایگاه داریم که در آن‌ها می‌تواند توپ قرار بگیرد. باید ابتدا ۴ جایگشت برای توپ‌های قرمز، سپس ۳ جایگاه از ۵ جایگاه باقی‌مانده برای توپ‌های آبی و در انتها ۲ جایگاه از ۲ جایگاه باقی‌مانده برای توپ‌های سبز انتخاب کنیم. پس طبق فرمول ترکیب‌ها و اصل ضرب پاسخ برابر \binom{9}{4}\binom{5}{3}\binom{2}{2}=\frac{9!}{4!5!}\frac{5!}{3!2!}\frac{2!}{2!0!} =\frac{9!}{4!3!2!} خواهد بود. در ادامه فرمولی کلی برای جایگشت باتکرار پیدا می‌کنیم.

فرمول جایگشت باتکرار

فرض کنید k نوع شیء داریم که از نوع i-ام، a_i شیء موجود است. می‌خواهیم تعداد جایگشت‌های این اشیاء را بیابیم. همانند مثال قبل، پاسخ برابر است با: \binom{a_1+a_2+...+a_k}{a_1}\binom{a_2+a_2+...+a_k}{a_2}...\binom{a_k}{a_k} =\frac{(a_1+a_2+...+a_k)!}{a_1!(a_2+a_3+...+a_k)!}\frac{(a_2+a_3+...+a_k)!}{a_2!(a_3+a_4+...+a_k)!}...\frac{a_k!}{a_k!0!} پس پاسخ برابر است با: \frac{(a_1+a_2+...+a_k)!}{a_1!a_2!...a_k!} اگر فرض کنیم n=a_1+a_2+...+a_k، پاسخ برابر \frac{n!}{a_1!a_2!...a_k!} خواهد بود.

جایگشت با تکرار را با \binom{n}{a_1, a_2, ..., a_k} نیز نشان می‌دهند.

مثال:

  1. چند جایگشت از کلمه‌ی combination وجود دارد؟
  2. در چند جایگشت آن حرف t بعد از یکی از حروف n می‌آید؟
  3. در چند جایگشت آن، هیچ دو حرف صداداری، مجاور نیستند؟

پاسخ

  1. در این کلمه از هر یک از حروف o, i, n دو تا و از بقیه‌ی حروف یکی داریم. پس پاسخ برابر است با:\frac{11!}{2!2!2!}
  2. بلوک دو حرفی tn را یک عنصر می‌گیریم. بنابراین ۲ عنصر o، ۲ عنصر i و ۸ عنصر متفاوت دیگر باقی می‌ماند که تعداد جایگشت‌های‌شان برابر است با:\frac{10!}{2!2!}
  3. ابتدا حروف بی‌صدا را جایگشت می‌دهیم. این کار به \frac{6!}{2!} طریق قابل انجام است. حال بین حروف بی‌صدا ۷ فضا برای حروف دیگر به وجود می‌آید که در هر فضا، حداکثر ۱ حرف صدادار می‌تواند قرار گیرد. پس مکان‌های حروف صدادار، \binom{7}{5} حالت دارد. جایگشت دادن حروف صدادار نیز \frac{5!}{2!2!} حالت دارد. پس در کل پاسخ برابر \frac{6!}{2!}\binom{7}{5}\frac{5!}{2!2!} است.

مسائل نمونه