اختلال و آشفتگی
این نوشتار نیازمند پیوند میانزبانی است. در صورت وجود، با توجه به خودآموز ترجمه، میانویکی مناسب را به نوشتار بیفزایید. |
در ریاضیات ترکیبیاتی، اختلال و آشفتگی یک جایگشت است که هیچیک از عوامل مجموعه در جایگاههای اصلی خود ظاهر نشوند که یک تابع دو طرفه (هم پوشا، هم یک به یک) φ از مجموعهٔ 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 در
φ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=۴ باشد ما میتوانیم تبدیلات اختلالهای به طول ۴٬۵ را اجرا کنیم: به ترتیب:
۵۱۴۳۲ → ۵۱۴۳۲۶ → ۵۱۴۶۲۳;
۳۱۴۲ → ۳۱۵۴۲ → ۳۱۵۴۲۶ → ۳۱۵۶۲۴
بنابراین اگر dn را به عنوان تعداد اختلالات در n نامه فرض میکنیم و d0 = 1, d1 = ۰را تعریف میکنیم، آنگاه dn حالت بازگشتی پیدا میکند:
و همچنین:
توجه داشته باشیم که فرمول بازگشتی مشابه زیر نیز برای فاکتوریلها با مقادیر ابتدایی متفاوت کار میکند که۱=!۱٬۱=!۰ و:
که به ما در اثبات رابطهٔ حدی زیر به ما کمک میکند. همچنین رابطه ی را میدانیم:
که با شروع با 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,g، یک اختلال φاز S وجود دارد به صورتی که
.
تعمیم دیگر مسئله زیر است:
چند آناگرام (تشکیل لغت یا جملهای از درهم ریختن کلمات یا لغات جمله دیگر) با هیچ حرف ثابتی از یک کلمهٔ داده شده وجود دارد؟
برای مثال برای کلمهای که فقط از دو حرف تشکیل شده، بگویید nتا حرف Aو mتا حرف B، جواب مشخصا با توجه به این که m=n است یا نه ۰ یا ۱ است، برای تنها راه شکل دادن آناگرام بدون حرفهای ثابت به این صورت است که تمام A را باB تعویض کنیم، و این فقط در صورتی است که اگر و تنها اگرm=n. در حالت کلی برای کلمهای با n1 حرف n2،... ,X1حرف nr … n1حرف Xr ، به صورتی زیر میشود (البته پس از استفاده از اصل شمول و عدم شمول):
به ازای دنبالهای از چند جملهایهای 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