Линдстрем-Гессель-Вено леммасы - Lindström–Gessel–Viennot lemma

Математикада Линдстрем-Гессель-Вено леммасы қиылыспайтын кортеждер санын санау тәсілін ұсынады торлы жолдар. Мұны Гинсель-Вена 1985 жылы, Линдстремнің 1973 жылы жарияланған алдыңғы шығармасы негізінде дәлелдеді.

Мәлімдеме

Келіңіздер G жергілікті шектеулі бағытталған ациклді болу график. Бұл әр шыңның ақырлы болатындығын білдіреді дәрежесі және сол G бағытталған циклдарды қамтымайды. Негізгі шыңдарды қарастырыңыз және тағайындалған шыңдар , сондай-ақ салмақ тағайындаңыз әр бағытталған жаққа e. Бұл шеттік салмақтар кейбіреулеріне тиесілі деп есептеледі ауыстырғыш сақина. Әр бағыт үшін P екі төбенің арасында, рұқсат етіңіз жол жиектерінің салмағының көбейтіндісі болу керек. Кез-келген екі шыңға арналған а және б, жаз e(а,б) сомаға барлық жолдар бойынша а дейін б. Егер кез-келген екі нүктенің арасында тек қана көптеген жолдар болса, бұл өте жақсы анықталған; бірақ тіпті жалпы жағдайда да мұны кейбір жағдайларда жақсы анықтауға болады (мысалы, барлық шекті салмақтар жұптық формальды анықталмаған болып табылады және формальды қуат қатарлары ретінде қарастырылған). Егер әр салмаққа әр салмақ 1 берілсе, онда e(а,б) бастап келген жолдардың санын есептейді а дейін б.

Осы қондырғы арқылы жазыңыз

.

Ан n-ден қиылыспайтын жолдардың трапы A дейін B мағынасын білдіреді n-тупле (P1, ..., Pn) жолдарының G келесі қасиеттері бар:

  • Ауыстыру бар туралы әрқайсысы үшін мен, жол Pмен деген жол дейін .
  • Қашан болса да , жолдар Pмен және Pj ортақ екі төбе жоқ (тіпті соңғы нүктелер де жоқ).

Берілген осындай n-тупле (P1, ..., Pn) деп белгілейміз ауыстыру бірінші шарттан.

The Линдстрем-Гессель-Вено леммасы онда анықтаушы М барлығына қол қойылған сома n- жұп P = (P1, ..., Pn) of қиылыспайтын жолдары A дейін B:

Яғни, детерминанты М барлығының салмағын есептейді n-басатын қиылыспайтын жолдардың қосындылары A және аяқталады B, әрқайсысы сәйкес ауыстырудың белгісімен әсер етеді , берілген қабылдау дейін .

Атап айтқанда, егер мүмкін болатын жалғыз мүмкіндік - бұл сәйкестілік болса (яғни, әрқайсысы) n-ден қиылыспайтын жолдардың трапы A дейін B алады амен дейін бмен әрқайсысы үшін мен) және біз салмақтарды 1 деп аламыз, содан кейін det (М) дәл қиылыспайтын саны n-басталатын жолдар A және аяқталады B.

Дәлел

Линдстрем-Гессель-Вено леммасын дәлелдеу үшін алдымен бірнеше белгілерді енгіземіз.

Ан n-жол ан n-тупле шыңдарының G дейін n-тупле шыңдарының G мағынасын білдіреді n-тупле ішіндегі жолдар G, әрқайсысымен бастап дейін . Бұл n-жол шақырылады қиылыспайтын жолдар болған жағдайда ғана Pмен және Pj әрқашан ортақ екі шыңның болмауы (соңғы нүктелерді қосқанда) . Әйтпесе, ол аталады шатастырылған.

Берілген n-жол , салмағы осы туралы n-жол өнім ретінде анықталады .

A бұралған n-жол ан n-тупле шыңдарының G дейін n-тупле шыңдарының G мағынасын білдіреді n-жол дейін ауыстыру үшін ішінде симметриялық топ . Бұл ауыстыру деп аталады бұралу бұл бұралған n-жол, және арқылы белгіленеді (қайда P болып табылады n-жол). Бұл, әрине, белгілерді жалпылайды бұрын енгізілген.

Анықтамасын еске түсіру М, біз кеңейте аламыз М ауыстырудың қол қойылған қосындысы ретінде; осылайша аламыз

Ол қалады көрсету қосындысы барлық шиеленіскен n-жолдар жоғалады. Келіңіздер шиыршықталған бұралған жиынтығын белгілеңіз n-жолдар. Мұны орнату үшін біз инволюция қасиеттерімен және барлығына . Осындай инволюцияны ескере отырып, жоғарыдағы қосындыдағы қалған мерзімге дейін азаяды

Инволюцияның құрылысы: эволюцияны анықтаудағы идея шатасқан жолдың бойында екі қиылысатын жолды таңдап, олардың қиылысу нүктесінен кейін құйрықтарын ауыстыру. Жалпы қиылысатын бірнеше жұп жолдар бар, олар бірнеше рет қиылысуы да мүмкін; сондықтан мұқият таңдау жасау керек. Келіңіздер кез келген бұралған болуы n-жол. Содан кейін келесідей анықталады. Бастап шатастырылған, минимум бар жылы осындай және ортақ шыңды бөлісу. Таңдау ең кіші индекстер болу. Жалпы шың міндетті түрде осы жолдардың соңғы нүктесі болып табылмайды. Бізде бар осы ақпаратты қорытындылай келе

