Робинзон-Шенстед-Кнут хат-хабарлары - Robinson–Schensted–Knuth correspondence - Wikipedia

Жылы математика, Робинзон-Шенстед-Кнут хат-хабарлары, деп те аталады РСК хат-хабарлары немесе RSK алгоритмі, комбинаторлық болып табылады биекция матрицалар арасында A бірге теріс емес бүтін сан жазбалар мен жұптар (P,Q) туралы semistandard Жас кесте тең формадағы, оның мөлшері жазбалардың қосындысына тең A. Дәлірек айтқанда салмағы P қосындысының бағанымен беріледі A, және салмағы Q оның қосындылары бойынша. Бұл жалпылау Робинзон - Шенст корреспонденциясы, қабылдау мағынасында A болу ауыстыру матрицасы, жұп (P,Q) Робинзон-Шенстед корреспонденциясы бойынша ауыстыруға байланысты стандартты кестелер жұбы болады.

Робинзон-Шенстед-Кнут сәйкестігі-нің көптеген керемет қасиеттерін кеңейтеді Робинзон - Шенст корреспонденциясы, атап айтқанда оның симметриясы: матрицаның транспозициясы A нәтижесінде кесте алмасады P,Q.

Робинзон - Шенстед - Кнут сәйкестігі

Кіріспе

The Робинзон - Шенст корреспонденциясы Бұл биективті арасындағы картаға түсіру ауыстыру және стандартты жұптар Жас үстелдер, екеуінің пішіні бірдей. Бұл биекцияны деп аталатын алгоритмнің көмегімен жасауға болады Шенсттік кірістіру, бос кестеден бастап және мәндерді дәйекті түрде енгізу σ1,…,σn ауыстыру туралы σ 1,2,… сандарында…n; олар екінші жолды құрайды σ екі жолды нотада келтірілген:

.

Бірінші стандартты кесте P дәйекті енгізулердің нәтижесі болып табылады; басқа стандартты кесте Q салу кезінде аралық кестелердің дәйекті формаларын жазады P.

Шенстедтік кірістіру σ бірнеше рет енгізілген жағдайды оңай қорытады; бұл жағдайда корреспонденциялар кестенің кестесін береді P стандартты кестеден гөрі, бірақ Q бәрібір стандартты кесте болады. РСК сәйкестігінің анықтамасы арасындағы симметрияны қалпына келтіреді P және Q үшін жартылай стандартты кесте жасау арқылы tableaux Q сонымен қатар.

Екі жолды массивтер

The екі жолды массив (немесе жалпыланған ауыстыру) wA матрицаға сәйкес келеді A анықталды[1] сияқты

онда кез-келген жұп үшін (мен,j) жазбаны индекстейтін Aмен,j туралы A, Сонда бар Aмен,j тең бағандар , және барлық бағандар лексикографиялық тәртіпте орналасқан, демек

  1. , және
  2. егер және содан кейін .

Мысал

Сәйкес келетін екі жолды жиым

болып табылады

Хат-хабардың анықтамасы

Осы екі жолдық массивтің төменгі жолына Шенстті кірістіру алгоритмін қолдану арқылы жартылай стандартты кестеден тұратын жұп алынады P және стандартты кесте Q0, мұнда соңғысын жартылай стандартты кестеге айналдыруға болады Q әр жазбаны ауыстыру арқылы б туралы Q0 бойынша б-жоғары жолдың үшінші жазбасы wA. Біреуі а биекция матрицалардан A тапсырыс берілген жұптарға,[2] (P,Q) Жазбалардың жиынтығы салынған бірдей пішінді жас кестелер P екінші жолына жатады wA, және жазбалар жиынтығы Q бұл бірінші жолдың wA. Жазбалар саны j жылы P сондықтан бағандағы жазбалардың қосындысына тең j туралы Aжәне жазбалар саны мен жылы Q қатардағы жазбалардың қосындысына тең мен туралы A.

Мысал

Жоғарыда келтірілген мысалда, бастапқыда бос кестеге 1,3,3,2,2,1,2-ді дәйекті кірістіру үшін Шенстедті кірістіруді қолдану нәтижесі кестеге әкеледі P, және қосымша стандартты кесте Q0 берілген дәйекті фигураларды қайта санау

және 1,2,3,4,5,6,7 жазбаларын ауыстырғаннан кейін Q0 бірінен соң бірі 1,1,1,2,2,3,3 жартылай стандартты кестені алады

РСК корреспонденциясының тікелей анықтамасы

