A364464 -id:A364464 - cp's OEIS frontend

A363260 Number of integer partitions of n with parts disjoint from first differences of parts, meaning no part is the difference of two consecutive parts.

1, 1, 2, 2, 4, 5, 7, 10, 13, 17, 21, 28, 35, 46, 57, 70, 87, 110, 130, 165, 198, 238, 285, 349, 410, 498, 583, 702, 819, 983, 1136, 1353, 1570, 1852, 2137, 2520, 2898, 3390, 3891, 4540, 5191, 6028, 6889, 7951, 9082, 10450, 11884, 13650, 15508, 17728, 20113

Offset: 0

Gus Wiseman, Jul 19 2023

nonn

			The a(1) = 1 through a(8) = 13 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (111)  (22)    (32)     (33)      (43)       (44)
                    (31)    (41)     (51)      (52)       (53)
                    (1111)  (311)    (222)     (61)       (62)
                            (11111)  (411)     (322)      (71)
                                     (3111)    (331)      (332)
                                     (111111)  (511)      (611)
                                               (4111)     (2222)
                                               (31111)    (3311)
                                               (1111111)  (5111)
                                                          (41111)
                                                          (311111)
                                                          (11111111)

For length instead of differences we have A229816, strict A240861.
For all differences of pairs parts we have A364345.
For subsets of {1..n} instead of partitions we have A364463.
The strict case is A364464.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A323092 counts double-free partitions, ranks A320340.
A325325 counts partitions with distinct first-differences.
Cf. A002865, A025065, A108917, A236912, A237113, A237667, A320347, A326083, A363225, A364347.

