

A002619


Number of 2colored patterns on an n X n board.
(Formerly M0887 N0336)


11



1, 1, 2, 3, 8, 24, 108, 640, 4492, 36336, 329900, 3326788, 36846288, 444790512, 5811886656, 81729688428, 1230752346368, 19760413251956, 336967037143596, 6082255029733168, 115852476579940152, 2322315553428424200, 48869596859895986108
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Also number of orbits in the set of circular permutations (up to rotation) under cyclic permutation of the elements.  Michael Steyer, Oct 06 2001
Moser shows that (1/n^2)*Sum_{dn} k^d*phi(n/d)^2*(n/d)^d*d! is an integer. Here we have k=1.  Michel Marcus, Nov 02 2012


REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 5661.
K. Yordzhev, On the cardinality of a factor set in the symmetric group. AsianEuropean Journal of Mathematics, Vol. 7, No. 2 (2014) 1450027, doi: 10.1142/S1793557114500272, ISSN:17935571, EISSN:17937183, Zbl 1298.05035.


LINKS

T. D. Noe, Table of n, a(n) for n = 1..100
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
W. O. J. Moser, A (modest) generalization of the theorems of Wilson and Fermat, Canad. Math. Bull. 33(1990), pp. 253256.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 5661.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 5661. [Annotated scanned copy. Note that the scanned pages are out of order]
A. Vella, Pattern avoidance in permutations: linear and cyclic orders, Electron. J. Combin. 9 (2002/03), no. 2, #R18, 43 pp.
K. Yordzhev, On the cardinality of a factor set in the symmetric group, arXiv:1410.8408 [math.CO], 2014.


FORMULA

a(n) = Sum_{kn} u(n, k)/(nk), where u(n, k) = A047918(n, k).
a(n) = (1/n^2)*Sum_{dn} phi(d)^2*(n/d)!*d^(n/d), where phi is Euler's totient function (A000010).  Emeric Deutsch, Aug 23 2005


EXAMPLE

n=6: {(123456)}, {(135462), (246513), (351624)} and {(124635), (235146), (346251), (451362), (562413), (613524)} are 3 of the 24 orbits, consisting of 1, 3 and 6 permutations, respectively.


MAPLE

with(numtheory): a:=proc(n) local div: div:=divisors(n): sum(phi(div[j])^2*(n/div[j])!*div[j]^(n/div[j]), j=1..tau(n))/n^2 end: seq(a(n), n=1..23); # Emeric Deutsch, Aug 23 2005


MATHEMATICA

a[n_] := EulerPhi[#]^2*(n/#)!*#^(n/#)/n^2 & /@ Divisors[n] // Total; a /@ Range[23] (* JeanFrançois Alcover, Jul 11 2011, after Emeric Deutsch *)


PROG

(PARI) a(n)={sumdiv(n, d, eulerphi(n/d)^2*d!*(n/d)^d)/n^2} \\ Andrew Howroyd, Sep 09 2018


CROSSREFS

Cf. A002618, A047916, A064852, A064649.
Cf. A000010.
Cf. A000939, A000940, A089066, A262480, A275527 (other classes of permutations under various symmetries).
Sequence in context: A182212 A120260 A202592 * A286820 A129202 A127905
Adjacent sequences: A002616 A002617 A002618 * A002620 A002621 A002622


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane, Colin Mallows


STATUS

approved



