Ménage muammosi - Ménage problem

O'nta joy sozlamalari mavjud jadval. Ushbu stolda beshta erkak-ayol juftlik o'tirishi mumkin bo'lgan 3120 xil usullar mavjud, shunda erkaklar va ayollar bir-birini almashtirib turishadi va hech kim sherigining yonida o'tirmaydi.

Yilda kombinatoriya matematikasi, ménage muammo yoki problème des ménages^[1] erkaklar va ayollar bir-birini almashtirib turishi va o'z sherigi yonida hech kim o'tirmasligi uchun dumaloq ovqatlanish stoliga erkak-ayol juftliklarini joylashtirishning turli xil usullarini so'raydi. Ushbu muammo 1891 yilda tuzilgan Eduard Lukas va mustaqil ravishda, bir necha yil oldin, tomonidan Piter Gutri Tayt bilan bog'liq tugun nazariyasi.^[2] 3, 4, 5, ... ga teng bo'lgan juftliklar uchun o'tirish tartibi soni

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (ketma-ketlik A059375 ichida OEIS ).

Matematiklar formulalarni ishlab chiqdilar va takrorlanish tenglamalari ushbu raqamlarni va tegishli raqamlar ketma-ketligini hisoblash uchun. Ularning odob-axloq qoidalari va tugunlar nazariyasiga tatbiq etilishi bilan bir qatorda, bu raqamlar ham grafik nazariy talqin: ular sonlarini sanaydilar taalukli va Gamilton davrlari ba'zi bir grafikalar oilalarida.

Touchard formulasi

Ruxsat bering M_n uchun o'tirish tartibi sonini belgilang n juftliklar. Touchard (1934) formuladan olingan

{displaystyle M_ {n} = 2cdot n! sum _ {k = 0} ^ {n} (- 1) ^ {k} {frac {2n} {2n-k}} {2n-k ni tanlang k} (nk) !.}

Keyinchalik ko'plab ishlar ushbu formulaning muqobil dalillari va muammoning turli xil umumlashtirilgan versiyalariga sarflandi.

Boshqasi kindik uchun formula M_n jalb qilish Chebyshev polinomlari birinchi turdagi tomonidan berilgan Vayman va Mozer (1958).

Ménage raqamlari va ayollar uchun birinchi echimlar

2 × mavjudn! ayollarni o'tirish usullari: ayollar uchun ajratiladigan ikkita o'rindiq bor va ular mavjud n! ularni ma'lum bir o'rindiqda o'tirish usullari. Ayollar uchun har bir o'tirish tartibi mavjud

{displaystyle A_ {n} = sum _ {k = 0} ^ {n} (- 1) ^ {k} {frac {2n} {2n-k}} {2n-k ni tanlang k} (n-k)!}

erkaklarni o'tirish usullari; ushbu formula oddiygina 2 × ni chiqarib tashlaydin! Touchard formulasidan olingan omil. Natijada kichikroq raqamlar (yana, dan boshlab n = 3),

1, 2, 13, 80, 579, 4738, 43387, 439792, ... (ketma-ketlik) A000179 ichida OEIS )

deyiladi ménage raqamlari. Omil ${displaystyle {frac {2n} {2n-k}} {2n-k tanlang k}}$ shakllantirish usullarining soni $k$ qo'shni o'rindiqlarning bir-biriga mos kelmaydigan juftliklari yoki shunga teng ravishda ularning soni taalukli ning $k$ a qirralari tsikl grafigi ning $2 n$ tepaliklar. Uchun ifoda $A n$ ni qo'llashning bevosita natijasidir qo'shilish printsipi - chiqarib tashlash mos keladigan har bir chekkaning so'nggi nuqtalarida o'tirgan odamlardan juftlik bo'lishi kerak bo'lgan tartiblarga.

Ishiga qadar Bogart va Doyl (1986), ménage muammosiga echimlar, avvalambor, ayollar uchun barcha o'tiradigan joylarni topish, so'ngra bu qisman o'tirishlarning har biri uchun, erkaklarni sheriklaridan uzoqlashtirib, uni bajarish usullari sonini hisoblash shaklida amalga oshirildi. Bogart va Doylning ta'kidlashicha, Touchardning formulasi to'g'ridan-to'g'ri ayollarning ishtirokini inobatga olish o'rniga, barcha yashash joylarini ko'rib chiqish orqali olinishi mumkin.^[3] Biroq, Kirousis & Kontogeorgiou (2018) Bogart va Doylning bir nechta g'oyalaridan foydalangan holda yuqorida tavsiflangan eng sodda ayollar echimini topdi (garchi ular argumentni jinsi bo'lmagan tilda qayta ko'rib chiqishga harakat qilishgan bo'lsa ham).

