A096203 -id:A096203 - cp's OEIS frontend

A096202 Number of coverings of {1...n} by translation of a single set.

1, 2, 3, 6, 11, 22, 45, 92, 188, 382, 791, 1632, 3357, 6922, 14289, 29542, 61013, 126142, 260664, 538850, 1113372, 2300954, 4752279, 9814226, 20257082, 41798206, 86204773, 177729712, 366231907, 754356336, 1553063269, 3196028942, 6573883225, 13515943986, 27775807554

Offset: 1

Jon Wild, Jul 27 2004

nonn

The number of sets (up to translation) that with their translations can cover {1...n} in at least one way is given by A079500(n). For example, for n = 5 the 8 sets are {1}, {1,2}, {1,3}, {1,2,3}, {1,2,4}, {1,3,4}, {1,2,3,4}, {1,2,3,4,5}. - Andrew Howroyd, Nov 06 2019

			a(5)=11 because the following are the 11 coverings of {1...5}, each one of which only uses a single set and its translations:
   {{1},{2},{3},{4},{5}}
   {{1,2},{3,4},{4,5}}
   {{1,2},{2,3},{3,4},{4,5}}
   {{1,2},{2,3},{4,5}}
   {{1,3},{2,4},{3,5}}
   {{1,2,3},{2,3,4},{3,4,5}}
   {{1,2,3},{3,4,5}}
   {{1,2,4},{2,3,5}}
   {{1,3,4},{2,4,5}}
   {{1,2,3,4},{2,3,4,5}}
   {{1,2,3,4,5}}

Cf. A079500, A096154, A096203.

covers(all, v)={
  my(u=vector(#v+1)); for(i=1, #v, u[i+1]=bitor(u[i], v[i]));
  my(recurse(k,b) = if(bitnegimply(b,u[k+1]), 0, if(k==0, 1, my(t=bitnegimply(b,v[k])); if(t==b, 2*self()(k-1, b), self()(k-1, b) + self()(k-1, t)) )));
  recurse(#v, all)
}
a(n)={sum(i=2^(n-1), 2^n-1, covers(2^n-1, vector(valuation(i,2)+1, j, i>>(j-1))))} \\ Andrew Howroyd, Nov 06 2019

a(14)-a(32) from Andrew Howroyd, Nov 06 2019

a(33)-a(35) from Jinyuan Wang, Jun 09 2021

A096154 Number of tilings of {1...n} by translation and reflection of a single set.

Original entry on oeis.org

1, 2, 2, 4, 2, 8, 2, 13, 6, 20, 2, 56, 2, 68, 12, 160, 2, 299, 2, 584, 18, 1028, 2, 2338, 8, 4100, 38, 8456, 2, 16576, 2, 33469, 30, 65540

Offset: 1

Jon Wild, Jul 26 2004

nonn

a(n) counts the partitions of {1...n} with the property that all elements of the partition are congruent, modulo translation and reflection, to the same tile.

Two tilings that are reflections of each other are considered distinct. E.g. {{1,2,6},{3,7,8},{4,5,9}} and {{1,5,6},{2,3,7},{4,8,9}} are both included in the count for a(9). The first tile that allows more than one tiling for the same set without one being a reflection of the other is {1,2,7} on the span {1...12}.

			a(8)=13 because the following are the 13 tilings of {1...8}:
{{1},{2},{3},{4},{5},{6},{7},{8}} tile: {1}
{{1,2},{3,4},{5,6},{7,8}} tile: {1,2}
{{1,3},{2,4},{5,7},{6,8}} tile: {1,3}
{{1,5},{2,6},{3,7},{4,8}} tile: {1,5}
{{1,2,3,4},{5,6,7,8}} tile: {1,2,3,4}
{{1,2,3,5},{4,6,7,8}} tile: {1,2,3,5}
{{1,5,6,7},{2,3,4,8}} tile: {1,2,3,7}
{{1,2,4,6},{3,5,7,8}} tile: {1,2,4,6}
{{1,4,6,7},{2,3,5,8}} tile: {1,2,4,7}
{{1,2,5,6},{3,4,7,8}} tile: {1,2,5,6}
{{1,3,4,7},{2,5,6,8}} tile: {1,3,4,7}
{{1,3,5,7},{2,4,6,8}} tile: {1,3,5,7}
{{1,2,3,4,5,6,7,8}} tile: {1,2,3,4,5,6,7,8}

Cf. A096202, A096203.

a(n)-4 often seems to be a power of 2. - Don Reble

More terms from Don Reble, Jul 04 2004

A329128 Number of nonequivalent sets whose translations and reflections cover {1..n}.

Original entry on oeis.org

1, 2, 3, 6, 8, 17, 24, 52, 77, 171, 265, 593, 952, 2131, 3519, 7846, 13238, 29351, 50374, 111031, 193155, 423403, 744616, 1624302, 2881784, 6260030, 11186219, 24213106, 43522800, 93922741, 169653109, 365172178

Offset: 1

Andrew Howroyd, Nov 07 2019

Equivalence is up to translation and reflection. Only translations and reflections that are subsets of {1..n} are included.

			For n = 4 there are 6 sets (up to equivalence) that with their reflections and translations cover {1..4}:
  {{1}, {2}, {3}, {4}};
  {{1, 2}, {2, 3}, {3, 4}};
  {{1, 3}, {2, 4}};
  {{1, 2, 4}, {1, 3, 4}};
  {{1, 2, 3}, {2, 3, 4}};
  {{1, 2, 3, 4}}.
.
For n = 5 there are 8 sets (up to equivalence) that with their reflections and translations cover {1..5}:
  {{1}, {2}, {3}, {4}, {5}};
  {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
  {{1, 3}, {2, 4}, {3, 5}};
  {{1, 2, 4}, {1, 3, 4}, {2, 3, 5}, {2, 4, 5}};
  {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}};
  {{1, 2, 3, 5}, {1, 3, 4, 5}};
  {{1, 2, 3, 4}, {2, 3, 4, 5}};
  {{1, 2, 3, 4, 5}}.

Cf. A079500 (if only translations allowed).

Cf. A096202, A096203, A329235.

cp's OEIS Frontend

A096202 Number of coverings of {1...n} by translation of a single set.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A096154 Number of tilings of {1...n} by translation and reflection of a single set.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A329128 Number of nonequivalent sets whose translations and reflections cover {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs