Number of asymmetric partial functions over a finite non-empty set

Question

Let $S$ be a finite non-empty set.

I recently used the presumed fact that the number of asymmetric partial functions over $S$ is $3^{|S|-1}(|S|-1)!$, after I became quite convinced of it, since it worked for $|S|\in\{1,2,3,4\}$ and would be rather unusual not to continue like that. Unfortunately, I could not come up with a proof since.

I unsuccessfully tried it by induction, and to derive it from the number $3^{\frac{|S|^2-|S|}{2}}$ of asymmetric relations, and the number $(|S|+1)^{|S|}$ of partial functions, over $S$, which are both easy to show. Also, I failed to find an existing proof on the internet.

Does anyone know or see how this could be done, and might have some hint?

Answer 1

OEIS sequence A089466 seems to be what you're looking for. The first few values, starting with $n=0$, are $$1,1,3,18,163,1950,28821$$ It says here that

$a(n)$ is the number of functions $f:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$ such that the functional digraph contains no cycles of length $2$ — Geoffrey Critzer

which are the same as your "asymmetric partial functions" if you delete the cycles of length $1$.