cp's OEIS Frontend

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

%I A002619 M0887 N0336 #98 Jun 12 2025 10:13:07
%S A002619 1,1,2,3,8,24,108,640,4492,36336,329900,3326788,36846288,444790512,
%T A002619 5811886656,81729688428,1230752346368,19760413251956,336967037143596,
%U A002619 6082255029733168,115852476579940152,2322315553428424200,48869596859895986108
%N A002619 Number of 2-colored patterns on an n X n board.
%C A002619 Also number of orbits in the set of circular permutations (up to rotation) under cyclic permutation of the elements. - _Michael Steyer_, Oct 06 2001
%C A002619 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
%D A002619 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002619 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A002619 J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
%D A002619 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.
%H A002619 T. D. Noe, <a href="/A002619/b002619.txt">Table of n, a(n) for n = 1..100</a>
%H A002619 M. Kazarian, E. Krasilnikov, S. Lando, and M. Shapiro, <a href="https://arxiv.org/abs/2505.24491">Generalized chord diagrams and weight systems</a>, arXiv:2505.24491 [math.CO], 2025. See Theorem 5.3 p. 24.
%H A002619 C. L. Mallows and N. J. A. Sloane, <a href="/A002618/a002618_1.pdf">Notes on A002618, A002619, etc.</a>
%H A002619 W. O. J. Moser, <a href="http://dx.doi.org/10.4153/CMB-1990-040-6">A (modest) generalization of the theorems of Wilson and Fermat</a>, Canad. Math. Bull. 33(1990), pp. 253-256.
%H A002619 Ludovic Schwob, <a href="https://arxiv.org/abs/2506.04007">On the enumeration of double cosets and self-inverse double cosets</a>, arXiv:2506.04007 [math.CO], 2025. See p. 9.
%H A002619 N. J. A. Sloane, <a href="/A002618/a002618_2.pdf">Notes on A002618, A002619, etc.</a>
%H A002619 András Szilárd, <a href="https://ajc.maths.uq.edu.au/pdf/49/ajc_v49_p265.pdf">A combinatorial generalization of Wilson's theorem</a>, Australasian Journal of Combinatorics, Volume 49 (2011), Pages 265-272. See Theorem 3.c p. 269.
%H A002619 J. E. A. Steggall, <a href="https://www2.cs.arizona.edu/patterns/weaving/articles596.html">On the numbers of patterns which can be derived from certain elements</a>, Mess. Math., 37 (1907), 56-61.
%H A002619 J. E. A. Steggall, <a href="/A002618/a002618.pdf">On the numbers of patterns which can be derived from certain elements</a>, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]
%H A002619 A. Vella, <a href="https://doi.org/10.37236/1690">Pattern avoidance in permutations: linear and cyclic orders</a>, Electron. J. Combin. 9 (2002/03), no. 2, #R18, 43 pp.
%H A002619 K. Yordzhev, <a href="https://arxiv.org/abs/1410.8408">On the cardinality of a factor set in the symmetric group</a>, arXiv:1410.8408 [math.CO], 2014. See Table 2 p. 14.
%H A002619 Saeed Zakeri, <a href="https://arxiv.org/abs/1909.03300">Cyclic Permutations: Degrees and Combinatorial Types</a>, arXiv:1909.03300 [math.DS], 2019. See Table 2 p. 10.
%F A002619 a(n) = Sum_{k|n} u(n, k)/(nk), where u(n, k) = A047918(n, k).
%F A002619 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
%F A002619 From _Richard L. Ollerton_, May 09 2021: (Start)
%F A002619 Let A(n,k) = (1/n^2)*Sum_{d|n} k^d*phi(n/d)^2*(n/d)^d*d!, then:
%F A002619 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)!.
%F A002619 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))!.
%F A002619 a(n) = A(n,1). (End)
%e A002619 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.
%p A002619 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
%t A002619 a[n_] := EulerPhi[#]^2*(n/#)!*#^(n/#)/n^2 & /@ Divisors[n] // Total; a /@ Range[23] (* _Jean-François Alcover_, Jul 11 2011, after _Emeric Deutsch_ *)
%o A002619 (PARI) a(n)={sumdiv(n, d, eulerphi(n/d)^2*d!*(n/d)^d)/n^2} \\ _Andrew Howroyd_, Sep 09 2018
%o A002619 (Python)
%o A002619 from sympy import totient, factorial, divisors
%o A002619 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
%Y A002619 Cf. A002618, A047916, A064852, A064649.
%Y A002619 Cf. A000010.
%Y A002619 Cf. A000939, A000940, A089066, A262480, A275527 (other classes of permutations under various symmetries).
%K A002619 nonn,nice,easy
%O A002619 1,3
%A A002619 _N. J. A. Sloane_, _Colin Mallows_