A364465 -id:A364465 - cp's OEIS frontend

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

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

A364464 Number of strict integer partitions of n where no part is the difference of two consecutive parts.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 2, 4, 4, 6, 5, 8, 9, 12, 13, 16, 16, 21, 23, 29, 34, 38, 41, 49, 57, 64, 73, 86, 95, 110, 120, 135, 160, 171, 197, 219, 247, 277, 312, 342, 386, 431, 476, 527, 598, 640, 727, 796, 893, 966, 1097, 1178, 1327, 1435, 1602, 1740, 1945, 2084, 2337

Offset: 0

Gus Wiseman, Jul 30 2023

nonn

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

			The strict partition y = (9,5,3,1) has differences (4,2,2), and these are disjoint from the parts, so y is counted under a(18).
The a(1) = 1 through a(9) = 6 strict partitions:
  (1)  (2)  (3)  (4)    (5)    (6)    (7)    (8)    (9)
                 (3,1)  (3,2)  (5,1)  (4,3)  (5,3)  (5,4)
                        (4,1)         (5,2)  (6,2)  (7,2)
                                      (6,1)  (7,1)  (8,1)
                                                    (4,3,2)
                                                    (5,3,1)

For length instead of differences we have A240861, non-strict A229816.
For all differences of pairs of elements we have A364346, for subsets A007865.
For subsets instead of strict partitions we have A364463, complement A364466.
The non-strict version is A363260.
The complement is counted by A364536, non-strict A364467.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A120641 counts strict double-free partitions, non-strict A323092.
A320347 counts strict partitions w/ distinct differences, non-strict A325325.
Cf. A002865, A025065, A236912, A237667, A275972, A363226, A364345, A364465.

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

from collections import Counter
from sympy.utilities.iterables import partitions
def A364464(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 set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023

cp's OEIS Frontend

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