A054946 - OEIS

%I #47 Jul 25 2024 10:47:37

%S 1,0,2,24,544,22320,1677488,236522496,64026088576,33832910196480,

%T 35262092417856512,72926863133112198144,300318571786159783496704,

%U 2467430973323656141183549440,40490606137578335674252914280448

%N Number of strongly connected labeled tournaments on n nodes.

%C For n>=3, a(n) is equal to the number of minimal idempotent generating sets of the semigroup of all singular mappings on {1,2,...,n}.  (In the reference below, Howie gave a correspondence between such generating sets and strongly connected labeled tournaments, but stated an incorrect  formula for a(n).) - _James East_, Jan 08 2013

%D Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.

%H N. J. A. Sloane, <a href="/A054946/b054946.txt">Table of n, a(n) for n = 1..80</a> [Shortened file because terms grow rapidly: see Sloane link below for additional terms]

%H James East and Robert D. Gray, <a href="http://arxiv.org/abs/1404.2359">Idempotent generators in finite partition monoids and related semigroups</a>, arXiv preprint arXiv:1404.2359, 2014

%H J. M. Howie, <a href="http://dx.doi.org/10.1017/S0308210500010647">Idempotent generators in finite full transformation semigroups</a>, Proc. Roy. Soc. Edinburgh Sect. A, 81 (1978), no. 3-4, 317-323.

%H Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, <a href="https://arxiv.org/abs/2407.11877">Bridging Weighted First Order Model Counting and Graph Polynomials</a>, arXiv:2407.11877 [cs.LO], 2024. See p. 33.

%H Valery A. Liskovets, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LISK/Derseq.html">Some easily derivable sequences</a>, J. Integer Sequences, 3 (2000), #00.2.2.

%H Thierry Monteil and Khaydar Nurligareev, <a href="https://arxiv.org/abs/2401.00818">Asymptotic probability for connectedness</a>, arXiv:2401.00818 [math.CO], 2024. See p. 12.

%H N. J. A. Sloane, <a href="/A054946/a054946.txt">Table of n, a(n) for n = 1..100</a>

%H E. M. Wright, <a href="http://dx.doi.org/10.1017/S0017089500000914">The number of irreducible tournaments</a>, Glasgow Math. J., 11 (1970), 97-101.

%F Let F(n) = 2^(n*(n-1)/2). Then a(n) is defined by the recurrence a(1)=1, F(n) = a(n) + Sum_{s=1..n-1} binomial(n,s)*a(s)*F(n-s). [Wright]

%F E.g.f.: 1-1/(1+f(x)) where f(x) = Sum_{m>=1} 2^(m(m-1)/2) x^m / m!.

%F Wright also gives an asymptotic expansion for a(n).

%e For n=3, there are two minimal idempotent generating sets for the semigroup of singular mappings on {1,2,3}.  Writing (a,b,c) to indicate the map for which 1->a, etc, the relevant generating sets are: {(1,1,3),(1,2,2),(3,2,3)} and {(2,2,3),(1,3,3),(1,2,1)}.

%p with(powseries): powcreate(t(n)=2^(n*(n-1)/2)/n!): s := evalpow(1-1/t): a := tpsform(s, x, 21): for n from 0 to 20 do printf(`%d,`,n!*coeff(a,x,n)) od:

%p f:=array(0..500); F:=array(0..500); M:=100; f[1]:=1; F[1]:=1; lprint(1,f[1]); for n from 2 to M do F[n]:=2^(n*(n-1)/2); f[n]:=F[n]-add( binomial(n,s)*f[s]*F[n-s], s=1..n-1); lprint(n,f[n]); od:

%t F[n_] := 2^(n*(n - 1)/2);

%t a[1] = 1; a[n_] := a[n] = F[n] - Sum[Binomial[n, s]*a[s]*F[n-s], {s, 1, n-1 }];

%t Array[a, 15] (* _Jean-François Alcover_, Nov 13 2017, from first formula *)

%o (PARI) seq(n)={my(a=vector(n)); for(n=1, n, a[n] = 2^(n*(n-1)/2) - sum(k=1, n-1, binomial(n,k)*2^((n-k)*(n-k-1)/2)*a[k])); a} \\ _Andrew Howroyd_, Jan 10 2022

%Y Cf. A000568 (unlabeled tournaments), A051337 (strongly connected unlabeled tournaments).

%K nonn,easy

%O 1,3

%A _N. J. A. Sloane_, May 24 2000