login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A187767 Number of bicolored cyclic patterns n X n. 2
0, 2, 3, 10, 15, 35, 63, 138, 255, 527, 1023, 2083, 4095, 8255, 16383, 32906, 65535, 131327, 262143, 524815, 1048575, 2098175, 4194303, 8390691, 16777215, 33558527, 67108863, 134225983, 268435455, 536887295, 1073741823, 2147516554, 4294967295, 8590000127, 17179869183 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

A bicolored cyclic pattern is a 0-1 n x n matrix where the j-th row is equal to the first row rotated to the left by (j-1)*k places, with 1 <= k <= n a parameter. For example, with first row = 0110 we have

.

. (k=1) 0 1 1 0  (k=2) 0 1 1 0  (k=3) 0 1 1 0  (k=4) 0 1 1 0

.       1 1 0 0        1 0 0 1        0 0 1 1        0 1 1 0

.       1 0 0 1        0 1 1 0        1 0 0 1        0 1 1 0

.       0 0 1 1        1 0 0 1        1 1 0 0        0 1 1 0

The (2^n-2)*n matrices so obtained are reduced considering equivalent those obtained exchanging 0's and 1's and those which produce the same pattern, apart translation.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

Giovanni Resta, Picture explaining sequence definition.

Giovanni Resta, Pictures for a(2)-a(7).

Giovanni Resta, Pictures for a(8) and a(9).

FORMULA

a(1) = 0; a(n) = 2^(n-1)-1 if n is odd, 2^(n-1)+a(n/2) if n is even (conjectured).

a(n) = -1 + Sum_{d|n} d*A000048(d). - Andrew Howroyd, Jun 02 2017

EXAMPLE

a(4)=10 is represented below. See Links for more examples.

. 1000 0100 0010 0001 0101 1010 1001 0110 1100 0011

. 0100 0001 0100 0001 0101 0101 1100 1100 0011 0011

. 0010 0100 1000 0001 0101 1010 0110 1001 1100 0011

. 0001 0001 0001 0001 0101 0101 0011 0011 0011 0011

MATHEMATICA

cyPatt[n_]:=Block[{b, c}, c[v_, q_:1]:=Table[RotateLeft[v, i q], {i, n}]; b=Union[(First@Union[c@#, c[1-#]])& /@ IntegerDigits[Range[2^n/2-1], 2, n]]; Union@Flatten[Table[c[e, j], {j, n}, {e, b}], 1]];

(*count*) a[n_] := Length@cyPatt@n; Print["Seq = ", a/@Range[12]];

(*show*) showP[p_] := GraphicsGrid@Partition[ArrayPlot/@p, 8, 8, 1, Null];

showP[cyPatt[6]]

PROG

(PARI)

b(n)=sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n);

a(n)=sumdiv(n, d, d*b(d)) - 1; \\ Andrew Howroyd, Jun 02 2017

CROSSREFS

The number of patterns made of vertical stripes only is A056295(n).

Cf. A000048, A056303, A127804.

Sequence in context: A075770 A135101 A108065 * A226881 A026336 A027913

Adjacent sequences:  A187764 A187765 A187766 * A187768 A187769 A187770

KEYWORD

nonn

AUTHOR

Giovanni Resta, Jan 04 2013

EXTENSIONS

a(22)-a(35) from Andrew Howroyd, Jun 02 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 14:41 EST 2018. Contains 299623 sequences. (Running on oeis4.)