درهم ریختگی

درهم ریختگی (جایگشت). یک در هم ریختگی یا بی ترتیبی، یک جایگشت از اشیائی است که هیچ شئ در مکان اصلی خود نباشد. برای حل مسئله طرح شده در بعضی مسئله ها نیاز داریم تعداد در هم ریختگی های یک مجموعه با n شئ را تعیین کنیم.
تعداد در هم ریختگی ها یک مجموعه N عضوی:فرض کنید Dn نمایش تعداد درهم ریختگی های n شئ باشند برای مثال D2=۲ زیرا در هم ریختگی ها ۱۲۳ اعداد ۲۳۱. ۳۱۲ هستند برای هر عدد صحیح مثبت n , Dn را بااستفاده از اصل شمول و عدم شمول تعیین می کنیم:
D n = n ! { 1 − 1 1 ! + 1 2 ! − 1 3 ! + … + ( − 1 ) n 1 n ! } {\displaystyle 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 را ندارد به این معنی که: