پریش

در ترکیبیات یک پریش یک جایگشت است که هیچ کدام از عناصر در مکان اصلی خود نمی‌باشند در حقیقت یک رابطهٔ $F$ وجود دارد از مجموعهٔ $S$ به خودش بدون آن که هیچ عضوی با خودش رابطه داشته باشد یعنی برای همهٔ $x$های عضو $S$ داریم $(F(x$ مخالف $x$ است . و یک مشکل تکراری محاسبهٔ تعداد پریش‌ها است مشکل شمارش پریش‌ها اولین بار در سال ۱۷۰۸ توسط Pierre Reymond بررسی شد و البته همزمان Nicholas Bernoulli روی این موضوع کار می‌کرد.

مثال‌ها

فرض کنید یک استاد می خواهد ۴ تا آزمون را بین ۴ تا دانشجو تقسیم کند که دانشجوی $A$ آزمون $A$ و دانشجوی $B$ هم آزمون $B$ را بدهد و $D$ و $C$ هم همین طور ولی پروفسور هنگام پخش برگه‌ها دچار اشتباه می‌شود و اکنون هیچکدام از دانشجویان برگهٔ خود را ندارد چندین راه برای برگه‌ها در دست دانشجویان وجود دارد؟ از میان ۲۴ تا جایگشت فقط ۹تا از آن‌ها پریش هستند.

BADC, BCDA, BDAC ,CADB, CDAB, CDBA ,DABC, DCAB, DCBA

و در هر کدام از جایگشت‌های دیگر حداقل یکی از دانشجویان برگهٔ خودش را دارد. و یا مثلاً می‌توان مسئله را این چنین بیان کرد که$n$ تا نامه داریم که نامهٔ۱ باید به نفر اول و نامهٔ۲ به نفر دوم و ... برسد و اگر پستچی دچار اشتباه شود به چند طریق ممکن است هیچکس نامهٔ خودش را نگیرد؟باز هم محاسبهٔ پریش !

شمارش پریش‌ها

برای شمارش تعداد پریش‌ها اصل متمم را به کار می بریم، نخست تعداد کل جایگشت های$n$ تایی را می شماریم که برابر $n!$ است و اکنون با توجه به اصل متمم تعداد جایگشت هایی که دست کم یکی از آن‌ها در جای خودش باشد را از آن کم می کنیم که تعداد آن برابر است با

$\tbinom{n}{1}(n-1)!=\tfrac{n!}{1!}$

و اکنون می بینیم جایگشت هایی که دو تا از آن‌ها در جای خودشان هستند دو بار کم شده‌اند پس طبق اصل شمول و عدم شمول یک بار دیگر آن‌ها را جمع می کنیم که تعداد آن‌ها برابر است با

$\tbinom{n}{2}(n-2)!=\tfrac{n!}{2!}$

و به همین ترتیب داریم... پس تعداد کل پریش‌ها برابر است با

$D(n)= n!-\tfrac{n!}{1!}+\tfrac{n!}{2!}-...+(-1)^n\tfrac{n!}{n!}$

$D(n)= n!(1-\tfrac{1}{1!}+\tfrac{1}{2!}-...+(-1)^n\tfrac{1}{n!})$

محاسبهٔ تعداد پریش‌ها وقتی$n$ به سمت $\infty$ میل می‌کند

وقتی $n$ به سمت $\infty$ میل می‌کند آن گاه مقدار

$D(n)= 1-\tfrac{1}{1!}+\tfrac{1}{2!}-...+(-1)^n\tfrac{1}{n!}$

به سمت $\tfrac{1}{e}$ می‌رود پس تعداد کل پریش‌ها برابر می‌شود با $\tfrac{n!}{e}$

پیوند بیشتر

• بیایید پریش بسازیم!
• Bogart, Kenneth P. and Doyle, Peter G. (1985).Non-sexist solution of the ménage problem
• Dickau, Robert M.. Derangement diagrams
• Dickau, Robert M..Figures Using Mathematica
• Hassani, Mehdi. Derangements and Applications. Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003.
• Weisstein, Eric W. Derangement. MathWorld–A Wolfram Web Resource.

منابع

• de Montmort, P. R. (1708). Essay d'analyse sur les jeux de hazard. Paris: Jacque Quillau. Seconde Edition, Revue & augmentée de plusieurs Lettres. Paris: Jacque Quillau. 1713.
• ^ Hassani, M. "Derangements and Applications." J. Integer Seq. 6, No. 03.1.2, 1-8, 2003