cp's OEIS Frontend

A054946 Number of strongly connected labeled tournaments on n nodes.

%I A054946 #47 Jul 25 2024 10:47:37
%S A054946 1,0,2,24,544,22320,1677488,236522496,64026088576,33832910196480,
%T A054946 35262092417856512,72926863133112198144,300318571786159783496704,
%U A054946 2467430973323656141183549440,40490606137578335674252914280448
%N A054946 Number of strongly connected labeled tournaments on n nodes.
%C A054946 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 A054946 Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
%H A054946 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 A054946 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 A054946 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 A054946 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 A054946 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 A054946 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 A054946 N. J. A. Sloane, <a href="/A054946/a054946.txt">Table of n, a(n) for n = 1..100</a>
%H A054946 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 A054946 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 A054946 E.g.f.: 1-1/(1+f(x)) where f(x) = Sum_{m>=1} 2^(m(m-1)/2) x^m / m!.
%F A054946 Wright also gives an asymptotic expansion for a(n).
%e A054946 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 A054946 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 A054946 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 A054946 F[n_] := 2^(n*(n - 1)/2);
%t A054946 a[1] = 1; a[n_] := a[n] = F[n] - Sum[Binomial[n, s]*a[s]*F[n-s], {s, 1, n-1 }];
%t A054946 Array[a, 15] (* _Jean-François Alcover_, Nov 13 2017, from first formula *)
%o A054946 (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 A054946 Cf. A000568 (unlabeled tournaments), A051337 (strongly connected unlabeled tournaments).
%K A054946 nonn,easy
%O A054946 1,3
%A A054946 _N. J. A. Sloane_, May 24 2000