Yosh-Fibonachchi panjarasi

Young-Fibonachchi grafigi, Young-Fibonachchi panjarasining Hasse diagrammasi .

Matematikada Alfred Yang va Leonardo Fibonachchi nomi bilan atalgan Young-Fibonachchi grafigi va Young-Fibonachchi panjarasi 1 va 2 raqamlari ketma-ketligini oʻz ichiga olgan bir-biriga chambarchas bogʻliq ikkita tuzilmadan iboratdir. Ushbu turdagi har qanday raqam ketma-ketligiga daraja berilishi mumkin, uning raqamlari yigʻindisi: masalan, 11212 darajasi 1 ga teng.1+1+2+1+2=7. Qadimgi Hindistonda maʼlum boʻlganidek, berilgan darajali ketma-ketliklar soni Fibonachchi raqamidir . Young-Fibonachchi panjarasi cheksiz modulli panjara boʻlib, uning elementlari sifatida ushbu raqamli ketma-ketliklarga ega boʻlib, ushbu daraja tuzilishiga mos keladi. Young-Fibonachchi grafigi bu panjaraning grafigi boʻlib, har bir raqam ketma-ketligi uchun tepaga ega. Modulli panjaraning grafigi sifatida u modulli grafikdir .

Yosh-Fibonachchi grafigi va Yosh-Fibonachchi panjarasi dastlab Fomin (1988) va Stanley (1988) tomonidan ikkita maqolada chiqarilgan. Ular bir-biriga chambarchas bogʻliq boʻlgan Young panjarasi sharafiga va har qanday darajadagi elementlarning Fibonachchi sonidan keyin nomlanganidadir.

Berilgan darajali raqamlar ketma-ketligi

Raqamli r boʻlgan raqamlar ketma-ketligi r − 2 darajali ketma-ketlikka 2 raqamini qoʻshish yoki r − 1 darajali ketma-ketlikka 1 raqamini qoʻshish orqali tuzilishi mumkin boʻladi. Agar f funktsiya r ni shu darajadagi turli xil raqamlar ketma-ketligi soniga moslashtiruvchi funktsiya boʻlsa, f (r) = f (r − 2) + f (r − 1), f takrorlanish munosabatini qanoatlantiradi.f (r) = f (r − 2) + f (r − 1) Fibonachchi raqamlarini aniqlash, lekin bir oz boshqacha boshlangʻich shartlar bilan bweiladi: f (0) = f (1) = 1 (bitta 0-darajali qator, boʻsh qator va bitta raqamdan iborat 1-darajali qator mavjud). Ushbu boshlangʻich shartlar f qiymatlari ketma-ketligini Fibonachchi raqamlaridan bir pozitsiyaga siljishiga olib keladi: f (r) = F_r +1 .

Qadimgi hindlarning prosodiyani oʻrganishda Fibonachchi raqamlari maʼlum umumiy uzunlikdagi qisqa va uzun boʻgʻinlarning turli ketma-ketliklarini hisoblash uchun ishlatilgan; agar 1 raqami qisqa bo‘g‘inga, 2 raqami esa uzun bo‘g‘inga to‘g‘ri kelsa, raqamlar qatorining darajasi tegishli bo‘g‘inlar qatorining umumiy uzunligini o‘lchaydi. Tafsilotlar uchun Fibonachchi raqami maqolasiga oʻqib koʻring.

Raqamli ketma-ketliklarning grafiklari

Young-Fibonachchi grafigi cheksiz grafik boʻlib, „1“ va „2“ raqamlarning har bir satri uchun (shu jumladan boʻsh qator) tepaga simavjud. s satrning qoʻshnilari s dan quyidagi amallardan biri orqali hosil qilingan satrlardir:

1. s ga eng chapdagi „1“dan oldin „1“ qo‘yamiz (yoki „1“ mavjud bo‘lmasa, s ning istalgan joyiga).
2. s ning eng chapdagi „1“ ni „2“ ga oʻzgartiramiz.
3. s dan eng chapdagi „1“ ni olib tashlaymiz.
4. Chap tomonida „1“ boʻlmagan „2“ ni „1“ ga oʻzgartiramiz.

Har bir operatsiyani invertatsiya qilish mumkinligini tekshirish juda oddiy: 1 -va 3-operatsiyalar, 2-va 4-operatsiyalar kabi bir-biriga teskari. Shuning uchun hosil boʻlgan grafikni yoʻnaltirilmagan deb hisoblash mumkin. Biroq, odatda, har bir chekka pastki darajali choʻqqidan yuqori darajali choʻqqigacha bogʻlangan yoʻnaltirilgan asiklik grafik deb hisoblanadi.

