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

%I #19 Jun 09 2021 11:13:08

%S 1,2,3,6,11,22,45,92,188,382,791,1632,3357,6922,14289,29542,61013,

%T 126142,260664,538850,1113372,2300954,4752279,9814226,20257082,

%U 41798206,86204773,177729712,366231907,754356336,1553063269,3196028942,6573883225,13515943986,27775807554

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

%C 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

%e 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:

%e {{1},{2},{3},{4},{5}}

%e {{1,2},{3,4},{4,5}}

%e {{1,2},{2,3},{3,4},{4,5}}

%e {{1,2},{2,3},{4,5}}

%e {{1,3},{2,4},{3,5}}

%e {{1,2,3},{2,3,4},{3,4,5}}

%e {{1,2,3},{3,4,5}}

%e {{1,2,4},{2,3,5}}

%e {{1,3,4},{2,4,5}}

%e {{1,2,3,4},{2,3,4,5}}

%e {{1,2,3,4,5}}

%o (PARI)

%o covers(all, v)={

%o my(u=vector(#v+1)); for(i=1, #v, u[i+1]=bitor(u[i], v[i]));

%o 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)) )));

%o recurse(#v, all)

%o }

%o 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

%Y Cf. A079500, A096154, A096203.

%K nonn

%O 1,2

%A _Jon Wild_, Jul 27 2004

%E a(14)-a(32) from _Andrew Howroyd_, Nov 06 2019

%E a(33)-a(35) from _Jinyuan Wang_, Jun 09 2021