Lindström-Gessel-Viennot lemmasi - Lindström–Gessel–Viennot lemma

Matematikada Lindström-Gessel-Viennot lemmasi kesishmaydigan to'siqlar sonini hisoblash usulini beradi panjara yo'llari. Buni Gessel-Viennot 1985 yilda, Lindströmning 1973 yilda nashr etilgan avvalgi asari asosida isbotlagan.

Bayonot

Ruxsat bering G mahalliy cheklangan yo'naltirilgan asiklik bo'lishi grafik. Bu shuni anglatadiki, har bir tepalik cheklangan daraja va bu G yo'naltirilgan tsikllarni o'z ichiga olmaydi. Asosiy tepaliklarni ko'rib chiqing ${ displaystyle A = {a_ {1}, ldots, a_ {n} }}$ va borar joylari ${ displaystyle B = {b_ {1}, ldots, b_ {n} }}$ va shuningdek, vaznni tayinlang ${ displaystyle omega _ {e}}$ har bir yo'naltirilgan chetga e. Ushbu chekka og'irliklar ba'zilariga tegishli deb taxmin qilinadi komutativ uzuk. Har bir yo'naltirilgan yo'l uchun P ikkita tepalik o'rtasida, ruxsat bering ${ displaystyle omega (P)}$ yo'lning chekkalari og'irliklari mahsuloti bo'ling. Har qanday ikkita tepalik uchun a va b, yozing e(a,b) summa uchun ${ displaystyle e (a, b) = sum _ {P: a to b} omega (P)}$ dan barcha yo'llar bo'ylab a ga b. Agar har qanday ikkita nuqta o'rtasida faqat juda ko'p yo'llar mavjud bo'lsa, bu yaxshi aniqlangan; ammo umumiy holatda ham, buni ba'zi holatlarda yaxshi aniqlash mumkin (masalan, barcha chekka og'irliklar juft rasmiy ravishda aniqlanmagan va ${ displaystyle e (a, b)}$ rasmiy kuch seriyasi sifatida qaraladi). Agar har bir kishi har bir chekkaga 1 vaznini tayinlasa, unda e(a,b) dan yo'llar sonini hisoblaydi a ga b.

Ushbu sozlash bilan yozing

{ displaystyle M = { begin {pmatrix} e (a_ {1}, b_ {1}) & e (a_ {1}, b_ {2}) & cdots & e (a_ {1}, b_ {n}) e (a_ {2}, b_ {1}) & e (a_ {2}, b_ {2}) & cdots & e (a_ {2}, b_ {n}) vdots & vdots & ddots & vdots e (a_ {n}, b_ {1}) & e (a_ {n}, b_ {2}) & cdots & e (a_ {n}, b_ {n}) end {pmatrix} }}

.

An n-dan kesishmaydigan yo'llarning tutashuvi A ga B degan ma'noni anglatadi n-tuple (P₁, ..., P_n) yo'llarning G quyidagi xususiyatlarga ega:

Bu erda almashtirish mavjud ${ displaystyle sigma}$ ning ${ displaystyle left {1,2, ..., n right }}$ shunday qilib, har bir kishi uchun men, yo'l P_men dan yo'l ${ displaystyle a_ {i}}$ ga ${ displaystyle b _ { sigma (i)}}$ .
Har doim ${ displaystyle i neq j}$ , yo'llar P_men va P_j umumiy ikkita tepalikka ega bo'lmang (hatto so'nggi nuqta ham emas).

Bunday berilgan n-tuple (P₁, ..., P_n) bilan belgilaymiz ${ displaystyle sigma (P)}$ almashtirish ${ displaystyle sigma}$ birinchi shartdan.

The Lindström-Gessel-Viennot lemmasi keyin ning aniqlovchisi ekanligini aytadi M bu hamma uchun imzolangan summa n- juftliklar P = (P₁, ..., P_n) ning kesishmaydigan dan yo'llar A ga B:

{ displaystyle det (M) = sum _ {(P_ {1}, ldots, P_ {n}) nuqta A dan B} mathrm {ishora} ( sigma (P)) prod _ { i = 1} ^ {n} omega (P_ {i}).}

Ya'ni, ning determinanti M barchaning og'irligini hisoblaydi n- boshlanadigan kesishmaydigan yo'llarning juftliklari A va tugaydi B, har biriga mos keladigan almashtirish belgisi ta'sir qiladi ${ displaystyle (1,2, ldots, n)}$ , tomonidan berilgan ${ displaystyle P_ {i}}$ olish ${ displaystyle a_ {i}}$ ga ${ displaystyle b _ { sigma (i)}}$ .

Xususan, agar faqatgina bitta imkoniyat bo'lsa, bu identifikatsiya (ya'ni, har bir kishi) n-dan kesishmaydigan yo'llarning tutashuvi A ga B oladi a_men ga b_men har biriga men) va biz og'irliklarni 1 ga, keyin det (M) kesishning aniq soni n- boshlanadigan yo'llarning juftliklari A va tugaydi B.

