پریش‌ها

پریش (Derangement) از پریشانی می‌آید. هر گاه هیچ کس سر جای خود نباشد، گوییم پریش رخ داده است. در ترکیبیات شمارشی، به جای‌گشت $$<\pi_1, \pi_2, ..., \pi_n>$$ از اعداد $1, 2, ..., n$ پریش گوییم، اگر هیچ $1 \le i \le n$ وجود نداشته باشد که $\pi_i=i$ باشد (در واقع هیچ عنصری سر جای خود نباشد). برای مثال، جایگشت $<3, 1, 4, 2>$ یک پریش ۴-عنصره است. تعداد پریش‌های $n$-عنصره را با $D_n$ یا $!n$ (با $n!$ اشتباه نگیرید) نشان می‌دهند.

پریش‌ها به طور رسمی، برای نخستین بار توسط ریموند و برنولی بررسی شدند.

مثال: تمام پریش‌های ۳-عنصره را بنویسید.

می‌خواهیم تعداد پریش‌های $n$-عنصره یا همان $D_n$ را پیدا کنیم. $n$ زیرمجموعه‌ی $A_1, A_2, ..., A_n$ از تمام جای‌گشت‌های $n$-عنصره، به این صورت تعریف می‌کنیم که $A_i$ شامل جای‌گشت‌هایی است که عدد $i$ در مکان $i$ (سر جای خودش) باشد. ما باید تعداد جای‌گشت‌هایی که در هیچ یک از $A_i$ها نیستند را بشماریم. در واقع باید مقدار $|(A_1 \cup A_2 \cup ... \cup A_n)'|$ را محاسبه کنیم. طبق اصل شمول و عدم شمول داریم: $$D_n = |(A_1 \cup A_2 \cup ... \cup A_n)'|$$ $$ = n! - \Big( \sum_{i=1}^{n}|A_i| - \sum_{1 \le i < j \le n}|A_i \cap A_j| + ... + (-1)^{n-1}|A_1 \cap A_2 \cap ... \cap A_n|\Big)$$

حال اعداد صحیح $1 \le i_1 < i_2 < ... < i_k \le n$ و زیرمجموعه‌های $A_{i_1}, A_{i_2}, ..., A_{i_k}$ را در نظر بگیرید. می‌خواهیم تعداد اعضای $$A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}$$ را حساب کنیم. این اشتراک $k$-تایی، شامل جای‌گشت‌هایی است که اعداد $i_1, i_2, ..., i_k$ سر جای خود باشند. تعداد این جای‌گشت‌ها، برابر $(n-k)!$ است (این $k$ عدد باید سر جای خود باشند و بقیه‌ی اعداد، یک جای‌گشت $n-k$ عنصره در میان خود تشکیل می‌دهند).

به محاسبه‌ی $D_n$ برمی‌گردیم. داریم: $$D_n = n! - \Bigg(\binom{n}{1}(n-1)! - \binom{n}{2}(n-2)! + ... + (-1)^{n-1}\binom{n}{n}(n-n)!\Bigg)$$ $$ = n! - \sum_{i=1}^{n}(-1)^{i-1}\binom{n}{i}(n-i)!$$ $$ = n! + \sum_{i=1}^{n}(-1)^i\binom{n}{i}(n-i)!$$ $$ = n! + \sum_{i=1}^{n}(-1)^i\frac{n!(n-i)!}{i!(n-i)!}$$ $$ = n! + \sum_{i=1}^{n}(-1)^i\frac{n!}{i!}$$ پس: $$D_n = n! \Big(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ... + (-1)^n\frac{1}{n!}\Big)$$

مثال: چند پریش از اعداد $1, 2, ..., 10$ وجود دارد که عدد ۹ در مکان ۱۰-ام جایگشت آمده باشد؟

مثال: ثابت کنید: $$\sum_{i=0}^n\binom{n}{i}D_i=n!$$

توجه: قبل از دیدن این قسمت، بهتر است روابط بازگشتی را بخوانید.

می‌خواهیم یک رابطه‌ی بازگشتی برای $!n$ پیدا کنیم. فرض کنید عدد ۱ در جای‌گاه شماره $i$ باشد. در این صورت برای جای‌گاه عدد $i$، دو حالت داریم:

