Classe combinatòria

En matemàtiques, una classe combinatòria és un conjunt contable d'objectes matemàtics, junt en una funció de tamany que assigna cada objecte a un número entero no negatiu, de modo que hi ha una cantitat finita d'objectes de cada tamany.

Conteo de seqüències i isomorfisme

La seqüència de conteo d'una classe combinatòria és la seqüència del número d'elements de tamany i per a i = 0, 1, 2, ...; també pot descriure's com una funció generadora que té estos números com a coeficients. Les seqüències de conteo de classes combinatòries són el principal tema d'estudi de la combinatòria enumerativa. Es diu que dos classes combinatòries són isomòrfiques si tenen el mateix número d'objectes de cada tamany, o de manera equivalent, si les seues seqüències de conteo són les mateixes. En freqüència, una volta que se sap que dos classes combinatòries són isomòrfiques, es busca una prova biyectiva d'esta equivalència; una prova d'este tipo pot interpretar-se en el sentit de que els objectes de les dos classes isomorfas són criptomórficos entre sí.

Per eixemple, les triangulacions de polígons regulars (en un tamany donat pel número de costats del polígon i una elecció fixa de polígon a triangular per a cada tamany) i el conjunt d'arbres plans binarios sense raïl (fins al isomorfisme del gràfic, en un l'orde dels fulls, i en el tamany donat pel número de fulls) es conten abdós pels números de Catalan, per lo que formen classes combinatòries isomorfas. Un isomorfisme biyectivo en este cas ve dau per la dualitat gràfica plana: una triangulació es pot transformar biyectivamente en un arbre en un full per a cada vora de polígon, un nodo intern per a cada triàngul i una vora per a cada dos vores de polígon o triànguls adjacents. l'u a l'atre.

Combinatoria analítica

La teoria de les espècies combinatòries i la seua extensió a la combinatoria analítica proporcionen un llenguage per a descriure moltes classes combinatòries importants, construir noves classes a partir de combinacions de les prèviament definides i derivar automàticament les seues seqüències de conteo. Per eixemple, dos classes combinatòries poden combinar-se per unió disjunta, o per una construcció de producte cartesiano en la que els objectes són parells ordenats d'un objecte de cada una de dos classes, i la funció de tamany és la suma dels tamanys de cada objecte en el parell. Estes operacions formen, respectivament, les operacions de suma i multiplicació d'un semianillo en la família de (classes d'equivalència d'isomorfisme de) classes combinatòries, en la que l'objecte zero és la classe combinatòria buida, i l'unitat és la classe l'únic objecte de la qual és el conjunt buit.