اختلال و آشفتگی

در ریاضیات ترکیبیاتی، اختلال و آشفتگی یک جایگشت است که هیچ‌یک از عوامل مجموعه در جایگاه‌های اصلی خود ظاهر نشوند که یک تابع دو طرفه (هم پوشا، هم یک به یک) φ از مجموعهٔ S به روی خودش، بدون نقطه ثابت، است: برای تمام xها داخل S، φ(x) ≠ x مشکلی که ما زیاد به آن برمی‌خوریم محاسبهٔ تعداد اختلال‌ها بر حسب یک تابع از تعداد اعضای مجموعه (اغلب با محدودیت‌های اضافی) است. این اعداد زیرفاکتوریل‌ها نام دارند و حالت خاصی از «اعداد مقابله‌ای» هستند. در ابتدا مشکل شمردن اختلالات مورد توجه پیر ریموند دی مونت مورت(Pierre Raymond de Montmort)در سال ۱۷۰۸ قرار گرفت و در سال ۱۷۱۳ همزمان با برنولی این مسئله را حل کرد.

مثالها

فرض کنید استادی برای چهار دانشجو ۴ نمره داده است. دانشجوی اول ،Aدر امتحان “A” گرفته و دانشجوی Bدر امتحان “B” گرفته است و به همین صورت. به هر حال هنگام پس دادن برگه‌ها، برگه‌ها جابه‌جا می‌شوند و حالا هیچ‌یک از دانشجویان برگه درست خود را ندارند. حالا سؤال این است که "به چند طریق برگه‌ها می‌توانند به این صورت به هم بریزند؟"از میان ۲۴ جایگشت ممکن برای پس دادن برگه‌ها فقط در ۹ حالت اختلال داریم: BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA. در هر حالت جایگشت از این مجموعهٔ ۴ عضوی حداقل یک دانشجو برگه درست را می‌گیرد. مدل دیگر این مسئله این است که وقتی تعداد راه‌هایی را می‌خواهیم که n نامه که هر کدام به شخص خاصی اشاره دارد را می‌توان درون n پاکت نامهٔ از قبل آدرس گذاری شده گذاست که هیچ نامه‌ای در پاکت نامه خاص خود نباشد.

محاسبهٔ تعداد اختلالات

یک دیدگاه برای محاسبهٔ تعداد اختلالها، استفاده از استقرا است. ابتدا فرض کنید اگر φ_n هر اختلال اعداد طبیعی { 1, … , n }باشد، آنگاه به ازای بعضی مقادیر k در

{ 1, … , n − ۱ }

φ_n(n) = kسپس اگر ما (k,n) را که n,k را جابجا می‌کند به عنوان جایگشت { 1, … , n } فرض کنیم و φ_n-1 را ترکیب (k, n) o φ_n-1)) فرض کنیم آنگاه φ_n-1(n) = n و:

• φ_n-1(k) ≠ k، پس φ_n-1 یک اختلال در { 1, … , n − ۱ } است یا
• φ_n-1(k) = k، و برای تمام xها x ≠ k, φ_n-1(x) ≠ x

