Número de Schröder-Hipparchus - Schröder–Hipparchus number

Número de Schröder-Hipparchus
Nomeado após Ernst Schröder , Hipparchus , Eugène Charles Catalan
Ano de publicação 1870 (Schröder)
Nº de termos conhecidos infinidade
Fórmula
Primeiros termos 1 , 1 , 3 , 11 , 45 , 197 , 903
Índice OEIS
Onze subdivisões de um pentágono

Na combinatória , os números de Schröder-Hipparchus formam uma sequência inteira que pode ser usada para contar o número de árvores planas com um determinado conjunto de folhas, o número de maneiras de inserir parênteses em uma sequência e o número de maneiras de dissecar um convexo polígono em polígonos menores inserindo diagonais. Esses números começam

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... (sequência A001003 no OEIS ).

Eles também são chamados de números super-catalães , os pequenos números de Schröder ou os números de Hiparco , em homenagem a Eugène Charles Catalan e seus números catalães , Ernst Schröder e os números de Schröder intimamente relacionados e o antigo matemático grego Hiparco que aparece a partir de evidências em Plutarco ter conhecido esses números.

Aplicativos de enumeração combinatória

Equivalência combinatória entre subdivisões de um polígono, árvores planas e parênteses

Os números de Schröder-Hipparchus podem ser usados ​​para contar vários objetos combinatórios intimamente relacionados:

  • O n th número nas contagens de sequência o número de diferentes formas de subdivisão de um polígono com n  + 1 partes em polígonos mais pequenos, adicionando diagonais do polígono originais.
  • Os n th Número conta o número de diferentes árvores planas com n folhas e com todos os vértices interna de duas ou mais crianças.
  • Os n th número conta o número de diferentes formas de inserção parênteses para uma sequência de n  + 1 símbolos, com cada par de parênteses entre dois ou mais símbolos ou grupos parênteses, e sem quaisquer parênteses que rodeiam a sequência inteira.
  • Os n th Número contagem do número de faces de todas as dimensões de um associahedron K n  + 1 de dimensão n  - 1, incluindo o associahedron-se como uma face, mas não incluindo o conjunto vazio. Por exemplo, o associaedro bidimensional K 4 é um pentágono ; tem cinco vértices, cinco faces e um associaedro inteiro, para um total de 11 faces.

Como mostra a figura, existe uma equivalência combinatória simples entre esses objetos: uma subdivisão poligonal tem uma árvore plana como forma de seu gráfico dual , as folhas da árvore correspondem aos símbolos em uma sequência entre parênteses e os nós internos do árvore diferente da raiz corresponde a grupos entre parênteses. A própria sequência entre parênteses pode ser escrita em torno do perímetro do polígono com seus símbolos nas laterais do polígono e com parênteses nas extremidades das diagonais selecionadas. Essa equivalência fornece uma prova bijetiva de que todos esses tipos de objetos são contados por uma única sequência inteira.

Os mesmos números também contam o número de permutações duplas (sequências dos números de 1 a n , cada número aparecendo duas vezes, com as primeiras ocorrências de cada número em ordem classificada) que evitam os padrões de permutação 12312 e 121323.

Sequências relacionadas

Os grandes números de Schröder intimamente relacionados são iguais a duas vezes os números de Schröder-Hipparchus e também podem ser usados ​​para contar vários tipos de objetos combinatórios, incluindo certos tipos de caminhos de rede, partições de um retângulo em retângulos menores por corte recursivo e parênteses nos quais um par de parênteses envolvendo toda a sequência de elementos também é permitido. Os números catalães também contam conjuntos de objetos intimamente relacionados, incluindo subdivisões de um polígono em triângulos, árvores planas em que todos os nós internos têm exatamente dois filhos e parênteses em que cada par de parênteses envolve exatamente dois símbolos ou grupos entre parênteses.

A sequência de números catalães e a sequência de números de Schröder-Hipparchus, vistos como vetores de dimensão infinita , são os autovetores únicos para os dois primeiros em uma sequência de operadores lineares naturalmente definidos em sequências de números. Mais geralmente, a k- ésima sequência nesta sequência de sequências inteiras é ( x 1 , x 2 , x 3 , ...) onde os números x n são calculados como as somas dos números de Narayana multiplicados por potências de  k . Isso pode ser expresso como uma função hipergeométrica :

Substituindo k  = 1 nesta fórmula dá os números catalães e substituindo k  = 2 nesta fórmula dá os números de Schröder-Hipparchus.

Em conexão com a propriedade dos números de Schröder-Hipparchus das faces de contagem de um associaedro, o número de vértices do associaedro é dado pelos números catalães. Os números correspondentes para o permutoedro são, respectivamente, os números ordenados de Bell e os fatoriais .

Recorrência

Assim como a fórmula de soma acima, os números de Schröder-Hipparchus podem ser definidos por uma relação de recorrência :

Stanley prova esse fato usando funções geradoras, enquanto Foata e Zeilberger fornecem uma prova combinatória direta.

História

O diálogo de Plutarco Table Talk contém a linha:

Crisipo diz que o número de proposições compostas que podem ser feitas a partir de apenas dez proposições simples ultrapassa um milhão. (Hiparco, com certeza, refutou isso mostrando que do lado afirmativo há 103.049 afirmações compostas e do lado negativo 310.952.)

Essa afirmação ficou sem explicação até 1994, quando David Hough, um estudante de graduação na George Washington University , observou que existem 1.03049 maneiras de inserir parênteses em uma sequência de dez itens. O historiador da matemática Fabio Acerbi ( CNRS ) mostrou que uma explicação semelhante pode ser fornecida para o outro número: ele está muito próximo da média do décimo e décimo primeiro números de Schröder-Hipparchus, 310.954, e conta colchetes de dez termos junto com uma partícula negativa.

O problema de contar parênteses foi introduzido na matemática moderna por Schröder (1870) .

A recontagem de Plutarco dos dois números de Hiparco registra uma discordância entre Hiparco e o filósofo estóico anterior Crisipo , que havia afirmado que o número de proposições compostas que podem ser feitas a partir de dez proposições simples excede um milhão. A filósofa contemporânea Susanne Bobzien  ( 2011 ) argumentou que o cálculo de Crisipo era o correto, com base em sua análise da lógica estóica . Bobzien reconstrói os cálculos de Crisipo e Hiparco e diz que mostrar como Hiparco acertou sua matemática, mas sua lógica estóica errada pode lançar uma nova luz sobre as noções estóicas de conjunções e afirmações.

Referências

links externos