A248605 Partitions into parts of the form k(3k plus or minus 1)/2 (in other words: 1,2,5,7,12,15,...) with a set of frequencies which has no binary carry.

1, 1, 2, 1, 3, 3, 3, 3, 4, 6, 6, 6, 7, 7, 7, 10, 9, 11, 11, 14, 15, 14, 16, 19, 17, 22, 20, 22, 20, 23, 28, 28, 29, 29, 32, 35, 35, 37, 39, 43, 46, 45, 50, 49, 53, 58, 60, 60, 63, 61, 70, 73, 77, 77, 75, 84, 83, 84, 88, 92, 99, 101, 110, 99, 112, 118, 118, 121

Offset: 0

Author

David S. Newman, Oct 09 2014

Keywords

• nonn

Comments

The expression "a set of frequencies which has no binary carry," means the following: For a given partition take the set of frequencies of the summands expressed as binary numbers and add them together. If there is a carry in the addition, then this is not an allowed set of frequencies. See the example for more explanation.

Elements of this sequence have the same parity (A040051) as the corresponding elements of the sequence of unrestricted partitions (A000041). See lemma 2.2.ii of the paper by Cooper, Eichorn and O'Bryant.

From David S. Newman, May 30 2017: (Start)

Also the number of partitions of n into parts which are powers of 2 used with a frequency which is k(3k plus or minus 1)/2.

Every set of partitions defined with the "no binary carry" condition has a dual of this sort. (End)

Examples

			For n=5, there are 4 partitions which have summands coming from {1,2,5,7,...} namely: 5; 2+2+1; 2+1+1+1; and 1+1+1+1. The third of these has frequencies 1 and 3. These frequencies when written in binary are 1 and 11. If we add these two binary numbers there will be a carry from the units column; therefore this set of frequencies is not allowed and the partition 2+1+1+1 is not counted.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• J. N. Cooper, D. Eichhorn and K. O'Bryant, Reciprocals of binary power series, arXiv:math/0506496 [math.NT], 2005.

Crossrefs

Cf. A000041, A001318, A040051.

Programs

Mathematica

<<"Combinatorica`";
nend=20;
For[n=1,n<=nend,n++,
summands={1,2,5,7,12,15,22,26,35,40};
p=Partitions[n];preduced=p;
For[i=Length[p],i>=1,i--,
For[j=1,j<=Length[p[[i]]],j++,
If[MemberQ[summands,p[[i]][[j]]]= =False,preduced=Delete[preduced,i];
Break[]]]];
For[i=Length[preduced],i>=1,i--,
t=Tally[preduced[[i]]];
For[j=1,j<=nend,j++,sum[j]=0];
For[j=1,j<=Length[t],j++,
IntDig=IntegerDigits[t[[j,2]],2,7];
For[k=1,k<=7,k++,sum[k]=sum[k]+IntDig[[k]]]];
table=Table[sum[k],{k,1,7}];
If[Max[table]>1,preduced=Delete[preduced,i]]];
a[n]=Length[preduced]];
Print[Table[a[i],{i,1,nend}]]

Extensions

More terms from Alois P. Heinz, Oct 13 2014