Ménage raqamlari takrorlanish munosabati^[4]

{displaystyle A_ {n} = nA_ {n-1} + {frac {n} {n-2}} A_ {n-2} + {frac {4 (-1) ^ {n-1}} {n- 2}}}

va oddiyroq to'rt muddatli takrorlanish^[5]

{displaystyle displaystyle A_ {n} = nA_ {n-1} + 2A_ {n-2} - (n-4) A_ {n-3} -A_ {n-4},}

ulardan ménage raqamlarini osongina hisoblash mumkin.

Grafik-nazariy talqinlar

Oltita, sakkizta va o'nta vertikalli tojli grafikalar. Har bir grafikning tashqi tsikli Gamilton tsiklini hosil qiladi; sakkizta va o'nta vertikal grafikalarda boshqa Gemilton davrlari ham mavjud.

Ménage muammosining echimlari talqin qilinishi mumkin grafik-nazariy shartlari, kabi yo'naltirilgan Gamilton davrlari yilda toj grafikalari. A olib tashlash orqali toj grafigi hosil bo'ladi mukammal moslik dan to'liq ikki tomonlama grafik K_{n, n}; unda 2 born ikkita rangning tepalari va bitta rangning har bir tepasi boshqa rangning bitta tepasidan tashqari hamma bilan bog'langan. Ménage muammosida, grafaning tepalari erkaklar va ayollarni, qirralar esa bir-biriga yonma-yon o'tirishga ruxsat berilgan juft erkaklar va ayollarni anglatadi. Ushbu grafik har bir erkakni har bir ayol bilan bog'laydigan to'liq bipartitli grafadan erkak-ayol juftliklar tomonidan yaratilgan mukammal uyg'unlikni olib tashlash orqali hosil bo'ladi. Har qanday to'g'ri o'tirish tartibi jadval atrofida odamlarning ketma-ketligi bilan tavsiflanishi mumkin, bu grafilda Hamilton tsiklini hosil qiladi. Shu bilan birga, ikkita gililton tsikli, agar ular bir xil tepaliklarni boshlang'ich tepadan qat'i nazar, bir xil tsiklik tartibda birlashtirsa, teng deb hisoblanadi, ménage muammosida esa boshlang'ich pozitsiyasi muhim hisoblanadi: agar Elis Choy partiyasi, barcha mehmonlar o'z pozitsiyalarini bitta o'rindiqqa almashtiradilar, xuddi shu tsikl bilan tavsiflangan bo'lishiga qaramay, bu boshqa joy ajratish tartibi hisoblanadi. Shuning uchun toj grafigidagi yo'naltirilgan Hamilton tsikllari soni 2 baravar kichikn o'tirish joylari sonidan,^[6] lekin kattaroq (n - 1)! ménage raqamlaridan ko'ra. Ushbu grafikalardagi tsikllar sonining ketma-ketligi (avvalgidek, boshlangan n = 3) bo'ladi

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (ketma-ketlik A094047 ichida OEIS ).

Muammoning ikkinchi grafik-nazariy tavsifi ham mumkin. Ayollar o'tirgandan so'ng, qolgan erkaklar uchun mumkin bo'lgan joylarni quyidagicha tavsiflash mumkin mukammal mosliklar to'liq Gipartitli grafildan bitta Hamilton tsiklini olib tashlash natijasida hosil bo'lgan grafikada; grafada ochiq o'rindiqlarni erkaklar bilan bog'laydigan qirralar mavjud va tsiklning olib tashlanishi erkaklar xotinlariga ulashgan ochiq o'rindiqlarning birida o'tirishni taqiqlashga to'g'ri keladi. Ikki tomonlama grafikada mosliklarni hisoblash muammosi va shuning uchun fortiori ménage raqamlarini hisoblash masalasini, yordamida hal qilish mumkin doimiy aniq 0-1 matritsalar. Ménage muammosida, masalaning ushbu nuqtai nazaridan kelib chiqadigan matritsa sirkulant matritsa unda hosil bo'ladigan qatorning ikkala qo'shni elementidan tashqari barchasi teng $1$ .^[7]

Tugun nazariyasi