1. عدد $i$ در جای‌گاه ۱ باشد. در این صورت بقیه‌ی اعداد به $D_{n-2}$ حالت می‌توانند جای‌گشت بگیرند.
2. عدد $i$ در جای‌گاه ۱ نباشد. در این صورت $n-1$ عدد داریم که $i$ نباید در مکان ۱ باشد و هر عدد دیگر نباید در مکان خودش باشد. پس تعداد روش‌های قرار گرفتن این $n-1$ عدد، برابر تعداد پریش‌های

$(n-1)$ -عنصره یا همان $D_{n-1}$ است. پس نتیجه می‌شود: $$D_n=(n-1)\big(D_{n-1}+D_{n-2} \big)$$ پس یک رابطه‌ی بازگشتی برای $D_n$ به دست آمد. اگر نماد $!n$ را استفاده کنیم، داریم: $$!n=(n-1)\big(!(n-1)+!(n-2)\big)$$ از طرفی در بحث فاکتوریل دیدیم: $$n!=(n-1)\big((n-1)!+(n-2)!\big)$$ دور از ذهن نیست که شاید یکی از انگیزه‌های ایجاد نماد $!n$، همین شباهت روابط بازگشتی $!n$ و $n!$ باشد.

روابط بازگشتی دیگری نیز برای $D_n$ می‌توان تعریف کرد. برای مثال، رابطه‌ی بازگشتی زیر، مستقیمن از روی فرمول $D_n$ و هم‌چنین با ساده کردن رابطه‌ي بازگشتی بالا، به دست می‌آید: $$D_n=nD_{n-1}+(-1)^n$$

توجه: قبل از دیدن این قسمت، بهتر است روابط بازگشتی را بخوانید.

فرض کنید $n, k$، اعداد طبیعی باشند که $1 \le k \le n$ . جای‌گشت‌هایی از اعداد $1, 2, ..., n$ را در نظر بگیرید، که هیچ کدام از اعداد $1, 2, ..., k$ سر جای خود نباشند. تعداد این جای‌گشت‌ها را با $D_{n, k}$ نشان می‌دهیم. به وضوح داریم: $$D_{n, 0}=n!$$ و $$D_{n, n}=!n$$

مثال: $D_{4, 3}$ را بیابید.

می‌خواهیم $D_{n, k}$ را پیدا کنیم. ابتدا یک رابطه‌ی بازگشتی برای $D_{n, k}$ می‌یابیم. جای‌گشت‌های متناظر $D_{n, k}$ زیرمجموعه‌از جای‌گشت‌های متناظر $D_{n, k-1}$ هستند. از $D_{n, k-1}$ باید جای‌گشت‌هایی را کم کنیم که عدد $k$ سر جای خودش باشد که تعداد آن‌ها برابر $D_{n-1,k-1}$ است زیرا در $n-1$ عدد باقی‌مانده، اعداد $1, 2, ..., k-1$ نباید سر جای خود بیایند. پس داریم: $$D_{n, k}=D_{n, k-1}-D_{n-1, k-1}$$

حال با استفاده از اصل شمول و عدم شمول، فرمول صریح $D_n$ را می‌یابیم. زیرمجموعه‌های $A_1, A_2, ..., A_k$ از جای‌گشت‌های اعداد $1, 2, ..., n$ را به این صورت تعریف می‌کنیم که $A_i$ شامل جای‌گشت‌هایی باشد که عدد $i$، سر جای خود باشد. ما باید $|A_1 \cup A_2 \cup ... \cup A_k|$ را محاسبه کنیم. داریم: $$D_{n, k}=|A_1 \cup A_2 \cup ... \cup A_k|$$ $$= n!-\Big(\sum_{i=1}^k |A_i| - \sum_{1 \le i < j \le k} |A_i \cap A_j| + ... + (-1)^{k-1}|A_1 \cap A_2 \cap ... \cap A_k| \Big)$$ از طرفی به ازای هر $1 \le i_1 < i_2 < ... < i_m \le k$ ، مجموعه‌ی $A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_m}$ شامل جای‌گشت‌هایی است که اعداد $i_1, i_2, ..., i_m$ سر جای خود باشند که تعداد جای‌گشت‌ها با این ویژگی، برابر $(n-m)!$ است. پس داریم: $$D_{n, k}=n!-\Big(\binom{k}{1}(n-1)! - \binom{k}{2}(n-2)! + ... + (-1)^{k-1}\binom{k}{k}(n-k)! \Big)$$ پس: $$D_{n, k}=\sum_{i=0}^k (-1)^i \binom{k}{i}(n-i)!$$

