A002619 Number of 2-colored patterns on an n X n board.

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

Author

N. J. A. Sloane, Colin Mallows

Keywords

• nonn
• nice
• easy

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

Examples

			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.
		

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
• M. Kazarian, E. Krasilnikov, S. Lando, and M. Shapiro, Generalized chord diagrams and weight systems, arXiv:2505.24491 [math.CO], 2025. See Theorem 5.3 p. 24.
• 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.
• Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See p. 9.
• 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. See Table 2 p. 14.
• Saeed Zakeri, Cyclic Permutations: Degrees and Combinatorial Types, arXiv:1909.03300 [math.DS], 2019. See Table 2 p. 10.

Crossrefs

Cf. A002618, A047916, A064852, A064649.

Cf. A000010.

Cf. A000939, A000940, A089066, A262480, A275527 (other classes of permutations under various symmetries).

Programs

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 *)

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

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)