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)$ $A$ $D$ $\Delta = D - A$ $\lambda$

k (G) = \frac{1 1}{n} \prod_{k = 1 1}^{n - 1 1} λ_{k}

$k(G) = \frac{1}{n} \prod_{k=1}^{n-1} \lambda_k$

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

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

insira a descrição da imagem aqui

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

graph-theory randomized-algorithms matrices tree 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 \times n

$m \times n$

315 Peter Peter Shor

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. $n$ $m$

\exp (z_{s q} m n)

$\exp (z_{\mathrm{sq}}mn)$

z_{s q} = \frac{4}{π} \sum_{Eu = 0 0}^{\infty} \frac{(- 1 1)^{Eu}}{(2 Eu + 1 1)^{2}} \approx 1.16624

$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$

m

$m$

n

$n$

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

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

Respostas: