|
| |
|
|
A002619
|
|
Number of 2-colored patterns on an n X n board.
(Formerly M0887 N0336)
|
|
12
|
|
|
|
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_{d|n} 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), 56-61.
K. Yordzhev, On the cardinality of a factor set in the symmetric group. Asian-European Journal of Mathematics, Vol. 7, No. 2 (2014) 1450027, doi: 10.1142/S1793557114500272, ISSN:1793-5571, E-ISSN:1793-7183, 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. 253-256.
N. J. A. Sloane, Notes on A002618, A002619, etc.
András Szilárd, A combinatorial generalization of Wilson's theorem, Australasian Journal of Combinatorics, Volume 49 (2011), Pages 265-272. See Theorem 3.c p. 269.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [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.
Saeed Zakeri, Cyclic Permutations: Degrees and Combinatorial Types, arXiv:1909.03300 [math.DS], 2019. See Table 2 p. 10.
|
|
|
FORMULA
|
a(n) = Sum_{k|n} u(n, k)/(nk), where u(n, k) = A047918(n, k).
a(n) = (1/n^2)*Sum_{d|n} 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] (* Jean-Franç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
|
| |
|
|
