A096154 -id:A096154 - 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

A096203 Number of coverings of {1..n} by translation and reflection of a single set.

Original entry on oeis.org

1, 2, 3, 7, 18, 66, 239, 963, 3792, 15230, 60297, 240295, 952530, 3783000, 14999274, 59492918, 235852544, 935260075, 3707948564, 14702345112, 58294850481, 231152521791, 916584704599, 3634684693457, 14413639272087

Offset: 1

Jon Wild, Jul 27 2004

nonn

			a(4) = 7 because the following are the 7 coverings of {1...4}, each one of which only uses a single set and its translations and reflections:
  {{1}, {2}, {3}, {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}}.
.
a(5) = 18 because the following are the 18 coverings of {1...5}, each one of which only uses a single set and its translations and reflections:
  {{1}, {2}, {3}, {4}, {5}};
  {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
  {{1, 2}, {2, 3}, {4, 5}};
  {{1, 2}, {3, 4}, {4, 5}};
  {{1, 3}, {2, 4}, {3, 5}};
  {{1, 2, 4}, {1, 3, 4}, {2, 3, 5}, {2, 4, 5}};
  {{1, 2, 4}, {1, 3, 4}, {2, 3, 5}};
  {{1, 2, 4}, {1, 3, 4}, {2, 4, 5}};
  {{1, 2, 4}, {2, 3, 5}, {2, 4, 5}};
  {{1, 3, 4}, {2, 3, 5}, {2, 4, 5}};
  {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}};
  {{1, 2, 4}, {2, 3, 5}};
  {{1, 3, 4}, {2, 3, 5}};
  {{1, 3, 4}, {2, 4, 5}};
  {{1, 2, 3}, {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. A096202 (if only translations allowed).

Cf. A096154, A329128.

Corrected by Andrew Howroyd, Nov 08 2019

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