درهم‌ریختگی (جایگشت)

یک در هم ریختگی یا بی ترتیبی، یک جایگشت از اشیائی است که هیچ شئ در مکان اصلی خود نباشد. برای حل مسئله طرح شده در بعضی مسئله‌ها نیاز داریم تعداد در هم ریختگی‌های یک مجموعه با n شئ را تعیین کنیم.

تعداد در هم ریختگی‌ها یک مجموعه N عضوی: فرض کنید Dn نمایش تعداد درهم ریختگی‌های n شئ باشند برای مثال D2=۲ زیرا در هم ریختگی‌ها ۱۲۳ اعداد ۲۳۱. ۳۱۲ هستند برای هر عدد صحیح مثبت n , Dn را بااستفاده از اصل شمول و عدم شمول تعیین می‌کنیم:

$D_{n}=n!{\big \{}1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+\ldots +(-1)^{n}{\frac {1}{n!}}{\big \}}$

اثبات: فرض کنید یک جایگشت دارای ویژگی p1 است اگر عضو i ثابت نگه داشته شود. تعداد در هم ریختگی‌ها برابر با تعداد جایگشت‌هایی است که هیچ‌یک ویژگی‌های pi را به ازای i=۱٬۲,…. ,n را ندارد به این معنی که:

$D_{n}=N(p'_{1}p'_{2}\ldots p'_{n})$

با استفاده از اصل شمول و عدم شمول داریم:

$D_{n}=N-\sum _{i}^{n}N(P_{i})+\sum _{i<j}^{n}N(P_{i}P_{j})+\sum _{i<j<k}^{n}(P_{i}P_{j}P_{k})+\ldots +(-1)^{n}N(P_{1}P_{2}\ldots P_{n})$

که در ان N تعداد جایگشت‌های n عضو است. این معادله بیان می‌کند که تعداد جایگشت‌هایی که هیچ عضوی را ثابت نکه نمی‌دارد برابر است با تمام تعداد جایگشت‌ها منهای تعدادی که حداقل یک عضو را ثابت نگه می‌دارند.. به همین ترتیب تا آخر، حال همهٔ مقادیری که در سمت راست این معادله ظاهر می‌شوند اکنون پیدا می‌شوند. ابتدا توجه کنید که $N=n!$ زیرا N تنها تعداد کل جایگشت‌های nعضو است. همچنین ، $N(Pi)=(n-1)!$ ، این مطلب از قانون ضرب پیروی می‌کند، زیرا N(Pi) تعداد جایگشت‌هایی است که عضو iام این جایگشت مشخص می‌شود؛ ولی هر مکان باقیمانده می‌تواند به طور دلخواه پرشود. به طور مشابه داریم:

$N(p_{i}p_{j})=(n-2)!$

زیرا این مقدار تعداد جایگشت‌هایی است که عضوهای i و j را ثابت نگه می‌دارد؛ ولی بقیهٔ (n-2) عضو، می‌توانند بطور دلخواه پر شوند. بطور مشابه داریم:

$N(p_{i_{1}}p_{j_{1}}\ldots p_{i_{m}})=(n-m)!$

زیرا این مقدار تعداد جایگشت‌هایی است که عضوهای i و j را ثابت نگه می‌دارد؛ ولی بقیهٔ (n-m) عضو می‌توانند به طور اختیاری چیده شوند. از آنجایی که C(n,m) راه برای انتخاب m عضو از n عضو وجود دارد داریم:

$\sum _{i\leq j\leq k}^{n}N(P_{i})=C(n,1)(n-1)!$

$\sum _{1\leq i\leq j\leq k}^{n}N(P_{i}p_{j})=C(n,2)(n-2)!$

و در حالت کلی:

$\sum _{1\leq i_{1}\leq i_{2}\leq j_{m}\leq n}^{n}N(P_{i_{1}}p_{j_{1}}\ldots p_{j_{m}})=C(n,m)(n-m)!$

مثال

چایگشت ۲۱۴۵۳ یک در هم ریختگی از ۱۲۳۴۵ است زیرا هیچ رقمی در جای اصلی خود نیس در حالی که ۲۱۵۴۳ یک در هم ریختگی از ۱۲۳۴۵ نیست زیرا در این جایگشت ۴ در مکان درست خود است.

منابع

Kenneth H, Rosen (1998). "Counting". [https://www.amazon.com/Discrete- Mathematics-Applications-Kenneth-Rosen/dp/0072899050 Discrete Mathematics and its Applications]. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition. Retrieved 2007. {{cite book}}: Check |نشانی= value (help); Check date values in: |بازبینی= (help); line feed character in |نشانی= at position 33 (help)