در مورد قبلی، φ_n-1 یک اختلال در مجموعه { 1, … , n − ۱ } به استثنا k، یعنیφ_n-2 = ((k,n − 1) o φ_n-1 o (k,n−۱یک اختلال از مجموعه { 1, … , n − ۲ }. به عنوان مثال برای این دو مورد، این دو اختلال ۶عاملی، که جانشینی‌های بالا را روی آنها انجام می‌دهیم، در نظر بگیرید:

۵۱۴۶۲۳ → (۵۱۴۳۲)۶;

۳۱۵۶۲۴ → (۳۱۵۴۲)۶ → (۳۱۴۲)۵۶

مطابقت توصیف شدهٔ بالا ۱به۱ است، معکوس این موضوع نیز درست :دقیقا (n-1)راه برای تبدیل هر اختلال (n-1)عاملی به اختلال n عاملی وجود دارد و (n-1)راه برای تبدیل هر اختلال (n-2) عاملی به اختلال n عاملی وجود دارد. برای مثال، اگر n=۶،k=۴ باشد ما می‌توانیم تبدیلات اختلال‌های به طول ۴٬۵ را اجرا کنیم: به ترتیب:

۵۱۴۳۲ → ۵۱۴۳۲۶ → ۵۱۴۶۲۳;

۳۱۴۲ → ۳۱۵۴۲ → ۳۱۵۴۲۶ → ۳۱۵۶۲۴

بنابراین اگر d_n را به عنوان تعداد اختلالات در n نامه فرض می‌کنیم و d₀ = 1, d₁ = ۰را تعریف می‌کنیم، آنگاه d_n حالت بازگشتی پیدا می‌کند:

$d_{n}=(n-1)(d_{n-1}+d_{n-2})\,$

و همچنین:

$d_{n}=nd_{n-1}+(-1)^{n},\quad n\geq 1$

توجه داشته باشیم که فرمول بازگشتی مشابه زیر نیز برای فاکتوریل‌ها با مقادیر ابتدایی متفاوت کار می‌کند که۱=!۱٬۱=!۰ و:

$n!=(n-1)((n-1)!+(n-2)!)\,$

که به ما در اثبات رابطهٔ حدی زیر به ما کمک می‌کند. همچنین رابطه ی را می‌دانیم:

$d_{n}=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}$

$d_{n}=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor =\left({\text{nearest integer to }}{\frac {n!}{e}}\right),\quad n\geq 1$

$d_{n}=\left\lfloor (e+e^{-1})n!\right\rfloor -\lfloor en!\rfloor ,\quad n\geq 2.$

که با شروع با n=۰، تعداد اختلال‌ها برابر:

۱, ۰, ۱, ۲, ۹, ۴۴, ۲۶۵, ۱۸۵۴, ۱۴۸۳۳, ۱۳۳۴۹۶, ۱۳۳۴۹۶۱, ۱۴۶۸۴۵۷۰, ۱۷۶۲۱۴۸۴۱, ۲۲۹۰۷۹۲۹۳۲, ...

این اعداد زیرفاکتورل یا اعداد مقابله‌ای نام دارند.

حد بینهایت

با استفاده از این بازگشت می‌توان نشان داد، که حد:

$\lim _{n\to \infty }{d_{n} \over n!}={1 \over e}\approx 0.3679\dots .$

این حد احتمال

p_n = d_n/n!

که یک جایگشت تصادفی یک اختلال است. این احتمال به صورت نسبتاً سریعی به این حد میل می‌کند.

شاید یک راه دیگر معروف در محاسبهٔ اختلال‌ها استفاده از اصل شمول و عدم شمول باشد.

تعمیم

مسئله مقابله(problème des rencontres) می‌پرسد چه تعداد از جایگشت‌های به طول n دقیقاً k نقطهٔ ثابت دارند.

اختلال مثالی از بحث گسترده‌تر جایگشت‌های قید دار است، برای مثال مسئله مناژ(ménage problem)می‌پرسد اگر n زوج به صورت دختر-پسر-دختر-پسر… دور یک میز دایره‌ای شکل نشسته باشند، به چند طریق آنها می‌توانند بشینند که هیچ مردی کنار همسر خود ننشسته باشد؟

به صورت رسمی‌تر، مجموعه‌های A,S داده شده‌اند و بعضی از مجموعه‌های U,V از A → S، همچنین می‌خواهیم تعداد زوج مرتب‌های تابع‌های (f,g) به صورتی که f در U و g در V و برای تمام aها در A

f(a)≠g(a)

به عبارت دیگر، برای هر f,g، یک اختلال φاز S وجود دارد به صورتی که

f(a) = φ(g(a))

.

تعمیم دیگر مسئله زیر است:

چند آناگرام (تشکیل لغت یا جمله‌ای از درهم ریختن کلمات یا لغات جمله دیگر) با هیچ حرف ثابتی از یک کلمهٔ داده شده وجود دارد؟

برای مثال برای کلمه‌ای که فقط از دو حرف تشکیل شده، بگویید nتا حرف Aو mتا حرف B، جواب مشخصا با توجه به این که m=n است یا نه ۰ یا ۱ است، برای تنها راه شکل دادن آناگرام بدون حرفهای ثابت به این صورت است که تمام A را باB تعویض کنیم، و این فقط در صورتی است که اگر و تنها اگرm=n. در حالت کلی برای کلمه‌ای با n₁ حرف n₂،... ,X₁حرف n_r … n₁حرف X_r ، به صورتی زیر می‌شود (البته پس از استفاده از اصل شمول و عدم شمول):

$\int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)e^{-x}\,dx,$

به ازای دنباله‌ای از چند جمله‌ای‌های Pn، که Pn از درجه nاست؛ ولی جواب بالا به ازای حالت r=۲ رابطهٔ تعامد می‌دهد، به گونه‌ای که Pnها چند جمله‌ای‌های لاگویر(Laguerre polynomials) هستند.

منابع

• 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