The number of Hamiltonian paths in a rectangular grid (Q1357721): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:04, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of Hamiltonian paths in a rectangular grid |
scientific article |
Statements
The number of Hamiltonian paths in a rectangular grid (English)
0 references
12 January 1998
0 references
Given a rectangular \(m\) vertex by \(n\) vertex grid, let \(f(m,n)\) be the number of Hamiltonian paths from the lower left corner (LL) to the upper right corner (UR). The paper gives a generating function which is the quotient of two polynomials, and contains the sequence \(f(m,1)\), \(f(m,2)\), \(f(m,3)\), \(f(m,4),\dots\) as the coefficients in its Taylor series expansion about 0. It is shown that for \(m=3\) the grid has \(2^{n-2}\) Hamiltonian paths from its LL corner to its UR corner and from its LL corner to its LR corner.
0 references
grid
0 references
Hamiltonian paths
0 references
generating function
0 references