Isbot

Lindstrem-Gessel-Viennot lemmasini isbotlash uchun avval bir nechta yozuvlarni kiritamiz.

An n- yo'l dan n- juftlik ${ displaystyle (a_ {1}, a_ {2}, ldots, a_ {n})}$ tepaliklari G ga n- juftlik ${ displaystyle (b_ {1}, b_ {2}, ldots, b_ {n})}$ tepaliklari G degan ma'noni anglatadi n- juftlik ${ displaystyle (P_ {1}, P_ {2}, ldots, P_ {n})}$ yo'llarning G, har biri bilan ${ displaystyle P_ {i}}$ dan boshlab ${ displaystyle a_ {i}}$ ga ${ displaystyle b_ {i}}$ . Bu n-path chaqiriladi kesishmaydigan faqat yo'llar uchun P_men va P_j har doim ham umumiy ikkita tepalikka ega bo'lmang (oxirgi nuqtalarni ham qo'shganda) ${ displaystyle i neq j}$ . Aks holda, u chaqiriladi chigallashgan.

Berilgan n- yo'l ${ displaystyle P = (P_ {1}, P_ {2}, ldots, P_ {n})}$ , vazn ${ displaystyle omega (P)}$ bu n-path mahsulot sifatida aniqlanadi ${ displaystyle omega (P_ {1}) omega (P_ {2}) cdots omega (P_ {n})}$ .

A o'ralgan n- yo'l dan n- juftlik ${ displaystyle (a_ {1}, a_ {2}, ldots, a_ {n})}$ tepaliklari G ga n- juftlik ${ displaystyle (b_ {1}, b_ {2}, ldots, b_ {n})}$ tepaliklari G degan ma'noni anglatadi n- yo'l ${ displaystyle (a_ {1}, a_ {2}, ldots, a_ {n})}$ ga ${ displaystyle chap (b _ { sigma (1)}, b _ { sigma (2)}, ldots, b _ { sigma (n)} o'ng)}$ ba'zi bir almashtirish uchun ${ displaystyle sigma}$ ichida nosimmetrik guruh ${ displaystyle S_ {n}}$ . Ushbu almashtirish ${ displaystyle sigma}$ deb nomlanadi burama bu o'ralgan n-path va tomonidan belgilanadi ${ displaystyle sigma (P)}$ (qayerda P bo'ladi n-path). Bu, albatta, yozuvlarni umumlashtiradi ${ displaystyle sigma (P)}$ oldin kiritilgan.

Ning ta'rifini eslab M, biz detni kengaytirishimiz mumkin M almashtirishlarning imzolangan yig'indisi sifatida; shunday qilib olamiz

{ displaystyle { begin {array} {rcl} det M & = & sum _ { sigma in S_ {n}} mathrm {sign} ( sigma) prod _ {i = 1} ^ {n } e (a_ {i}, b _ { sigma (i)}) & = & sum _ { sigma in S_ {n}} mathrm {sign} ( sigma) prod _ {i = 1} ^ {n} sum _ {P_ {i}: a_ {i} to b _ { sigma (i)}} omega (P_ {i}) & = & sum _ { sigma S_ {n}} mathrm {sign} ( sigma) sum { omega (P) da: P ~ { text {an}} ~ n { text {-path from}} ~ left (a_ {1}, a_ {2}, ldots, a_ {n} o'ng) ~ { text {to}} ~ chap (b _ { sigma (1)}, b _ { sigma (2)}, ldots, b _ { sigma (n)} right) } & = & sum { mathrm {sign} ( sigma (P)) omega (P): P ~ { text {a twisted }} ~ n { text {-yol}} ~ chap (a_ {1}, a_ {2}, ldots, a_ {n} o'ng) ~ { text {to}} ~ chap (b_ {1}, b_ {2}, ..., b_ {n} o'ng) } & = & sum { mathrm {ishora} ( sigma (P)) omega (P): P ~ { text {kesilmaydigan burmalangan}} ~ n { text {-profil}} ~ ~ chap (a_ {1}, a_ {2}, ldots, a_ {n} o'ng) ~ { matn {to}} ~ chap (b_ {1}, b_ {2}, ..., b_ {n} o'ng) } && + sum { mathrm {ishora} ( sigma (P )) omega (P): P ~ { text {a chalkash twisted}} ~ n { text {-path from from}} ~ left (a_ {1}, a_ {2}, ldots, a_ {n } o'ng) ~ { matn {ga }} ~ chap (b_ {1}, b_ {2}, ..., b_ {n} o'ng) } & = & sum _ {(P_ {1}, ldots, P_ {n }) nuqta A dan B} mathrm {belgisi} ( sigma (P)) omega (P) && + underbrace { sum { mathrm {sign} ( sigma (P))) omega (P): P ~ { text {chigal burmalangan}} ~ n { text {-path from}} ~ chap (a_ {1}, a_ {2}, ldots, a_ {n} o'ng ) ~ { text {to}} ~ left (b_ {1}, b_ {2}, ..., b_ {n} right) }} _ {= 0?} end {array} }}

Bu qoladi ko'rsatmoq ning yig'indisi ${ displaystyle mathrm {sign} ( sigma (P)) omega (P)}$ barcha chigallarga o'ralgan n- yo'llar yo'qoladi. Ruxsat bering ${ displaystyle { mathcal {E}}}$ o'ralgan o'ralgan to'plamni belgilang n- yo'llar. Buni o'rnatish uchun biz involyutsiya ${ displaystyle f: { mathcal {E}} longrightarrow { mathcal {E}}}$ xususiyatlari bilan ${ displaystyle omega (f (P)) = omega (P)}$ va ${ displaystyle mathrm {ishora} ( sigma (f (P))) = - mathrm {ishora} ( sigma (P))}$ Barcha uchun ${ displaystyle P in { mathcal {E}}}$ . Bunday evolyutsiyani hisobga olgan holda yuqoridagi summadagi qolgan muddat ga kamayadi

{ displaystyle { begin {array} {rcl} sum _ {P in { mathcal {E}}} mathrm {sign} ( sigma (P)) omega (P) & = & { frac {1} {2}} chap ( sum _ {P in { mathcal {E}}} mathrm {sign} ( sigma (P)) omega (P) + sum _ {P in { mathcal {E}}} mathrm {sign} ( sigma (f (P))) omega (f (P)) right) & = & { frac {1} {2}} chap ( sum _ {P in { mathcal {E}}} mathrm {sign} ( sigma (P)) omega (P) + sum _ {P in { mathcal {E}}} - mathrm {sign} ( sigma (P)) omega (P) right) & = & 0 end {array}}}