қайда , , және -шы шыңы бойымен сәйкес келеді шыңы бойымен . Таңдау нақтылап айтсақ, ең кіші позициялар болуы керек және . Енді орнатылды сәйкес келу компоненттерден басқа және ауыстырылады

Бұл бірден түсінікті шиыршықталған бұралған n-жол. Құрылыс баспалдақтарынан өтіп бара жатып, мұны байқау қиын емес , және бұдан басқа және қолдану үшін қайтадан құйрықтарын ауыстыруды қамтиды және басқа компоненттерді өзгеріссіз қалдыру. Демек . Осылайша бұл инволюция. Қажетті антисимметрия қасиеттерін көрсету қалады:

Мұны құрылыстан байқауға болады сәйкес келеді айырбастауды қоспағанда және , осылайша түсімді . Мұны көрсету үшін біз алдымен есеп айырысуды сұрай отырып есептейміз

Демек .

Осылайша біз қажетті қасиеттерге ие инволюцияны таптық және Линдстрем-Гессель-Вено леммасының дәлелдеуін аяқтадық.

Ескерту. Жоғарыда келтірілгенге ұқсас аргументтер бірнеше дереккөздерде кездеседі, олардың қай құйрықты ауыстыруға болатындығына қатысты вариациялары бар. Нұсқасы j ең кіші (тең емес мен) үлкен емес, Гессель-Вено 1989 сілтемесінде кездеседі (1 теореманың дәлелі).

Қолданбалар

Шур көпмүшелері

Линдстрем-Гессель-Вено леммасын келесі екі түрлі анықтаманың баламалылығын дәлелдеу үшін пайдалануға болады. Шур көпмүшелері. Бөлім берілген туралы n, Шур көпмүшесі деп анықтауға болады:

мұндағы сома жас кестенің бәрінен асып түседі Т пішін λжәне кестенің салмағы Т көбейтіндісін алу арқылы алынған мономиялық ретінде анықталады хмен жазбалармен индекстелген мен туралы Т. Мысалы, кестенің салмағыRSK result.svg мысалыболып табылады .

қайда сағмен болып табылады толық біртекті симметриялық көпмүшелер (бірге сағмен 0-ге тең деп түсінді мен теріс) Мысалы, (3,2,2,1) бөлімі үшін сәйкес анықтаушы болып табылады

Кез келген бөлімді ескере отырып, эквиваленттілікті дәлелдеу үшін λ жоғарыда айтылғандай, біреуін қарастырады р бастапқы нүктелер және р соңғы нүктелер , тордағы нүктелер ретінде , ол бағытталған графиктің құрылымын тек оңға немесе жоғарыға бағытталатын рұқсат етілген бағыттар деп санайды; биіктікте кез-келген көлденең жиекпен байланысты салмақ мен болып табылады хмен, ал тік жиекпен байланысты салмақ 1-ге тең. р-ден бастап жолдар A дейін B бұл пішіннің жас кестесі λ, және мұндай салмағы р-tuple - Шур полиномдарының бірінші анықтамасындағы сәйкес жиын. Мысалы, кестеменRSK result.svg мысалы, біреу сәйкес келеді 4-тупле

Schur торлы жолдары

Екінші жағынан, матрица М дәл осы үшін жоғарыда жазылған матрица Д.. Бұл қажетті эквиваленттілікті көрсетеді. (Сондай-ақ, Саганның кітабындағы §4.5 немесе Стэнлидің EC2-дегі Теореманың 7.16.1-нің бірінші дәлелі немесе Фулмектің arXiv баспасындағы §3.3 немесе Мартиннің дәрістеріндегі §9.13 қараңыз).

Коши-Бине формуласы

Мұны дәлелдеу үшін Линдстрем-Гессель-Венот леммасын қолдануға болады Коши-Бинет формуласы, және, атап айтқанда, детерминанттың мультипликативтілігі.

Жалпылау

Таласканың формуласы

Акциклділігі G Линдстрем-Гессель-Вено леммасында маңызды болжам; бұл сомаға кепілдік береді (ақылға қонымды жағдайларда) жақсы анықталған және бұл дәлелдемеге сәйкес келеді (егер G ациклдік емес f жолдың өзіндік қиылысын екі нақты жолдың қиылысына айналдыруы мүмкін, бұл аргументті бұзады f болып табылады). Осыған қарамастан, Келли Таласканың 2012 жылғы мақаласында лемманы ерікті диграфтарға жалпылайтын формула келтірілген. Қосындылар формальды қуат қатарларымен ауыстырылады, ал анықталмайтын циклдар кортеждерінің үстіндегі қосылыс енді анықталмайтын және өздігінен қиылыспайтын жолдар мен циклдар жиынтығының қосындысына айналады. Толығырақ білу үшін оқырман Таласканың қағазына жүгінеді.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  • Гессель, Ира М.; Венот, Ксавье Г. (1989), Детерминанттар, жолдар және жазықтық бөлімдері (PDF)
  • Саган, Брюс Е. (2001), Симметриялық топ, Springer
  • Стэнли, Ричард П. (1999), Санақ комбинаторикасы, 2 том, Кубок
  • Таласка, Келли (2012), Салмақталған матрицалардың детерминанттары, arXiv:1202.3128v1
  • Мартин, Джереми (2012), Алгебралық комбинаторика туралы дәрістер (PDF)
  • Фулмек, Маркус (2010), Анықтаушы емес торлы жолдар ретінде детерминанттарды қарастыру классикалық детерминанттық сәйкестікті биективті түрде береді, arXiv:1010.3860v1