|
| |
|
|
A002619
|
|
Number of 2-colored patterns on an n X n board.
(Formerly M0887 N0336)
|
|
4
| |
|
|
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; 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 (m.steyer(AT)osram.de), Oct 06 2001
|
|
|
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.
A. Vella, Pattern avoidance in permutations: linear and cyclic orders, The Electronic J. of Combinatorics, 9(2), 2002-3, #R18.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..100
|
|
|
FORMULA
| Sum_{k|n} u(n, k)/(nk), where u(n, k) = A047918(n, k).
a(n)=(1/n^2)Sum[phi(p)^2*(n/p)!*p^(n/p)], where phi is Euler's totient function (A000010) and summation is over all divisors of n. (see the Vella reference, p. 31). - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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); # (Deutsch) (Deutsch)
|
|
|
MATHEMATICA
| a[n_] := EulerPhi[#]^2*(n/#)!*#^(n/#)/n^2 & /@ Divisors[n] // Total; a /@ Range[23] (* From Jean-François Alcover, Jul 11 2011, after E. Deutsch *)
|
|
|
CROSSREFS
| Cf. A002618, A047916, A064852, A064649.
Cf. A000010.
Sequence in context: A055981 A120260 A202592 * A129202 A127905 A009224
Adjacent sequences: A002616 A002617 A002618 * A002620 A002621 A002622
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), C. L. Mallows (colinm(AT)research.avayalabs.com)
|
| |
|
|
