$n\times
n$ matrix. The permanent of empty matrix is set to be 1. Then $$\operatorname{per}(A)=\sum\limits_{i=1}^{n}A(i,1)\operatorname{per}(A_{i1}).$$*\
\
**Lemma 4.** *Let $A=(A(i,j))_{n\times n}$ be an $n\times
n$ matrix, $n\geq 2$. Then $$\operatorname{ham}(A)=\sum\limits_{i=2}^{n}A(i,1)\operatorname{ham}(A^{'}_{i1}).$$*

For the permanent, this expansion is well known. For the Hamilton, the formula is very similar and [@Ra94] proposes a combinatorial proof when each edge weight of the digraph is one. Regarding its importance in our algorithm, a proof in terms of matrix is presented below. We emphasize Lemma 4 is crucial in the sequential sampling procedure which is different from the one used in [@HL08], and ensures our algorithm to approximate the number of Hamiltonian cycles.\
\
**Proof of Lemma 4.** We proceed to prove the lemma by induction on $n$, the order of the matrix.\
The case $k=2$ is trivial.\
Suppose Lemma 4 holds for $k=n-1$.\
Consider $k=n$. Since $$\operatorname{ham}(A)=\sum\limits_{i=2}^{n}A(i,1)\sum\limits_{\{k_2
\cdots, k_{n-1}\}}A(k_2,i)A(k_3,k_2)\cdots
A(k_{n-1},k_{n-2})A(1,k_{n-1}),$$ it is sufficient to show that $$\operatorname{ham}(A^{'}_{i1})=\sum\limits_{\{k_2 \cdots,
k_{n-1}\}}A(k_2,i)\cdots A(k_{n-1},k_{n-2})A(1,k_{n-1}),$$ for $i=2,\cdots,n$, where $\{k_2 \cdots, k_{n-1}\}$ goes over all the permutations of $\{2 \cdots, n\}/i$. Considering the definition of $A^{'}_{i1}$, the row $i-1$ of $A^{'}_{i1}$ is the first row of $A$ except removing the first element, and

$A^{'}_{i1}(k_2-1,i-1)=A(k_2,i)$, $\cdots$ $\cdots$,

$A^{'}_{i1}(k_{n-1}-1,k_{n-2}-1)=A(k_{n-1},k_{n-2})$, and

$A^{'}_{i1}(i-1,k_{n-1}-1)=A(1,k_{n-1})$.

By the 