login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054946 Number of strongly connected labeled tournaments on n nodes. 3
1, 0, 2, 24, 544, 22320, 1677488, 236522496, 64026088576, 33832910196480, 35262092417856512, 72926863133112198144, 300318571786159783496704, 2467430973323656141183549440, 40490606137578335674252914280448 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..80 [Shortened file because terms grow rapidly: see Sloane link below for additional terms]

J. East, R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014

J. M. Howie, Idempotent generators in finite full transformation semigroups, Proc. Roy. Soc. Edinburgh Sect. A, 81 (1978), no. 3-4, 317-323.

V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

N. J. A. Sloane, Table of n, a(n) for n = 1..100

E. M. Wright, The number of irreducible tournaments, Glasgow Math. J., 11 (1970), 97-101.

FORMULA

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]

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

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

EXAMPLE

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)}.

MAPLE

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:

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:

MATHEMATICA

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

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

Array[a, 15] (* Jean-Fran├žois Alcover, Nov 13 2017, from first formula *)

CROSSREFS

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

Sequence in context: A187658 A138450 A262009 * A046744 A000186 A210905

Adjacent sequences:  A054943 A054944 A054945 * A054947 A054948 A054949

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, May 24 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 06:52 EST 2018. Contains 318049 sequences. (Running on oeis4.)