Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

Question

I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032

1) "A further problem that can be shown to be #P-hard is that of counting the number of Hamiltonian subgraphs of an arbitrary directed graph." (I think he means subgraphs as sets of edges, not induced by nodes.)

2) "Given a complete graph on n nodes and arbitrary probabilities assigned to each edge, the probability that the graph has a Hamiltonian circuit (or some other NP-complete substructure) is easily seen to be #P-complete."

Given 1ドル)$, it's easy to see that 2ドル)$ problem is $\sharp P$ hard$^*$, but it's unclear to me why this problem is in $\sharp P$. Valiant mentions that 1ドル)$ is likely not in $\sharp P$, so maybe this is a typo. 2ドル)$ appears to perhaps even strictly harder than 1ドル)$.

Can anyone give me a hint on how to think about 1ドル)$?

(*In the following way: For any given graph $G$, embed $G$ into a complete graph. On that complete graph, set the probabilities for edges not in the embedding to zero, and for edges in the embedding to 1ドル/2$. Then each subgraph of $G$ has probability $(1/2)^{E(G)}$ of appearing, so the probability that the random subgraph has a HC can be used to easily determine the number of subgraphs with Hamiltonian cycles. This shows that (given 1) ) it is $\sharp P$ hard to compute those probabilities.)

Answer 1

I think you could be interested by the counting class Span-P (which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time). It was introduced in this paper. Both 1) and 2) are in Span-P. For 1): guess a subgraph, then guess a Hamiltonian circuit, then output the graph (of course order the nodes beforehand so that you don't output the same graph twice). For 2) something similar should work.

In this paper they also show that a version of 1) is Span-P complete (page 375). The only difference is that a number $k$ is also part of the input and they want only the Hamiltonian subgraphs of size $k$ (I'm assuming the "positive integer $c$" was a typo). Also at the end of Section 6 ("A variation of the above...") they specifically mention your problem (so without the restriction of size $k$) and they that they do not know if it is Span-P hard.