المپدیا

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

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:جایگشت‌های باتکرار

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

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

یک مثال

فرض کنید ۴ توپ قرمز، ۳ توپ آبی و ۲ توپ سبز داریم و می‌خواهیم این توپ‌ها را در یک ردیف بچینیم. توجه کنید توپ‌های هم‌رنگ، یک‌سان هستند و تمایزی ندارند. تعداد روش‌های این کار قطعن $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!}$$ است.

مسائل نمونه


ابزار صفحه