|
Search: id:A002619
|
|
|
| A002619 |
|
Number of 2-colored patterns on an n X n board.
(Formerly M0887 N0336)
|
|
+0
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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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
|
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)
|
|
CROSSREFS
|
Cf. A002618, A047916, A064852, A064649.
Cf. A000010.
Sequence in context: A038561 A055981 A120260 this_sequence A129202 A127905 A009224
Adjacent sequences: A002616 A002617 A002618 this_sequence A002620 A002621 A002622
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
njas, C. L. Mallows (colinm(AT)research.avayalabs.com)
|
|
|
Search completed in 0.002 seconds
|