Table[Length[Select[IntegerPartitions[n],Intersection[#,-Differences[#]]=={}&]],{n,0,30}]

from collections import Counter
from sympy.utilities.iterables import partitions
def A363260(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), partitions(n,size=True)) if set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023

A364463 Number of subsets of {1..n} with elements disjoint from first differences of elements.

Original entry on oeis.org

1, 2, 3, 6, 10, 18, 30, 54, 92, 167, 290, 525, 935, 1704, 3082, 5664, 10386, 19249, 35701, 66702, 124855, 234969, 443174, 839254, 1592925, 3032757, 5786153, 11066413, 21204855, 40712426, 78294085, 150815154, 290922900, 561968268, 1086879052, 2104570243

Offset: 0

Gus Wiseman, Jul 27 2023

nonn

In other words, no element is the difference of two consecutive elements.
From David A. Corneth, Aug 02 2023: (Start)
As subsets counted in a(n) are also counted in a(n+1) and {n+1} is a subset counted in a(n+1) but not a(n), a(n + 1) > a(n) for n >= 1.
As every subset counted in a(n + 1) that contains n+1 can be found from some subset counted in a(n) by appending n+1 and every subset counted in a(n) not containing n + 1 is counted in a(n + 1), a(n+1) <= 2*a(n). (End)

			The a(0) = 1 through a(5) = 18 subsets:
  {}  {}   {}   {}     {}       {}
      {1}  {1}  {1}    {1}      {1}
           {2}  {2}    {2}      {2}
                {3}    {3}      {3}
                {1,3}  {4}      {4}
                {2,3}  {1,3}    {5}
                       {1,4}    {1,3}
                       {2,3}    {1,4}
                       {3,4}    {1,5}
                       {2,3,4}  {2,3}
                                {2,5}
                                {3,4}
                                {3,5}
                                {4,5}
                                {1,3,5}
                                {2,3,4}
                                {3,4,5}
                                {2,3,4,5}

For all differences of pairs of elements we have A007865.
For partitions instead of subsets we have A363260, strict A364464.
The complement is counted by A364466.
A000041 counts integer partitions, strict A000009.
A364465 counts subsets with distinct first differences, partitions A325325.
Cf. A011782, A025065, A229816, A236912, A237113, A237667, A240861, A320347, A323092, A326083, A364347.

Table[Length[Select[Subsets[Range[n]],Intersection[#,Differences[#]]=={}&]],{n,0,10}]

from itertools import combinations
def A364463(n): return sum(1 for l in range(n+1) for c in combinations(range(1,n+1),l) if set(c).isdisjoint({c[i+1]-c[i] for i in range(l-1)})) # Chai Wah Wu, Sep 26 2023

a(n) < a(n + 1) <= 2 * a(n). - David A. Corneth, Aug 02 2023

a(21)-a(29) from David A. Corneth, Aug 02 2023
a(30)-a(32) from Chai Wah Wu, Sep 26 2023
a(33)-a(35) from Chai Wah Wu, Sep 27 2023

A364466 Number of subsets of {1..n} where some element is a difference of two consecutive elements.

Original entry on oeis.org

0, 0, 1, 2, 6, 14, 34, 74, 164, 345, 734, 1523, 3161, 6488, 13302, 27104, 55150, 111823, 226443, 457586, 923721, 1862183, 3751130, 7549354, 15184291, 30521675, 61322711, 123151315, 247230601, 496158486, 995447739, 1996668494, 4004044396, 8027966324, 16092990132, 32255168125

Offset: 0

Gus Wiseman, Jul 31 2023

nonn

In other words, the elements are not disjoint from their own first differences.

			The a(0) = 0 through a(5) = 14 subsets:
  .  .  {1,2}  {1,2}    {1,2}      {1,2}
               {1,2,3}  {2,4}      {2,4}
                        {1,2,3}    {1,2,3}
                        {1,2,4}    {1,2,4}
                        {1,3,4}    {1,2,5}
                        {1,2,3,4}  {1,3,4}
                                   {1,4,5}
                                   {2,3,5}
                                   {2,4,5}
                                   {1,2,3,4}
                                   {1,2,3,5}
                                   {1,2,4,5}
                                   {1,3,4,5}
                                   {1,2,3,4,5}

For differences of all pairs we have A093971, complement A196723.
For partitions we have A363260, complement A364467.
The complement is counted by A364463.
For subset-sums instead of differences we have A364534, complement A325864.
For strict partitions we have A364536, complement A364464.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A050291 counts double-free subsets, complement A088808.
A108917 counts knapsack partitions, strict A275972.
A325325 counts partitions with all distinct differences, strict A320347.
Cf. A011782, A212986, A237113, A325877, A325878, A326083, A363225.

Table[Length[Select[Subsets[Range[n]],Intersection[#,Differences[#]]!={}&]],{n,0,10}]

from itertools import combinations
def A364466(n): return sum(1 for l in range(n+1) for c in combinations(range(1,n+1),l) if not set(c).isdisjoint({c[i+1]-c[i] for i in range(l-1)})) # Chai Wah Wu, Sep 26 2023

a(n) = 2^n - A364463(n). - Chai Wah Wu, Sep 26 2023

a(21)-a(32) from Chai Wah Wu, Sep 26 2023

a(33)-a(35) from Chai Wah Wu, Sep 27 2023

A364467 Number of integer partitions of n where some part is the difference of two consecutive parts.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 4, 5, 9, 13, 21, 28, 42, 55, 78, 106, 144, 187, 255, 325, 429, 554, 717, 906, 1165, 1460, 1853, 2308, 2899, 3582, 4468, 5489, 6779, 8291, 10173, 12363, 15079, 18247, 22124, 26645, 32147, 38555, 46285, 55310, 66093, 78684, 93674, 111104

Offset: 0

Gus Wiseman, Jul 31 2023

nonn

In other words, the parts are not disjoint from their own first differences.

			The a(3) = 1 through a(9) = 13 partitions:
  (21)  (211)  (221)   (42)     (421)     (422)      (63)
               (2111)  (321)    (2221)    (431)      (621)
                       (2211)   (3211)    (521)      (3321)
                       (21111)  (22111)   (3221)     (4221)
                                (211111)  (4211)     (4311)
                                          (22211)    (5211)
                                          (32111)    (22221)
                                          (221111)   (32211)
                                          (2111111)  (42111)
                                                     (222111)
                                                     (321111)
                                                     (2211111)
                                                     (21111111)

For all differences of pairs parts we have A363225, complement A364345.
The complement is counted by A363260.
For subsets of {1..n} we have A364466, complement A364463.
The strict case is A364536, complement A364464.
These partitions have ranks A364537.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A050291 counts double-free subsets, complement A088808.
A323092 counts double-free partitions, ranks A320340.
A325325 counts partitions with distinct first differences.
Cf. A002865, A025065, A093971, A108917, A196723, A229816, A236912, A237113, A237667, A320347, A326083.

Table[Length[Select[IntegerPartitions[n],Intersection[#,-Differences[#]]!={}&]],{n,0,30}]

from collections import Counter
from sympy.utilities.iterables import partitions
def A364467(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), partitions(n,size=True)) if not set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023

A364536 Number of strict integer partitions of n where some part is a difference of two consecutive parts.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 2, 1, 2, 2, 5, 4, 6, 6, 9, 11, 16, 17, 23, 25, 30, 38, 48, 55, 65, 78, 92, 106, 127, 146, 176, 205, 230, 277, 315, 366, 421, 483, 552, 640, 727, 829, 950, 1083, 1218, 1408, 1577, 1794, 2017, 2298, 2561, 2919, 3255, 3685, 4116, 4638, 5163

Offset: 0

Gus Wiseman, Jul 31 2023

nonn

In other words, strict partitions with parts not disjoint from first differences.

			The a(3) = 1 through a(15) = 11 partitions (A = 10, B = 11, C = 12):
  21  .  .  42   421  431  63   532   542   84    742   743   A5
            321       521  621  541   632   642   841   752   843
                                631   821   651   A21   761   942
                                721   5321  921   5431  842   C21
                                4321        5421  6421  B21   6432
                                            6321  7321  6431  6531
                                                        6521  7431
                                                        7421  7521
                                                        8321  8421
                                                              9321
                                                              54321

For all differences of pairs we have A363226, non-strict A363225.
For all non-differences of pairs we have A364346, strict A364345.
The strict complement is counted by A364464, non-strict A363260.
For subsets of {1..n} we have A364466, complement A364463.
The non-strict case is A364467, ranks A364537.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A323092 counts double-free partitions, strict A120641.
A325325 counts partitions with distinct first-differences, strict A320347.
Cf. A002865, A025065, A093971, A108917, A229816, A236912, A237113, A237667, A326083, A364347.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Intersection[#,-Differences[#]]!={}&]],{n,0,30}]

from collections import Counter
from sympy.utilities.iterables import partitions
def A364536(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), filter(lambda p:max(p[1].values(),default=1)==1,partitions(n,size=True))) if not set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023

A364537 Heinz numbers of integer partitions where some part is the difference of two consecutive parts.

Original entry on oeis.org

6, 12, 18, 21, 24, 30, 36, 42, 48, 54, 60, 63, 65, 66, 70, 72, 78, 84, 90, 96, 102, 108, 114, 120, 126, 130, 132, 133, 138, 140, 144, 147, 150, 154, 156, 162, 165, 168, 174, 180, 186, 189, 192, 195, 198, 204, 210, 216, 222, 228, 231, 234, 240, 246, 252, 258

Offset: 1

Gus Wiseman, Aug 02 2023

nonn

In other words, partitions whose parts are not disjoint from their first differences.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The partition {3,4,5,7} with Heinz number 6545 has first differences (1,1,2) so is not in the sequence.
The terms together with their prime indices begin:
   6: {1,2}
  12: {1,1,2}
  18: {1,2,2}
  21: {2,4}
  24: {1,1,1,2}
  30: {1,2,3}
  36: {1,1,2,2}
  42: {1,2,4}
  48: {1,1,1,1,2}
  54: {1,2,2,2}
  60: {1,1,2,3}
  63: {2,2,4}
  65: {3,6}
  66: {1,2,5}
  70: {1,3,4}
  72: {1,1,1,2,2}
  78: {1,2,6}
  84: {1,1,2,4}
  90: {1,2,2,3}
  96: {1,1,1,1,1,2}

For all differences of pairs the complement is A364347, counted by A364345.
For all differences of pairs we have A364348, counted by A363225.
Subsets of {1..n} of this type are counted by A364466, complement A364463.
These partitions are counted by A364467, complement A363260.
The strict case is A364536, complement A364464.
A050291 counts double-free subsets, complement A088808.
A323092 counts double-free partitions, ranks A320340.
A325325 counts partitions with distinct first differences.
Cf. A002865, A025065, A093971, A108917, A196723, A229816, A236912, A237113, A237667, A320347, A326083.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#],Differences[prix[#]]]!={}&]

A364673 Number of (necessarily strict) integer partitions of n containing all of their own first differences.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 2, 1, 2, 2, 2, 5, 2, 2, 4, 2, 3, 6, 4, 4, 8, 4, 4, 10, 8, 7, 8, 13, 9, 15, 12, 13, 17, 20, 15, 31, 24, 27, 32, 33, 32, 50, 42, 45, 53, 61, 61, 85, 76, 86, 101, 108, 118, 137, 141, 147, 179, 184, 196, 222, 244, 257, 295, 324, 348, 380, 433

Offset: 0

Gus Wiseman, Aug 03 2023

nonn

			The partition y = (12,6,3,2,1) has differences (6,3,1,1), and {1,3,6} is a subset of {1,2,3,6,12}, so y is counted under a(24).
The a(n) partitions for n = 1, 3, 6, 12, 15, 18, 21:
  (1)  (3)    (6)      (12)       (15)         (18)         (21)
       (2,1)  (4,2)    (8,4)      (10,5)       (12,6)       (14,7)
              (3,2,1)  (6,4,2)    (8,4,2,1)    (9,6,3)      (12,6,3)
                       (5,4,2,1)  (5,4,3,2,1)  (6,5,4,2,1)  (8,6,4,2,1)
                       (6,3,2,1)               (7,5,3,2,1)  (9,5,4,2,1)
                                               (8,4,3,2,1)  (9,6,3,2,1)
                                                            (10,5,3,2,1)
                                                            (6,5,4,3,2,1)

John Tyler Rascoe, Table of n, a(n) for n = 0..200

Containing all differences: A007862.
Containing no differences: A364464, strict complement A364536.
Containing at least one difference: A364467, complement A363260.
For subsets of {1..n} we have A364671, complement A364672.
A non-strict version is A364674.
For submultisets instead of subsets we have A364675.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A236912 counts sum-free partitions w/o re-used parts, complement A237113.
A325325 counts partitions with distinct first differences.
Cf. A002865, A025065, A196723, A229816, A237667, A320347, A363225, A364272, A364345, A364463, A364537, A370386.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&SubsetQ[#,-Differences[#]]&]],{n,0,30}]

from collections import Counter
def A364673_list(maxn):
    count = Counter()
    for i in range(maxn//3):
        A,f,i = [[(i+1, )]],0,0
        while f == 0:
            A.append([])
            for j in A[i]:
                for k in j:
                    x = j + (j[-1] + k, )
                    y = sum(x)
                    if y <= maxn:
                        A[i+1].append(x)
                        count.update({y})
            if len(A[i+1]) < 1: f += 1
            i += 1
    return [count[z]+1 for z in range(maxn+1)] # John Tyler Rascoe, Mar 09 2024

A364671 Number of subsets of {1..n} containing all of their own first differences.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 23, 34, 58, 96, 171, 302, 565, 1041, 1969, 3719, 7105, 13544, 25999, 49852, 95949, 184658, 356129, 687068, 1327540, 2566295, 4966449, 9617306, 18640098, 36150918, 70166056, 136272548, 264844111, 515036040, 1002211421, 1951345157, 3801569113

Offset: 0

Gus Wiseman, Aug 04 2023

nonn

			The subset {1,2,4,5,10,14} has differences (1,2,1,5,4) so is counted under a(14).
The a(0) = 1 through a(5) = 14 subsets:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {2}    {2}      {2}        {2}
           {1,2}  {3}      {3}        {3}
                  {1,2}    {4}        {4}
                  {1,2,3}  {1,2}      {5}
                           {2,4}      {1,2}
                           {1,2,3}    {2,4}
                           {1,2,4}    {1,2,3}
                           {1,2,3,4}  {1,2,4}
                                      {1,2,3,4}
                                      {1,2,3,5}
                                      {1,2,4,5}
                                      {1,2,3,4,5}

Rémy Sigrist, C++ program

For differences of all strict pairs we have A054519, for partitions A007862.
For "disjoint" instead of "subset" we have A364463, partitions A363260.
For "non-disjoint" we have A364466, partitions A364467 (strict A364536).
The complement is counted by A364672, partitions A364673, A364674, A364675.
First differences of terms are A364752, complement A364753.
Cf. A151897, A196723, A237667, A237668, A325325, A326083, A363225, A364345, A364464, A364537.

Table[Length[Select[Subsets[Range[n]], SubsetQ[#,Differences[#]]&]], {n,0,10}]

More terms from Rémy Sigrist, Aug 06 2023

A364672 Number of subsets of {1..n} not containing all of their own first differences.

Original entry on oeis.org

0, 0, 0, 2, 6, 18, 41, 94, 198, 416, 853, 1746, 3531, 7151, 14415, 29049, 58431, 117528, 236145, 474436, 952627, 1912494, 3838175, 7701540, 15449676, 30988137, 62142415, 124600422, 249795358, 500719994, 1003575768, 2011211100, 4030123185, 8074898552, 16177657763, 32408393211, 64917907623

Offset: 0

Gus Wiseman, Aug 05 2023

nonn

			The a(0) = 0 through a(5) = 18 subsets:
  .  .  .  {1,3}  {1,3}    {1,3}
           {2,3}  {1,4}    {1,4}
                  {2,3}    {1,5}
                  {3,4}    {2,3}
                  {1,3,4}  {2,5}
                  {2,3,4}  {3,4}
                           {3,5}
                           {4,5}
                           {1,2,5}
                           {1,3,4}
                           {1,3,5}
                           {1,4,5}
                           {2,3,4}
                           {2,3,5}
                           {2,4,5}
                           {3,4,5}
                           {1,3,4,5}
                           {2,3,4,5}

For disjunction instead of containment we have A364463, partitions A363260.
For overlap we have A364466, partitions A364467 (strict A364536).
The complement is counted by A364671, partitions A364673, A364674, A364675.
First differences of terms are A364753, complement A364752.
Cf. A007862, A054519, A151897, A237667, A325325, A326083, A363225, A364345, A364464, A364537.

Table[Length[Select[Subsets[Range[n]],!SubsetQ[#,Differences[#]]&]],{n,0,10}]

a(n) = 2^n - A364671(n). - Andrew Howroyd, Jan 27 2024

a(21) onwards (using A364671) added by Andrew Howroyd, Jan 27 2024

A364675 Number of integer partitions of n whose nonzero first differences are a submultiset of the parts.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 7, 7, 10, 12, 15, 15, 26, 25, 35, 45, 55, 60, 86, 94, 126, 150, 186, 216, 288, 328, 407, 493, 610, 699, 896, 1030, 1269, 1500, 1816, 2130, 2620, 3029, 3654, 4300, 5165, 5984, 7222, 8368, 9976, 11637, 13771, 15960, 18978, 21896, 25815, 29915

Offset: 0

Gus Wiseman, Aug 04 2023

nonn

Conjecture: For subsets of {1..n} instead of partitions of n we have A101925.

Conjecture: The strict version is A154402.

			The partition y = (3,2,1,1) has first differences (1,1,0), and (1,1) is a submultiset of y, so y is counted under a(7).
The a(1) = 1 through a(8) = 10 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (221)    (33)      (421)      (44)
             (111)  (211)   (2111)   (42)      (2221)     (422)
                    (1111)  (11111)  (222)     (3211)     (2222)
                                     (2211)    (22111)    (4211)
                                     (21111)   (211111)   (22211)
                                     (111111)  (1111111)  (32111)
                                                          (221111)
                                                          (2111111)
                                                          (11111111)

For subsets of {1..n} we appear to have A101925, A364671, A364672.
The strict case (no differences of 0) appears to be A154402.
Starting with the distinct parts gives A342337.
For disjoint multisets: A363260, subsets A364463, strict A364464.
For overlapping multisets: A364467, ranks A364537, strict A364536.
For subsets instead of submultisets we have A364673.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A236912 counts sum-free partitions, complement A237113.
A325325 counts partitions with distinct first differences.
Cf. A002865, A007862, A108917, A229816, A237667, A237668, A320347, A363225, A364272, A364345, A364466.

submultQ[cap_,fat_] := And@@Function[i,Count[fat,i] >= Count[cap,i]] /@ Union[List@@cap];
Table[Length[Select[IntegerPartitions[n], submultQ[Differences[Union[#]],#]&]], {n,0,30}]

cp's OEIS Frontend

A363260 Number of integer partitions of n with parts disjoint from first differences of parts, meaning no part is the difference of two consecutive parts.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

A364463 Number of subsets of {1..n} with elements disjoint from first differences of elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A364466 Number of subsets of {1..n} where some element is a difference of two consecutive elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A364467 Number of integer partitions of n where some part is the difference of two consecutive parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

A364536 Number of strict integer partitions of n where some part is a difference of two consecutive parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

A364537 Heinz numbers of integer partitions where some part is the difference of two consecutive parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A364673 Number of (necessarily strict) integer partitions of n containing all of their own first differences.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

A364671 Number of subsets of {1..n} containing all of their own first differences.

Views

Author

Keywords

Examples

Links

Crossrefs