Fórmula exata para o número de árvores abrangidas de um retângulo

10

Este blog fala sobre a geração de "labirintos tortuosos" usando um computador e enumerando-os. A enumeração pode ser feita usando o algoritmo de Wilson para obter o UST , mas não me lembro da fórmula de quantos existem.

http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike

Em princípio, o Teorema da Árvore Matricial indica que o número de árvores abrangidas de um gráfico é igual ao determinante da matriz laplaciana do gráfico. Seja o gráfico e seja a matriz de adjacência, seja a matriz de graus, então com autovalores , então:G=(E,V)UMADΔ=D-UMAλ

k(G)=1 1nk=1 1n-1 1λk

No caso de um retângulo tanto quanto os autovalores devem assumir uma forma particularmente simples, que não consigo encontrar. m×nUMA

Qual é a fórmula exata (e assintótica) para o número de árvores de abrangência de um retângulo ?m×n

insira a descrição da imagem aqui

Aqui está um exemplo bonito do algoritmo de Wilson em ação.

john mangual
fonte
2
Enciclopédia on-line de seqüências inteiras As fórmulas exatas não parecem fáceis de derivar.
22878 Peter Shor
@PeterShor OEIS cita: Germain Kreweras, Complexite and circuits Euleriens in the sommes tensorielles of graphes , J. Combin. Theory, B 24 (1978), 202-212. Ele é o mesmo objeto que nós, certo?
31815 john mangual
Eles cobrem muitos objetos diferentes, incluindo a quadrilagem planaire , que é a grade . m×n
315 Peter Peter Shor

Respostas:

9

De acordo com https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf, não existe uma fórmula de forma fechada conhecida.

De acordo com http://arxiv.org/pdf/cond-mat/0004341v1.pdf, o número é assintótico (para e grandes) para que mas estou não tenho certeza se esse é um limite rigoroso ou o resultado de um raciocínio baseado na física heurística. O mesmo artigo também fornece fórmulas assintóticas de tipo semelhante quando é fixado em uma pequena constante é grande.m exp ( z s q m n ) z s q = 4nm

exp(zsqmn)
mn
zsq=4πEu=0 0(-1 1)Eu(2Eu+1 1)21.16624
mn
David Eppstein
fonte
Existem fórmulas assintóticas precisas para o número de árvores de abrangência em um retângulo (e seqüências mais gerais de subgráficos descritos por polígonos retilíneos) aqui: arxiv.org/pdf/math-ph/0011042.pdf (especificamente, corolário 2 e proposição 13 )
Lorenzo Najt 29/07
Novamente, isso está em um repositório de matemática matemática. Eles provam as fórmulas assintóticas rigorosamente ou apenas usam raciocínio ansatz semelhante à física?
David Eppstein
Foi publicado na Acta Math 185 (2000) no. 2, 239-286.
Lorenzo Najt 31/07/19
0

Os valores próprios do gráfico do retângulo m-por-n podem ser usados ​​para obter uma expressão para o número de combinações perfeitas nesses gráficos. Veja o artigo da Wikipedia sobre inclinação de dominó .

Tyson Williams
fonte
Isso é interessante, mas você pode explicar como isso resolve a questão? Existe algum tipo de mapeamento entre combinações perfeitas e árvores abrangidas nesse caso específico?
Saeed