A247935 Number of integer partitions of n whose distinct parts have no binary carries.

1, 1, 2, 3, 4, 5, 8, 10, 11, 14, 18, 21, 26, 30, 38, 49, 47, 55, 66, 74, 84, 96, 110, 126, 134, 151, 171, 195, 209, 235, 272, 318, 307, 349, 377, 422, 448, 491, 534, 595, 617, 674, 734, 801, 841, 925, 998, 1098, 1118, 1219, 1299, 1418, 1476, 1591, 1711, 1865

Offset

0,3

Comments

From Gus Wiseman, Mar 31 2019: (Start)

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the reversed binary expansions of 2, 5, and 8 are

{0,1}

{1,0,1}

{0,0,0,1}

and since there are no columns with more than one 1, the partition (8,5,2) is counted under a(15). The Heinz numbers of these partitions are given by A325097.

(End)

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Example

From Gus Wiseman, Mar 30 2019: (Start)
The a(1) = 1 through a(8) = 11 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (41)     (33)      (43)       (44)
             (111)  (211)   (221)    (42)      (52)       (422)
                    (1111)  (2111)   (222)     (61)       (611)
                            (11111)  (411)     (421)      (2222)
                                     (2211)    (2221)     (4211)
                                     (21111)   (4111)     (22211)
                                     (111111)  (22111)    (41111)
                                               (211111)   (221111)
                                               (1111111)  (2111111)
                                                          (11111111)
(End)

Maple

with(Bits):
b:= proc(n, i, t) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1, t) +`if`(i>n or And(t, i)>0, 0,
      add(b(n-i*j, i-1, Or(t, i)), j=1..n/i))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..80);  # Alois P. Heinz, Dec 28 2014

Mathematica

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
Table[Length[Select[IntegerPartitions[n], stableQ[#, Intersection[binpos[#1], binpos[#2]]!={}&]&]], {n, 0, 20}] (* Gus Wiseman, Mar 30 2019 *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1, t] + If[i > n || BitAnd[t, i] > 0, 0, Sum[b[n - i*j, i - 1, BitOr[t, i]], {j, 1, n/i}]]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 80] (* Jean-François Alcover, May 23 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000110, A000120, A050315, A070939, A080572, A248605, A267610.

Cf. A325095, A325096, A325097, A325098, A325102, A325103, A325109.

Sequence in context: A101547 A047597 A309960 * A005233 A155736 A074897

Adjacent sequences: A247932 A247933 A247934 * A247936 A247937 A247938

Keyword

nonn

Author

David S. Newman, Sep 26 2014

Extensions

More terms from Alois P. Heinz, Oct 15 2014

Name edited by Gus Wiseman, Mar 31 2019

Status

approved