Taitning ménage muammosini o'rganishga turtki to'liq ro'yxatini topishga urinishdan kelib chiqqan matematik tugunlar berilgan bilan o'tish joylari soni, demoq n. Yilda Dowker yozuvi tugunli diagrammalar uchun, uning dastlabki shakli Tait tomonidan ishlatilgan, 2n tugun bo'ylab ketma-ket ketma-ketlikda o'z-o'zidan kesib o'tadigan nuqtalar 2 bilan belgilanadin 1 dan 2 gacha bo'lgan raqamlarn. Qisqartirilgan diagrammada o'tish joyidagi ikkita yorliq ketma-ket bo'lishi mumkin emas, shuning uchun tugunni ko'rsatish uchun Dowker belgisida ishlatiladigan har bir o'tish joyidagi juft juft yorliqlar to'plami vertikalga ega bo'lgan grafadagi mukammal moslik sifatida talqin qilinishi mumkin. 1 dan 2 gacha bo'lgan har bir raqamn va har xil paritetga ega bo'lgan va ketma-ket modul 2 bo'lgan har bir juftlik orasidagi chekkan. Ushbu grafik Hamilton tsiklini (ketma-ket raqamlarni bog'lash) to'liq ikki tomonlama grafikadan olib tashlash orqali hosil bo'ladi (har xil tenglikdagi barcha juft juftlarni bir-biriga bog'lash) va shuning uchun u ménage soniga teng bo'lgan bir nechta mos kelishga ega. Uchun o'zgaruvchan tugunlar, bu moslik tugun diagrammasini o'zi tasvirlash uchun etarli; boshqa tugunlar uchun har bir o'tish juftligi uchun qo'shimcha ijobiy yoki salbiy belgini belgilash kerak, bu o'tish joyining ikkita ipidan qaysi biri boshqa ipning ustida joylashganligini aniqlash kerak.

Shu bilan birga, tugunlarni ro'yxatlash muammosi ménage muammosida mavjud bo'lmagan ba'zi bir qo'shimcha simmetriyalarga ega: agar belgi boshqa o'tish nuqtasida boshlasa, bitta tugun diagrammasi uchun har xil Dowker yozuvlarini oladi va bu har xil yozuvlar hammasi bir xil bo'lgan deb hisoblanishi kerak. diagramma. Shu sababli, bir-biridan a bilan farq qiluvchi ikkita mos kelish tsiklik almashtirish ekvivalent sifatida ko'rib chiqilishi va faqat bir marta hisoblanishi kerak. Gilbert (1956) turli xil mosliklar soni ekanligini ko'rsatib, ushbu o'zgartirilgan ro'yxatga olish muammosini hal qildi

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (ketma-ketlik) A002484 ichida OEIS ).

Shuningdek qarang

Oberwolfach muammosi, stollarda ovqatlanishni tashkil qilish bilan bog'liq boshqa matematik muammo

Izohlar

^ "Ménage" bu Frantsuzcha "uy" so'zi (bu erda erkak-ayol juftlikni nazarda tutadi).
^ Dutka (1986).
^ Glik (1986).
^ Muir (1882); Lizant (1891). Keyinchalik murakkab takrorlanishlar ilgari Cayley va Muir (1878).
^ Muir (1882); Canfield & Wormald (1987).
^ Passmore (2005).
^ Muir (1878); Eades, Praeger & Seberry (1983); Kräuter (1984); Xenderson (1975).

Adabiyotlar

