Matjaž Konvalinka: Determinante v kombinatoriki

"Sveti gral" v preštevalni kombinatoriki so produktne formule, ki pa seveda ne obstajajo vedno. Po lepoti in uporabnosti jim pridejo blizu determinantne formule, torej izrazi za moč množice (ali enumerator), ki vsebujejo determinanto neke matrike.

V tem preglednem predavanju si bomo ogledali primere tega, npr. izrek o številu vpetih dreves, formulo za število permutacij z dano množico padcev in Jacobi-Trudijevo identiteto za Schurove funkcije, pa tudi primere tega, ko se da produktna formula dokazati preko determinantne, npr. formulo o kljukah in formulo za število matrik z alternirajočim predznakom. Videli bomo, da je v ozadju mnogih identitet eleganten rezultat, znan kot Lindström-Gessel-Viennotova lema. Zaključili bomo z dvema nedavnima domnevama.

 

Vljudno vabljeni!

Roman Drnovšek in Primož Moravec