Closed form for $\left(-1\right)^{n}\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}2^{\binom{k}{2}}$

Question

Given $n$ cities, we need to construct a path passing through all the cities, in how many ways it can be done?

---

Label the cities and define:

$$A_i:=\left\{\text{Paths passing through the $i$th city}\right\}$$

Between any two of the cities either there is a way or there is not, so we can choose $2$ of the $n$ places and then decide to construct a path between them or not, it can be done in $2^{\binom{n}{2}}$ ways.

The desired result is given by:

$$\left|\bigcap _{i=1}^nA_{i}\right|$$$$=2^{\binom{n}{2}}-\binom{n}{1}2^{\binom{n-1}{2}}+\binom{n}{2}2^{\binom{n-2}{2}}-...+(-1)^{n-1}\binom{n}{n-1}2^{\binom{n-(n-1)}{2}}+(-1)^{n}\binom{n}{n}2^{\binom{n-n}{2}}$$$$=2^{\binom{n}{2}}+\sum_{k=1}^{n}\left(-1\right)^{k}\binom{n}{k}2^{\binom{n-k}{2}}$$$$=\left(-1\right)^{n}\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}2^{\binom{k}{2}}$$$$=a(n)$$

I could not find any closed form for the summation, It would be highly appreciated if someone gives me a closed form (if it does exist) or help me to simplify it (if it can be simpler).

Answer 1

Inclusion-exclusion works for things like $\displaystyle \left | \bigcup _{i=1}^nA_i\right |$ but you are seemed to be interested in $\left |\displaystyle \bigcap _{i=1}^n A_i\right |.$ If you want to count the number of paths in which you pass just once in each city then you just want to put an order in the path, so a total ordering in $n$ vertices can be done in $n!$ as proposed by RobPratt in the comments.

What you are doing is to choose some set of edges and you take out the choices that exclude at least one vertex. This is exactly edge coverings of the complete graph. Notice that in your options, it might be the following choice: You fix a city and then construct n paths, one to go from the chosen city to each other city.

What you are actually computing is $$\left |\text{All edge choices}\setminus \bigcup _{i=1}^n A_i\right |,$$ where $A_i=\{\text{edge choices that do not touch $i-$th city }\}.$

Answer 2

There is no closed form for $a_n$.

However, it seems that $$\log(a_n) \sim C x^2 \qquad \text{with} \qquad C \sim 0.34614$$ This results from a quick and dirty regression for $3 \leq n \leq 1000$ $(a_{1000} \sim 3.04 \times 10^{150364})$.

The constant $C$ was not recognized by inverse symbolic calculators but it looks like $\frac 12 \log(2)$.

Notice that, in the $OEIS$ page, Vaclav Kotesovec proposed $$a_n \sim 2^{\frac{n(n-1)}{2} }$$ which is in a relative arror of $1$% if $n>11$, $0.1$% if $n>15$, $0.01$% if $n >18$