Evolyutsiya qurilishi: evolyutsiya ta'rifi g'oyasi ${ displaystyle f}$ chalkashib ketgan yo'l ichida ikkita kesishgan yo'lni tanlash va ularning kesishgan joyidan keyin dumlarini almashtirishdir. Umuman olganda bir necha juft kesishgan yo'llar mavjud, ular ham bir necha marta kesishishi mumkin; shuning uchun ehtiyotkorlik bilan tanlov qilish kerak. Ruxsat bering ${ displaystyle P = chap (P_ {1}, P_ {2}, ..., P_ {n} o'ng)}$ har qanday chigalga o'ralgan bo'ling n- yo'l. Keyin ${ displaystyle f (P)}$ quyidagicha ta'riflanadi. Beri ${ displaystyle P}$ chalkashib ketgan, minimal mavjud ${ displaystyle i$ yilda ${ displaystyle {1,2, ldots, n }}$ shu kabi ${ displaystyle P_ {i}}$ va ${ displaystyle P_ {j}}$ umumiy tepalikni baham ko'ring. Tanlang ${ displaystyle i_ {P}$ eng kichik ko'rsatkichlar bo'lish. Umumiy tepalik bu yo'llarning so'nggi nuqtasi bo'lishi shart emas. Ushbu ma'lumotni umumlashtirsak

{ displaystyle { begin {array} {rcl} P_ {i} & equiv & a_ {i} = u_ {0} to u_ {1} to u_ {2} ldots u _ { alpha -1} to overbrace { mathbf {u} _ { alpha} to u _ { alpha +1} ldots to u_ {r} = b _ { sigma (i)}} ^ { mathrm {tail} ~ i } P_ {j} & equiv & a_ {j} = v_ {0} to v_ {1} to v_ {2} ldots v _ { beta -1} to underbrace { mathbf {v} _ { beta} to v _ { beta +1} ldots to v_ {s} = b _ { sigma (j)}} _ { mathrm {tail} ~ j} end {array}} }

qayerda ${ displaystyle i = i_ {P}}$ , ${ displaystyle j = j_ {P}}$ , ${ displaystyle sigma = sigma (P)}$ va ${ displaystyle alpha}$ -tepa bilan birga ${ displaystyle P_ {i}}$ ga to'g'ri keladi ${ displaystyle beta}$ tepada birga ${ displaystyle P_ {i}}$ . Tanlang ${ displaystyle alpha _ {P}, beta _ {P}}$ mumkin bo'lgan eng kichik pozitsiyalar bo'lish ${ displaystyle alpha _ {P}: = min { alpha mid mavjud { beta: ~} u _ { alpha} = v _ { beta} }}$ va ${ displaystyle beta _ {P}: = min { beta mid u _ { alpha _ {P}} = v _ { beta} }}$ . Endi o'rnatildi ${ displaystyle f (P)}$ bilan mos tushish ${ displaystyle P}$ komponentlardan tashqari ${ displaystyle i}$ va ${ displaystyle j}$ bilan almashtiriladi

{ displaystyle { begin {array} {rcl} P '_ {i} & equiv & a_ {i} = u_ {0} to u_ {1} to u_ {2} ldots u _ { alpha -1 } to overbrace {v _ { beta _ {P}} to v _ { beta _ {P} +1} ldots to v_ {s} = b _ { sigma (j)}} ^ { mathrm {tail} ~ j} P '_ {j} & equiv & a_ {j} = v_ {0} to v_ {1} to v_ {2} ldots v _ { beta -1} to {u _ { alfa _ {P}} to u _ { alfa _ {P} +1} ldots to u_ {r} = b _ { sigma (i)}} _ { mathrm {tail} ~ i} end {array}}}

Darhol aniq ${ displaystyle f (P)}$ chigal burama n- yo'l. Qurilish bosqichlaridan o'tib, buni ko'rish oson ${ displaystyle i_ {f (P)} = i_ {P}}$ , ${ displaystyle j_ {f (P)} = j_ {P}}$ va bundan tashqari ${ displaystyle alfa _ {f (P)} = alfa _ {P}}$ va ${ displaystyle beta _ {f (P)} = beta _ {P}}$ , shuning uchun murojaat qilish ${ displaystyle f}$ yana uchun ${ displaystyle f (P)}$ quyruqlarini almashtirishni o'z ichiga oladi ${ displaystyle f (P) _ {i}, f (P) _ {j}}$ va boshqa tarkibiy qismlarni buzilmasdan qoldirish. Shuning uchun ${ displaystyle f (f (P)) = P}$ . Shunday qilib ${ displaystyle f}$ bu involution. Kerakli antisimmetriya xususiyatlarini namoyish qilish qoladi:

Qurilishdan buni ko'rish mumkin ${ displaystyle sigma (f (P))}$ bilan mos keladi ${ displaystyle sigma = sigma (P)}$ faqat bu almashtiriladi ${ displaystyle sigma (i)}$ va ${ displaystyle sigma (j)}$ , shunday qilib hosil beradi ${ displaystyle sigma (f (P)) = - sigma (P)}$ . Buni ko'rsatish uchun ${ displaystyle omega (f (P)) = omega (P)}$ biz avval hisob-kitob qilamiz, quyruq almashtirishga murojaat qilamiz

{ displaystyle { begin {array} {rcl} omega (P '_ {i}) omega (P' _ {j}) & = & left ( prod _ {t = 0} ^ { alpha -1} omega (u_ {t}, u_ {t + 1}) cdot prod _ {t = beta} ^ {s-1} omega (v_ {t}, v_ {t + 1}) o'ng) cdot chap ( prod _ {t = 0} ^ { beta -1} omega (v_ {t}, v_ {t + 1}) cdot prod _ {t = alfa} ^ {r-1} omega (u_ {t}, u_ {t + 1}) o'ng) & = & prod _ {t = 0} ^ {r-1} omega (u_ {t}, u_ {t + 1}) cdot prod _ {t = 0} ^ {s-1} omega (v_ {t}, v_ {t + 1}) & = & omega (P_ {i} ) omega (P_ {j}). end {array}}}

Shuning uchun ${ displaystyle omega (f (P)) = prod _ {k = 1} ^ {n} omega (f (P) _ {k}) = prod _ {k = 1, ~ k neq i , j} ^ {n} omega (P_ {k}) cdot omega (P '_ {i}) omega (P' _ {j}) = prod _ {k = 1, ~ k neq i, j} ^ {n} omega (P_ {k}) cdot omega (P_ {i}) omega (P_ {j}) = prod _ {k = 1} ^ {n} omega ( P_ {k}) = omega (P)}$ .

Shunday qilib biz kerakli xususiyatlarga ega bo'lgan involyutsiyani topdik va Lindstrem-Gessel-Viennot lemmasining isbotini yakunladik.

Izoh. Yuqorida keltirilgan argumentlarga o'xshash dalillar bir nechta manbalarda uchraydi, qaysi dumlarni almashtirishni tanlash borasida farqlar mavjud. Bilan versiyasi j eng kichik (tengsiz men) o'rniga Gessel-Viennot 1989 ma'lumotnomasida (Teorema 1 isboti) katta.

Ilovalar

Schur polinomlari

Lindstrom-Gessel-Viennot lemmasidan quyidagi ikki xil ta'riflarning ekvivalentligini isbotlash uchun foydalanish mumkin. Schur polinomlari. Bo'lim berilgan ${ displaystyle lambda = lambda _ {1} + cdots + lambda _ {r}}$ ning n, Schur polinomi ${ displaystyle s _ { lambda} (x_ {1}, ldots, x_ {n})}$ quyidagicha ta'riflanishi mumkin:

${ displaystyle s _ { lambda} (x_ {1}, ldots, x_ {n}) = sum _ {T} w (T),}$

bu erda hamma semistandard Young tableaux ustidan yig'indisi T shakl λva jadvalning vazni T ning hosilasini olish natijasida olingan monomial sifatida aniqlanadi x_men yozuvlar bilan indekslangan men ning T. Masalan, jadvalning og'irligibu ${ displaystyle x_ {1} x_ {3} x_ {4} ^ {3} x_ {5} x_ {6} x_ {7}}$ .

${ displaystyle s _ { lambda} (x_ {1}, ldots, x_ {n}) = det left ((h _ { lambda _ {i} + ji}) _ {i, j} ^ {r times r} right),}$

qayerda h_men ular to'liq bir hil nosimmetrik polinomlar (bilan h_men 0 bo'lsa tushuniladi men salbiy). Masalan, (3,2,2,1) bo'lim uchun mos keladigan determinant

