|
|
A054946
|
|
Number of strongly connected labeled tournaments on n nodes.
|
|
6
|
|
|
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
|
|
REFERENCES
|
Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
|
|
LINKS
|
|
|
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]
E.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 }];
|
|
PROG
|
(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
|
|
CROSSREFS
|
Cf. A000568 (unlabeled tournaments), A051337 (strongly connected unlabeled tournaments).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|