cp's OEIS Frontend

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

%I A364463 #23 Dec 30 2023 21:24:19
%S A364463 1,2,3,6,10,18,30,54,92,167,290,525,935,1704,3082,5664,10386,19249,
%T A364463 35701,66702,124855,234969,443174,839254,1592925,3032757,5786153,
%U A364463 11066413,21204855,40712426,78294085,150815154,290922900,561968268,1086879052,2104570243
%N A364463 Number of subsets of {1..n} with elements disjoint from first differences of elements.
%C A364463 In other words, no element is the difference of two consecutive elements.
%C A364463 From _David A. Corneth_, Aug 02 2023: (Start)
%C A364463 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.
%C A364463 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)
%F A364463 a(n) < a(n + 1) <= 2 * a(n). - _David A. Corneth_, Aug 02 2023
%e A364463 The a(0) = 1 through a(5) = 18 subsets:
%e A364463   {}  {}   {}   {}     {}       {}
%e A364463       {1}  {1}  {1}    {1}      {1}
%e A364463            {2}  {2}    {2}      {2}
%e A364463                 {3}    {3}      {3}
%e A364463                 {1,3}  {4}      {4}
%e A364463                 {2,3}  {1,3}    {5}
%e A364463                        {1,4}    {1,3}
%e A364463                        {2,3}    {1,4}
%e A364463                        {3,4}    {1,5}
%e A364463                        {2,3,4}  {2,3}
%e A364463                                 {2,5}
%e A364463                                 {3,4}
%e A364463                                 {3,5}
%e A364463                                 {4,5}
%e A364463                                 {1,3,5}
%e A364463                                 {2,3,4}
%e A364463                                 {3,4,5}
%e A364463                                 {2,3,4,5}
%t A364463 Table[Length[Select[Subsets[Range[n]],Intersection[#,Differences[#]]=={}&]],{n,0,10}]
%o A364463 (Python)
%o A364463 from itertools import combinations
%o A364463 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
%Y A364463 For all differences of pairs of elements we have A007865.
%Y A364463 For partitions instead of subsets we have A363260, strict A364464.
%Y A364463 The complement is counted by A364466.
%Y A364463 A000041 counts integer partitions, strict A000009.
%Y A364463 A364465 counts subsets with distinct first differences, partitions A325325.
%Y A364463 Cf. A011782, A025065, A229816, A236912, A237113, A237667, A240861, A320347, A323092, A326083, A364347.
%K A364463 nonn
%O A364463 0,2
%A A364463 _Gus Wiseman_, Jul 27 2023
%E A364463 a(21)-a(29) from _David A. Corneth_, Aug 02 2023
%E A364463 a(30)-a(32) from _Chai Wah Wu_, Sep 26 2023
%E A364463 a(33)-a(35) from _Chai Wah Wu_, Sep 27 2023