Aula combinatória - Combinatorial class
Em matemática , uma classe combinatória é um conjunto contável de objetos matemáticos, junto com uma função de tamanho que mapeia cada objeto para um número inteiro não negativo, de modo que haja um número finito de objetos de cada tamanho.
Contando sequências e isomorfismo
A sequência de contagem de uma classe combinatória é a sequência dos números de elementos de tamanho i para i = 0, 1, 2, ...; também pode ser descrito como uma função geradora que tem esses números como seus coeficientes. As sequências de contagem de classes combinatórias são o principal objeto de estudo da combinatória enumerativa . Duas classes combinatórias são consideradas isomórficas se tiverem o mesmo número de objetos de cada tamanho ou, de maneira equivalente, se suas sequências de contagem forem iguais. Freqüentemente, uma vez que duas classes combinatórias são conhecidas como isomórficas, uma prova bijetiva dessa equivalência é buscada; tal prova pode ser interpretada como mostrando que os objetos nas duas classes isomórficas são criptomórficos entre si.
Por exemplo, as triangulações de polígonos regulares (com tamanho dado pelo número de lados do polígono, e uma escolha fixa de polígono para triangular para cada tamanho) e o conjunto de árvores planas binárias não enraizadas (até isomorfismo gráfico , com uma ordenação das folhas, e com tamanho dado pelo número de folhas) são ambos contados pelos números catalães , portanto, eles formam classes combinatórias isomórficas. Um isomorfismo bijetivo, neste caso, é dado pela dualidade do grafo planar : uma triangulação pode ser transformada bijetivamente em uma árvore com uma folha para cada aresta do polígono, um nó interno para cada triângulo e uma aresta para cada duas arestas do polígono ou triângulos adjacentes um para o outro.
Combinatória analítica
A teoria das espécies combinatórias e sua extensão à combinatória analítica fornecem uma linguagem para descrever muitas classes combinatórias importantes, construindo novas classes a partir de combinações de outras previamente definidas e derivando automaticamente suas sequências de contagem. Por exemplo, duas classes combinatórias podem ser combinadas por união disjunta ou por uma construção de produto cartesiano em que os objetos são pares ordenados de um objeto de cada uma das duas classes, e a função de tamanho é a soma dos tamanhos de cada objeto no par. Essas operações formam respectivamente as operações de adição e multiplicação de um semiramento na família de (classes de equivalência de isomorfismo de) classes combinatórias, nas quais o objeto zero é a classe combinatória vazia e a unidade é a classe cujo único objeto é o conjunto vazio .
Padrões de permutação
No estudo de padrões de permutação , uma classe combinatória de classes de permutação , enumerada pelo comprimento da permutação, é chamada de classe Wilf . O estudo de enumerações de classes de permutação específicas revelou equivalências inesperadas na contagem de sequências de classes de permutação aparentemente não relacionadas.