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