login
Number of partitions of n into parts which are a sum of exactly as many distinct powers of 2 as n has 1's in its binary representation.
5

%I #22 Dec 12 2021 18:04:49

%S 1,1,2,1,4,1,2,1,10,3,2,1,5,1,2,1,36,6,12,1,11,3,2,1,24,3,3,1,5,1,2,1,

%T 202,67,55,9,93,4,5,1,112,8,13,1,10,3,2,1,304,22,18,1,20,3,3,1,34,3,3,

%U 1,5,1,2,1,1828,1267,1456,71,1629,77,100,2,2342,99,123,9,132,4,3,1

%N Number of partitions of n into parts which are a sum of exactly as many distinct powers of 2 as n has 1's in its binary representation.

%H Alois P. Heinz, <a href="/A091891/b091891.txt">Table of n, a(n) for n = 0..16384</a> (terms n = 1..1000 from Andrew Howroyd)

%F a(A000079(n)) = A018819(n);

%F a(A018900(n)) = A091889(n);

%F a(A014311(n)) = A091890(n);

%F a(A091892(n)) = 1.

%e a(9) = 3 because there are 3 partitions of 9 into parts of size 3, 5, 6, 9 which are the numbers that have two 1's in their binary representations. The 3 partitions are: 9, 6 + 3 and 3 + 3 + 3. - _Andrew Howroyd_, Apr 20 2021

%p H:= proc(n) option remember; add(i, i=Bits[Split](n)) end:

%p v:= proc(n, k) option remember; `if`(n<1, 0,

%p `if`(H(n)=k, n, v(n-1, k)))

%p end:

%p b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p b(n, v(i-1, k), k)+b(n-i, v(min(n-i, i), k), k)))

%p end:

%p a:= n-> b(n$2, H(n)):

%p seq(a(n), n=0..80); # _Alois P. Heinz_, Dec 12 2021

%t etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}] b[n - j], {j, 1, n}]/n]; b];

%t EulerT[v_List] := With[{q = etr[v[[#]]&]}, q /@ Range[Length[v]]];

%t a[n_] := EulerT[Table[DigitCount[k, 2, 1] == DigitCount[n, 2, 1] // Boole, {k, 1, n}]][[n]];

%t Array[a, 100] (* _Jean-François Alcover_, Dec 12 2021, after _Andrew Howroyd_ *)

%o (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}

%o a(n) = {EulerT(vector(n,k,hammingweight(k)==hammingweight(n)))[n]} \\ _Andrew Howroyd_, Apr 20 2021

%Y Cf. A000079, A000120, A000041, A018819, A018900, A014311.

%Y Cf. A091889, A091890, A091892, A091893.

%K nonn,look

%O 0,3

%A _Reinhard Zumkeller_, Feb 10 2004

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 12 2021