A192314 For n >= 3, draw a regular n-sided polygon and its n*(n-3)/2 diagonals, so there are n*(n-1)/2 lines; a(n) is the number of ways to choose a nonempty subset of these lines (subsets differing by a rotation are regarded as identical). a(1)=0, a(2)=1 by convention.

0, 1, 3, 21, 207, 5559, 299599, 33562695, 7635498335, 3518440564543, 3275345183542207, 6148914696963883711, 23248573454127484129023, 176848577040808821410837119, 2704321280486889389864215362559, 83076749736557243209409446411255935, 5124252113632955685095523500148980125695, 634332307869315502692705867068871886072665599, 157534492276509956656902449336997243381860518317055

Offset: 1

Author

David N Lumsden, Jun 27 2011

Keywords

• nonn

Comments

This is the number of ways to sew on a button having n holes arranged in a regular polygon. A button with no stitches would fall off, which is why we require that the subset be nonempty (cf. A192332).

A. Kolmogorov posed the problem for n=4 at the age of 6.

References

• A. N. Shiryaev 'Andrei Nikolaevich Kolmogorov: A Biographical Sketch of His Life and Creative Paths' in Harold H. McFaden (translator), Kolmogorov in Perspective, American Mathematical Society (2000), page 4.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..80

Crossrefs

Cf. A192332, A191563.

Programs

Maple

with(numtheory); f:=proc(n) local t0,t1,d; t0:=0; t1:=divisors(n);
for d in t1 do
if d mod 2 = 0 then t0:=t0+phi(d)*2^(n^2/(2*d))
else t0:=t0+phi(d)*2^(n*(n-1)/(2*d)); fi; od; t0/n; end;
[seq(f(n)-1, n=1..30)];
# N. J. A. Sloane, Jun 28 2011

Mathematica

Table[ -1 + 1/n * Plus @@ Map[Function[d, EulerPhi[d]*2^((n*(n - Mod[d, 2])/2)/d)], Divisors[n]], {n, 1, 20}] (* Olivier Gérard, Aug 27 2011 *)

Formula

a(p) = ((2^(p*(p-1)/2) - 2^((p-1)/2)) / p) + (2^((p-1)/2)) - 1 if p is prime.

Comment from N. J. A. Sloane, Jun 28 2011: More generally, a(n) = (1/n)*(Sum_{d|n, d odd} phi(d)*2^(n*(n-1)/(2*d)) + Sum_{d|n, d even} phi(d)*2^(n^2/(2*d))) - 1.

Extensions

Terms from a(8) onwards from N. J. A. Sloane, Jun 28 2011