{ displaystyle s _ {(3,2,2,1)} = { begin {vmatrix} h_ {3} & h_ {4} & h_ {5} & h_ {5} & h_ {6} h_ {1} & h_ {2} & h_ { 3} & h_ {4} 1 & h_ {1} & h_ {2} & h_ {3} 0 & 0 & 1 & h_ {1} end {vmatrix}}.}

Ekvivalentlikni isbotlash uchun har qanday bo'lim berilgan λ yuqoridagi kabi, biri ko'rib chiqadi r boshlang'ich nuqtalari ${ displaystyle a_ {i} = (r + 1-i, 1)}$ va r yakuniy fikrlar ${ displaystyle b_ {i} = ( lambda _ {i} + r + 1-i, n)}$ , panjaradagi nuqta sifatida ${ displaystyle mathbb {Z} ^ {2}}$ , bu faqat bitta yo'nalish o'ngga yoki yuqoriga qarab borishni tasdiqlash orqali yo'naltirilgan grafika tuzilishini oladi; balandlikdagi har qanday gorizontal chekka bilan bog'liq bo'lgan vazn men bu x_men, va vertikal chekka bilan bog'liq bo'lgan og'irlik 1 ga teng. r-dan yo'llar A ga B Ular shakldagi yosh jadvallardir λva bunday vaznning vazni r-tuple - Shur polinomlarining birinchi ta'rifidagi tegishli summand. Masalan, jadval bilan, bittasi mos keladi 4- juftlik

