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

1, 1, 2, 3, 8, 24, 108, 640, 4492, 36336, 329900, 3326788, 36846288, 444790512, 5811886656, 81729688428, 1230752346368, 19760413251956, 336967037143596, 6082255029733168, 115852476579940152, 2322315553428424200, 48869596859895986108

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

From Richard L. Ollerton, May 09 2021: (Start)

Let A(n,k) = (1/n^2)*Sum_{d|n} k^d*phi(n/d)^2*(n/d)^d*d!, then:

A(n,k) = (1/n^2)*Sum_{i=1..n} k^gcd(n,i)*phi(n/gcd(n,i))*(n/gcd(n,i))^gcd(n,i)*gcd(n,i)!.

A(n,k) = (1/n^2)*Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))^2*(gcd(n,i))^(n/gcd(n,i))*(n/gcd(n,i))!.

a(n) = A(n,1). (End)

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
(Python)
from sympy import totient, factorial, divisors
def A002619(n): return sum(totient(m:=n//d)**2*factorial(d)*m**d for d in divisors(n, generator=True))//n**2 # Chai Wah Wu, Nov 07 2022

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