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,2

Comments

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

Links

Table of n, a(n) for n=1..35.

Example

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}}

Prog

(PARI)
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

Crossrefs

Cf. A079500, A096154, A096203.

Sequence in context: A007477 A274936 A244521 * A036653 A318031 A316500

Adjacent sequences: A096199 A096200 A096201 * A096203 A096204 A096205

Keyword

nonn

Author

Jon Wild, Jul 27 2004

Extensions

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

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

Status

approved