Boshqa tomondan, matritsa M aynan yuqorida uchun yozilgan matritsa D.. Bu kerakli ekvivalentlikni ko'rsatadi. (Shuningdek, Sagan kitobidagi §4.5-ga yoki Stenlining EC2-dagi 7.16.1-sonli teoremaning isboti yoki Fulmekning arXiv preprint-dagi §3.3-ga yoki Martinning ma'ruza yozuvlaridagi §9.13-ga qarang, bu argument bo'yicha ozgina farqlar uchun.)

Koshi-Binet formulasi

Buni isbotlash uchun Lindstrem-Gessel-Viennot lemmasidan foydalanish mumkin Koshi-Binet formulasi va xususan, determinantning multiplikativligi.

Umumlashtirish

Talaska formulasi

Achchiqligi G Lindstrem-Gessel-Viennot lemmasida muhim taxmindir; u (o'rtacha vaziyatlarda) summani kafolatlaydi ${ displaystyle e (a, b)}$ yaxshi aniqlangan va u dalillarga mos keladi (agar G asiklik emas, demak f yo'lning o'z-o'zidan kesishishini ikkita aniq yo'lning kesishmasiga aylantirishi mumkin, bu esa argumentni buzadi f (involution)). Shunga qaramay, Kelli Talaska 2012 yilgi maqolasida lemmani o'zboshimchalik bilan digraflarga umumlashtiruvchi formulalar o'rnatilgan. Jami ${ displaystyle e (a, b)}$ ularning o'rnini rasmiy kuchlar qatori egallaydi va o'zaro bog'liq bo'lmagan yo'l katakchalari ustidagi yig'indilar endi o'zaro bog'liq bo'lmagan va o'zaro kesishmaydigan yo'llar va tsikllar yig'indisining yig'indisiga aylanadi va o'zaro ta'sir qilmaydigan tsikllar yig'indisi yig'indisiga bo'linadi. Tafsilotlar uchun o'quvchi Talaska qog'oziga murojaat qiladi.

Shuningdek qarang

Matritsa daraxti teoremasi

Adabiyotlar

Gessel, Ira M.; Vena, Xaver G. (1989), Determinantlar, yo'llar va samolyot bo'laklari (PDF)
Sagan, Bryus E. (2001), Nosimmetrik guruh, Springer
Stenli, Richard P. (1999), Sanab chiquvchi kombinatorika, 2-jild, Kubok
Talaska, Kelli (2012), O'lchangan yo'l matritsalarining determinantlari, arXiv:1202.3128v1
Martin, Jeremi (2012), Algebraik kombinatorika bo'yicha ma'ruza matnlari (PDF)
Fulmek, Markus (2010), Determinantlarni notekislashtiruvchi panjara yo'llari sifatida ko'rish mumtoz determinantal identifikatorlarni biektiv ravishda beradi, arXiv:1010.3860v1