توجه: این قسمت برای کسانی است که با عدد نپر و مفهوم حد آشنا هستند. دیدن این قسمت مفید است، اما در صورتی که مطالب این قسمت را نفهمیدید، نگران چیزی نباشید.

عدد $e$ (عدد نپر)، یک عدد ثابت گنگ است و تقریبن برابر با $2/71$ می‌باشد. در ریاضیات ثابت می‌شود به ازای هر عدد حقیقی $x$: $$e^x=\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + ...$$ از طرفی با قرار دادن $x=-1$ داریم: $$e^{-1} = \frac{1}{e} = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ...$$ به شباهت مقدار $\frac{1}{e}$ با عبارت $\big(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ... + (-1)^n\frac{1}{n!}\Big)$ که در فرمول $D_n$ تأثیر داشت، دقت کنید. در بسط نوشته شده در بالا برای $\frac{1}{e}$ جملات هر چه جلوتر می‌روند کوچک‌تر می‌شوند و تأثیرشان کم‌تر می‌شود. پس می‌توان نتیجه گرفت: $$D_n \approx \frac{n!}{e}$$ برای محاسبه‌ی دقیق $D_n$ با استفاده از $e$، ثابت می‌شود که $D_n$ برابر نزدیک‌ترین عدد صحیح به $\frac{n!}{e}$ است. هم‌چنین ثابت می‌شود: $$D_n=\big\lfloor \frac{n!}{e}+\frac{1}{2} \big\rfloor$$ پس یک فرمول بسته نیز برای $e$ به دست آمد.

حال سراغ نکته‌ای دیگر می‌رویم. می‌خواهیم احتمال آن که یک جای‌گشت، پریش باشد را محاسبه کنیم. به وضوح این احتمال برابر است با: $$p=\frac{D_n}{n!}$$ فرض کنید $n$ به حد کافی بزرگ باشد و به $\infty$ میل کند. پس: $$p=lim_{n \rightarrow \infty}\frac{D_n}{n!}=\frac{n!\times \frac{1}{e}}{n!}=\frac{1}{e}$$

پس اگر $n$ به حد کافی بزرگ باشد، از حدود هر ۳ جای‌گشت تصادفی، یکی از آن‌ها پریش است! البته باز هم به دلیل کوچک شدن جملات در سری دنباله، در $n$های کوچک نیز این امر مشاهده می‌شود.

در نمودار زیر می‌توانید نحوه‌ی رشد $D_n$ با رشد $n$ را ببینید:

برای $D_{n, k}$ نیز می‌توان ثابت کرد: $$D_{n, k} \approx \frac{n!}{e^{\frac{k}{n}}}$$ و $$lim_{n \rightarrow \infty} \frac{D_{n, k}}{n!}=e^{-\frac{k}{n}}$$

پرسش: فرض کنید $C_n$ تعداد جای‌گشت‌هایی از اعداد $1, 2, ..., n$ باشد که به ازای هیچ $1 \le i < n$ ، عدد $i+1$ بلافاصله بعد از عدد $i$ نیامده باشد.

1. یک فرمول برای $C_n$ بیابید.
2. ثابت کنید:

$$C_n = D_n + D_{n-1}$$

پرسش: فرض کنید $D_n(k)$ برابر تعداد جای‌گشت‌هایی از اعداد $1, 2, ..., n$ باشد که دقیقن $k$ عدد دارند که سر جای خودشان آمده‌اند.

1. ثابت کنید:

$$\sum_{k=0}^n(k-1)^2D_n(k)=n!$$ (المپیاد ریاضی آلمان غربی، ۱۹۸۷)

1. ثابت کنید:

$$\sum_{k=0}^n kD_n(k)=n!$$ (المپیاد بین‌المللی ریاضی، ۱۹۸۷)

1. پرسش ۲ مرحله اول دوره‌ی ۵

1. James Tanton, 2010, Thinking Mathematics/Volume 2
2. D. Karl, 1988, Rencontres reencountered, the college maths, I.
3. Holton Derek, 2011, A Second Step to Mathematical Olympiad Problems, Australia, World Scientific
4. derangements-essay2.pdf
5. http://en.wikipedia.org/wiki/Derangement
6. http://en.wikipedia.org/wiki/Random_permutation_statistics
7. https://cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.html
8. http://mathworld.wolfram.com/Derangement.html