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

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

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

<math>D_n=n!  \big\{1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + (-1)^{n}  \frac{1}{n!} \big\} </math>

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

<math>D_n=N( p'_1 p'_2 \ldots  p'_n)</math>

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

<math>D_n=N- \sum_i^n N(P_i)+ \sum_{i < j}^n N(P_iP_j  )+ \sum_{i < j < k}^n (P_iP_j P_k )+   \ldots +(-1)^{n} N(P_1P_2 \ldots P_n)</math>

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

<math>N(p_ip_j)=(n-2)!</math>

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

<math>N(p_{i_1} p_{j_1} \ldots p_{i_m})=(n-m)!</math>

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

<math> \sum_{i \leq j \leq k}^n N(P_i)=C(n,1)(n-1)!</math>

<math> \sum_{1 \leq  i \leq j \leq k}^n N(P_ip_j)=C(n,2)(n-2)!</math>

و در حالت کلی:

<math> \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)!</math>

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

== منابع ==
{{پانویس}}
{{یادکرد کتاب | نام خانوادگی۱ = Kenneth H| نام۱ = Rosen | فصل = Counting | عنوان = Discrete Mathematics and its Applications| سری = SIGS Reference Library | سال = 1998| ناشر = William C Brown Pub; 4th edition | شابک = 0072899050| نشانی = https://www.amazon.com/Discrete-
Mathematics-Applications-Kenneth-Rosen/dp/0072899050| بازبینی = 2007| زبان = en}}

[[رده:منطق]]