Bogart, Kennet P.; Doyl, Piter G. (1986), "Ménage muammosining jinsiy bo'lmagan echimi", Amerika matematik oyligi, 93 (7): 514–519, doi:10.2307/2323022, JSTOR 2323022, JANOB 0856291.
Bong, Nguyen-Xu (1998), "Lukas raqamlari va menejment muammosi", Fan va texnologiyalar bo'yicha matematik ta'limning xalqaro jurnali, 29 (5): 647–661, doi:10.1080/0020739980290502, JANOB 1649926.
Kanfild, E. Rodni; Vormald, Nikolay C. (1987), "Ménage raqamlari, bijections va P-recursiveness", Diskret matematika, 63 (2–3): 117–129, doi:10.1016 / 0012-365X (87) 90002-1, JANOB 0885491.
Dörri, Geynrix (1965), "Lukasning turmush qurgan juftliklari muammosi", Elementar matematikaning 100 buyuk masalalari, Dover, 27-33 betlar, ISBN 978-0-486-61348-2. Devid Antin tomonidan tarjima qilingan.
Dutka, Jak (1986), "Problème des ménages to'g'risida", Matematik razvedka, 8 (3): 18–33, doi:10.1007 / BF03025785, JANOB 0846991.
Eades, Butrus; Praeger, Cheryl E.; Seberry, Jennifer R. (1983), "Sirkulant (0,1) matritsalarning doimiyligi to'g'risida ba'zi fikrlar", Utilitas Mathematica, 23: 145–159, JANOB 0703136.
Gilbert, E. N. (1956), "Mnage permutations tugunlari va sinflari", Scripta Mathematica, 22: 228–233, JANOB 0090568.
Glik, Jeyms (1986 yil 28 oktyabr), "Matematik + seksizm: muammo", Nyu-York Tayms.
Xenderson, J. R. (1975), "Har bir satrda kamida ikkita nolga teng bo'lgan (0,1) -matrisalarning doimiyligi", Kanada matematik byulleteni, 18 (3): 353–358, doi:10.4153 / CMB-1975-064-6, JANOB 0399127.
Xolst, Lars (1991), "ehtimoliy nuqtai nazardan" problème des ménages "to'g'risida" Statistika va ehtimollik xatlari, 11 (3): 225–231, doi:10.1016 / 0167-7152 (91) 90147-J, JANOB 1097978.
Kaplanskiy, Irving (1943), "Problème des ménages echimi", Amerika Matematik Jamiyati Axborotnomasi, 49 (10): 784–785, doi:10.1090 / S0002-9904-1943-08035-4, JANOB 0009006.
Kaplanskiy, Irving; Riordan, J. (1946), "problème des ménages", Scripta Mathematica, 12: 113–124, JANOB 0019074.
Kirousis, L .; Kontogeorgiou, G. (2018), "102.18 The problème des ménages qayta ko'rib chiqildi ", Matematik gazeta, 102 (553): 147–149, arXiv:1607.04115, doi:10.1017 / mag.2018.27.
Kräuter, Arnold Richard (1984), "Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen", Séminaire Lotaringien de Kombinatuar (nemis tilida), B11b.
Leyzant, Charlz-Anj (1891), "Sur deux problèmes de permutations", Vie de la sociéte, Xabar byulleteni de Société Mathématique de France (frantsuz tilida), 19: 105–108.
Lukas, Eduard (1891), Théorie des Nombres, Parij: Gautier-Villars, 491–495 betlar.
Muir, Tomas (1878), "Professor Taitning tartibga solish muammosi to'g'risida", Edinburg qirollik jamiyati materiallari, 9: 382–391. (388-391-betlar) tomonidan qo'shimchalar kiritilgan Artur Keyli.
Muir, Tomas (1882), "Tartibga solish muammosi to'g'risida qo'shimcha eslatma", Edinburg qirollik jamiyati materiallari, 11: 187–190.
Passmore, Amanda F. (2005), Ménage muammosining elementar echimi, CiteSeerX 10.1.1.96.8324.
Riordan, Jon (1952), "Ménage raqamlarining arifmetikasi", Dyuk Matematik jurnali, 19 (1): 27–30, doi:10.1215 / S0012-7094-52-01904-2, JANOB 0045680.
Takaks, Layos (1981), "On the" problème des ménages"", Diskret matematika, 36 (3): 289–297, doi:10.1016 / S0012-365X (81) 80024-6, JANOB 0675360.
Touchard, J. (1934), "Sur un problème de permutations", C. R. Akad. Ilmiy ish. Parij, 198 (631–633).
Vayman, Maks; Mozer, Leo (1958), "Problème des ménages to'g'risida", Kanada matematika jurnali, 10 (3): 468–480, doi:10.4153 / cjm-1958-045-6, JANOB 0095127.

Tashqi havolalar

[1] "Ménage" bu Frantsuzcha "uy" so'zi (bu erda erkak-ayol juftlikni nazarda tutadi).

[2] Dutka (1986).

[3] Glik (1986).

[4] Muir (1882); Lizant (1891). Keyinchalik murakkab takrorlanishlar ilgari Cayley va Muir (1878).

[5] Muir (1882); Canfield & Wormald (1987).

[6] Passmore (2005).

[7] Muir (1878); Eades, Praeger & Seberry (1983); Kräuter (1984); Xenderson (1975).

[1]

[2]

[3]

[4]

[5]

[6]

[7]