Fomin (1988) va Stanley (1988) kuzatganidek, bu grafik quyidagi xususiyatlarga ega boʻladi:

• U bogʻlangan : har qanday boʻsh boʻlmagan satr oʻz darajasi qandaydir operatsiyalar bilan kamayishi mumkin, shuning uchun undan boʻsh satrga olib boradigan operatsiyalar ketma-ketligi mavjud boʻlib, teskari yoʻnalish grafikda boʻsh satrdan boshqa har bir tepaga yoʻnaltirilgan yoʻlni beradi.
• Bu daraja tuzilishiga mos keladi: har bir yoʻnaltirilgan yoʻl uning soʻnggi nuqtalari darajalari farqiga teng uzunlikka ega.
• Har ikki alohida u va v tugunlari uchun u va v ning umumiy bevosita salaflari soni u va v ning umumiy bevosita vorislari soniga teng; bu raqam nol yoki birga teng.
• Har bir choʻqqining tashqi darajasi bitta va uning ichki darajasiga teng.

Fomin (1988) ushbu xususiyatlarga ega grafani Y-grafik deb ataydi; Stanley (1988) ushbu xususiyatlarning zaif versiyasi boʻlgan grafikani chaqiradi (unda har qanday juft tugunning umumiy oʻtmishdoshlari va umumiy vorislari soni teng boʻlishi kerak, lekin birdan katta boʻlishi mumkin) differential poset

Qisman tartibi va panjara tuzilishi

Young-Fibonachchi grafigining tranzitiv yopilishi qisman tartiblidir . Stanley (1988) koʻrsatganidek, har qanday ikkita choʻqqi x va y bu tartibda yagona eng katta umumiy oʻtmishdoshga (ularning uchrashishi) va yagona eng kichik umumiy vorisga (ularning qoʻshilishi) ega; Shunday qilib, bu tartib yosh-Fibonachchi panjarasi deb ataladigan panjarad boʻladi .

X va y ning uchrashini topish uchun avval x va y dan biri boshqasining salafi ekanligini tekshirish mumkin.. x va y ning eng uzun umumiy qoʻshimchasini olib tashlagandan soʻng, y ichida qolgan „2“ raqamlar soni hech boʻlmaganda qolgan barcha raqamlar soniga teng boʻlsa, x qatori bu tartibda boshqa y qatorining oʻtmishdoshidir. Agar x ushbu testga koʻra y ning oldingisi boʻlsa, u holda ularning uchrashishi x ga teng va xuddi shunday, agar y x ning oldingisi boʻlsa, ularning uchrashishi y boʻladi. Ikkinchi holda, agar x ham, y ham boshqasining oldingisi boʻlmasa, lekin ulardan biri yoki ikkalasi „1“ raqami bilan boshlansa, bu dastlabki raqamlar olib tashlansa, uchrashuv oʻzgarmaydi. Va nihoyat, agar x va y ikkalasi ham „2“ raqami bilan boshlansa, x va y ning uchrashini ikkalasidan ham ushbu raqamni olib tashlash, natijada paydo boʻlgan qoʻshimchalarning uchrashishini topib, „2“ ni qoʻshish orqali topish mumkin.

x va y ning umumiy davomi (garchi eng kam umumiy voris boʻlmasa ham) uzunligi x va y ning uzunligiga teng boʻlgan „2“ raqamlar qatorini olish orqali topish mumkin. Eng kam umumiy vorisi x va y ning umumiy vorislari boʻlgan chekli koʻp satrlarning uchrashishi va bu „2“ qatorining oʻtmishdoshlai boladi.

Stanley (1988) yana kuzatganidek, Young-Fibonachchi panjarasi moduldir . Fomin (1988) notoʻgʻri taʼkidlaganidek, u distributivdir; biroq, satrlar tomonidan hosil qilingan pastki panjara {21,22, 121,211,221} taqsimlovchi panjaralarda taqiqlangan olmosli pastki panjara ham hosil qiladi.

Manbalar

• Fomin, S. V. (1988), „Generalized Robinson–Schensted–Knuth correspondence“, Journal of Mathematical Sciences, 41 (2): 979–991, doi:10.1007/BF01247093. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR 155: 156-175, 1986.
• Stanley, Richard P. (1988), „Differential posets“, Journal of the American Mathematical Society, 1 (4): 919–961, doi:10.2307/1990995, JSTOR 1990995.