Жоғарыда келтірілген анықтамада стандартты жазу кестесін құратын Шенстед алгоритмі қолданылады Q0, және оны екі жолды массивтің бірінші жолын ескеру үшін өзгертеді және жартылай стандартты жазу кестесін жасайды; бұл қатынасты жасайды Робинзон - Шенст корреспонденциясы айқын. Алгоритмнің пішінді жазба бөлігін екі сызықты массивтің бірінші жолын тікелей ескеретін етіп өзгерту арқылы құрылысты жеңілдету табиғи нәрсе; дәл осы формада РСК хат алмасу алгоритмі сипатталады. Бұл жай Шенст енгізілген әр қадамнан кейін кесте дегенді білдіреді Q кеңейтіліп, жаңа квадратқа кіру ретінде б- кіру менб бірінші жолының wA, қайда б - кестенің ағымдағы өлшемі. Бұл әрқашан жартылай стандартты кесте тудырады, бұл қасиеттен шығады (алдымен Кнут байқады)[2]) бірінші жолдағы бірдей мәні бар кезек-кезек енгізулер үшін wA, пішінге қосылған әрбір дәйекті квадрат алдыңғысының оң жағындағы бағанда орналасқан.

Міне, осы екі жартылай стандартты кестенің құрылысының егжей-тегжейлі мысалы. Матрицаға сәйкес келеді

біреуінде екі жолды массив бар

Келесі кестеде осы мысал үшін екі кестенің де құрылысы көрсетілген

Жұп енгізілді
P
Q

РСК хат-хабарларының комбинаторлық қасиеттері

Орын ауыстыру матрицаларының жағдайы

Егер Бұл ауыстыру матрицасы содан кейін RSK стандартты Young Tableaux (SYT) шығарады, бірдей пішінді . Керісінше, егер бірдей пішінді SYT болып табылады , содан кейін сәйкес матрица бұл ауыстыру матрицасы. Осы қасиеттің нәтижесінде биективті картаға түсірудің екі жағындағы екі жиынтықтың негізгі мәндерін салыстыру арқылы біз келесі нәтижеге қол жеткіздік:

Қорытынды 1: Әрқайсысы үшін Бізде бар қайда білдіреді барлығында өзгереді бөлімдер туралы және бұл форманың стандартты жас кестесінің саны .

Симметрия

Келіңіздер теріс емес жазбалары бар матрица болыңыз. RSK алгоритм карталары делік дейін содан кейін RSK алгоритмінің карталары дейін , қайда транспозасы болып табылады .[1]

Атап айтқанда, ауыстыру матрицалары үшін Робинсон-Шенстед сәйкестігінің симметриясы қалпына келеді:[3]

Теорема 2: Егер ауыстыру үштікке сәйкес келеді , содан кейін кері ауыстыру, , сәйкес келеді .

Бұл қосылулар саны арасындағы келесі қатынасқа әкеледі жасалуы мүмкін кестелер санымен (Ан инволюция бұл өзіне тән ауыстыру кері ):[3]

Қорытынды 2: Жасалуы мүмкін кестелер саны қосылу санына тең .

Дәлел: Егер сәйкес келетін инволюция болып табылады , содан кейін сәйкес келеді ; демек . Керісінше, егер сәйкес келетін кез келген ауыстыру болып табылады , содан кейін сәйкес келеді ; демек . Сонымен, қосылулар арасында бір-бір сәйкестік бар және үстелдер

Қосылу саны қайталануымен беріледі:

Қайда . Осы қайталануды шеше отырып, біз байланысты санды ала аламыз ,

Симметриялық матрицалар

Келіңіздер және RSK алгоритмі матрицаны бейнелесін жұпқа , қайда форманың SSYT болып табылады .[1] Келіңіздер қайда және . Содан кейін карта симметриялы матрицалар арасында биекция орнатады () және SSYT типтері .

РСК хат-хабар қосымшалары

Кошидің жеке басы

Робинзон-Шенстед-Кнут сәйкестігі симметриялы функциялар үшін келесі танымал сәйкестіктің тікелей биективті дәлелі болып табылады:

қайда болып табылады Schur функциялары.

Костка сандары

Бөлімдерді түзету , содан кейін

қайда және белгілеу Костка сандары және матрицалар саны , теріс емес элементтермен, қатармен () және баған () .

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

  1. ^ а б c Стэнли, Ричард П. (1999). Санақ комбинаторикасы. 2. Нью-Йорк: Кембридж университетінің баспасы. 316–380 бб. ISBN  0-521-55309-1.
  2. ^ а б Кнут, Дональд Э. (1970). «Пермутаттар, матрицалар және жалпыланған жас кестелер». Тынық мұхит журналы. 34 (3): 709–727. дои:10.2140 / pjm.1970.34.709. МЫРЗА  0272654.
  3. ^ а б Кнут, Дональд Э. (1973). Компьютерлік бағдарламалау өнері, т. 3: сұрыптау және іздеу. Лондон: Аддисон-Уэсли. 54-58 бет. ISBN  0-201-03803-X.