A238423 -id:A238423 - cp's OEIS frontend

A238424 Number of partitions of n without three consecutive parts in arithmetic progression.

1, 1, 2, 2, 4, 5, 6, 8, 13, 13, 19, 24, 30, 36, 47, 54, 72, 85, 106, 123, 151, 178, 220, 256, 314, 362, 432, 505, 605, 692, 827, 953, 1121, 1303, 1522, 1729, 2037, 2321, 2691, 3095, 3577, 4061, 4699, 5334, 6126, 6959, 7966, 9005, 10317, 11638, 13252, 14977

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 26 2014

nonn

Also the number of partitions of n whose first differences are an anti-run, meaning there are no adjacent equal differences. - Gus Wiseman, Mar 31 2020

			The a(8) = 13 such partitions are:
01:  [ 3 2 2 1 ]
02:  [ 3 3 1 1 ]
03:  [ 3 3 2 ]
04:  [ 4 2 1 1 ]
05:  [ 4 2 2 ]
06:  [ 4 3 1 ]
07:  [ 4 4 ]
08:  [ 5 2 1 ]
09:  [ 5 3 ]
10:  [ 6 1 1 ]
11:  [ 6 2 ]
12:  [ 7 1 ]
13:  [ 8 ]

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000 (terms 0..300 from Joerg Arndt and Alois P. Heinz, terms 301..350 from Fausto A. C. Cariboni)
Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts

Cf. A238433 (partitions avoiding equidistant arithmetic progressions).
Cf. A238571 (partitions avoiding any arithmetic progression).
Cf. A238687.
The version for compositions is A238423, with strict case A325849.
The version for permutations is A295370.
The strict case is A332668.
The Heinz numbers of these partitions are the complement of A333195.
Partitions with equal differences are A049988.
Cf. A007862, A175342, A325850, A325851, A325852, A325874, A333631.

a[n_,r_,d_] := a[n,r,d] = Block[{j}, If[n == 0, 1, Sum[If[j == r+d, 0, a[n-j, j, j - r]], {j, Min[n, r]}]]]; a[n_] := a[n, 2*n+1, 0]; a /@ Range[0, 100] (* Giovanni Resta, Mar 02 2014 *)
Table[Length[Select[IntegerPartitions[n],!MemberQ[Differences[#,2],0]&]],{n,0,30}] (* Gus Wiseman, Mar 31 2020 *)

A054519 Number of increasing arithmetic progressions of nonnegative integers ending in n, including those of length 1 or 2.

Original entry on oeis.org

1, 2, 4, 6, 9, 11, 15, 17, 21, 24, 28, 30, 36, 38, 42, 46, 51, 53, 59, 61, 67, 71, 75, 77, 85, 88, 92, 96, 102, 104, 112, 114, 120, 124, 128, 132, 141, 143, 147, 151, 159, 161, 169, 171, 177, 183, 187, 189, 199, 202, 208, 212, 218, 220, 228, 232, 240, 244, 248

Offset: 0

Henry Bottomley, Apr 07 2000

a(0)=1, a(n) = a(n-1) + sigma_0(n) (A000005). - Ctibor O. Zizka, Nov 08 2008
a(n) is the index of the n-th term of A027750 whose value is 1. - Michel Marcus, Oct 15 2015
From Gus Wiseman, Jun 07 2019: (Start)
Also the number of subsets of {1..n} that are closed under taking the difference of two strictly decreasing terms. For example, the a(0) = 1 through a(6) = 15 subsets are:
  {}  {}   {}     {}       {}         {}           {}
      {1}  {1}    {1}      {1}        {1}          {1}
           {2}    {2}      {2}        {2}          {2}
           {1,2}  {3}      {3}        {3}          {3}
                  {1,2}    {4}        {4}          {4}
                  {1,2,3}  {1,2}      {5}          {5}
                           {2,4}      {1,2}        {6}
                           {1,2,3}    {2,4}        {1,2}
                           {1,2,3,4}  {1,2,3}      {2,4}
                                      {1,2,3,4}    {3,6}
                                      {1,2,3,4,5}  {1,2,3}
                                                   {2,4,6}
                                                   {1,2,3,4}
                                                   {1,2,3,4,5}
                                                   {1,2,3,4,5,6}
(End)

			a(3)=6 because the six increasing progressions (3), (2,3), (1,2,3), (0,1,2,3), (1,3) and (0,3) all end in 3.

Marius A. Burtea, Table of n, a(n) for n = 0..10000 (term 0..1000 from T. D. Noe).
Wikipedia, Arithmetic progression

Cf. A000005, A006218, A027750, A051336. Left edge of A056535.

Cf. A007862, A049988, A175342, A238423, A295370, A325849.

[1] cat [&+[Ceiling((k+1)/(i+1)): i in [1..k+1]]: k in [1..60]]; // Marius A. Burtea, Jun 10 2019

IBI:= {{}}: a[0]:= 1: for n from 1 to 45 do IBI:= IBI union map(t -> t union {n}, select(t -> (t minus map(q -> n-q, t)={}), IBI)); a[n]:= nops(IBI) od: seq(a[n], n=0..45); # Zerinvary Lajos, Mar 18 2007
with(numtheory):a[1]:=2: for n from 2 to 59 do a[n]:=a[n-1]+tau(n) od: seq(a[n], n=0..45); # Zerinvary Lajos, Mar 21 2009
map(`+`, ListTools:-PartialSums(map(numtheory:-tau, [$0..1000])),1); # Robert Israel, Oct 15 2015

a[0]=1; a[n_] := a[n] = a[n-1] + DivisorSigma[0, n]; Table[a[n], {n, 0, 45}] (* Jean-François Alcover, Oct 05 2012, after Ctibor O. Zizka *)
nxt[{n_,a_}]:={n+1,a+DivisorSigma[0,n+1]}; Transpose[NestList[nxt,{0,1},50]][[2]] (* Harvey P. Dale, Oct 15 2012 *)
Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Subtract@@@Reverse/@Subsets[#,{2}]]&]],{n,0,10}] (* Gus Wiseman, Jun 07 2019 *)

vector(100, n, n--; sum(k=1, n, n\k) + 1) \\ Altug Alkan, Oct 15 2015

a(n) = A051336(n+1) - A051336(n) = a(n-1) + A000005(n) = A006218(n)+1.
G.f.: (1-x)^(-1) * (1 + Sum_{j>=1} x^j/(1-x^j)). - Robert Israel, Oct 15 2015
a(n) = Sum_{i=1..n+1} ceiling((n+1)/(i+1)). - Wesley Ivan Hurt, Sep 15 2017

A295370 Number of permutations of [n] avoiding three consecutive terms in arithmetic progression.

Original entry on oeis.org

1, 1, 2, 4, 18, 80, 482, 3280, 26244, 231148, 2320130, 25238348, 302834694, 3909539452, 54761642704, 816758411516, 13076340876500, 221396129723368, 3985720881222850, 75503196628737920, 1510373288335622576, 31634502738658957588, 696162960370556156224, 15978760340940405262668

Offset: 0

Alois P. Heinz, Nov 20 2017

nonn

These are permutations of n whose second-differences are nonzero. - Gus Wiseman, Jun 03 2019

			a(3) = 4: 132, 213, 231, 312.
a(4) = 18: 1243, 1324, 1342, 1423, 2134, 2143, 2314, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4132, 4213, 4231, 4312.

Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Column k=0 of A295390.
Cf. A003407, A174080, A238423, A238424, A338765.
Cf. A049988, A175342, A279945, A325545, A325849, A325850, A325851, A325874, A325875.

b:= proc(s, j, k) option remember; `if`(s={}, 1,
      add(`if`(k=0 or 2*j<>i+k, b(s minus {i}, i,
          `if`(2*i-j in s, j, 0)), 0), i=s))
    end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..12);

Table[Length[Select[Permutations[Range[n]],!MemberQ[Differences[#,2],0]&]],{n,0,5}] (* Gus Wiseman, Jun 03 2019 *)
b[s_, j_, k_] := b[s, j, k] = If[s == {}, 1, Sum[If[k == 0 || 2*j != i + k, b[s~Complement~{i}, i, If[MemberQ[s, 2*i - j ], j, 0]], 0], {i, s}]];
a[n_] := a[n] = b[Range[n], 0, 0];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Nov 20 2023, after Alois P. Heinz *)

a(22)-a(23) from Vaclav Kotesovec, Mar 22 2022

A325874 Number of integer partitions of n whose differences of all degrees > 1 are nonzero.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 6, 8, 12, 13, 19, 24, 26, 33, 45, 52, 66, 78, 92, 113, 129, 160, 192, 231, 268, 305, 361, 436, 501, 591, 665, 783, 897, 1071, 1228, 1361, 1593, 1834, 2101, 2452, 2685, 3129, 3526, 4067, 4568, 5189, 5868, 6655, 7565, 8468, 9400

Offset: 0

Gus Wiseman, Jun 02 2019

nonn

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (6,3,1) are (-3,-2). The zeroth differences are the sequence itself, while k-th differences for k > 0 are the differences of the (k-1)-th differences. If m is the length of the sequence, its differences of all degrees are the union of the zeroth through m-th differences.

The case for all degrees including 1 is A325852.

			The a(1) = 1 through a(9) = 13 partitions:
  (1)  (2)   (3)   (4)    (5)    (6)     (7)    (8)     (9)
       (11)  (21)  (22)   (32)   (33)    (43)   (44)    (54)
                   (31)   (41)   (42)    (52)   (53)    (63)
                   (211)  (221)  (51)    (61)   (62)    (72)
                          (311)  (411)   (322)  (71)    (81)
                                 (2211)  (331)  (332)   (441)
                                         (421)  (422)   (522)
                                         (511)  (431)   (621)
                                                (521)   (711)
                                                (611)   (4221)
                                                (3221)  (4311)
                                                (3311)  (5211)
                                                        (32211)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..220
Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts

Cf. A049988, A238423, A325325, A325468, A325545, A325849, A325850, A325851, A325852, A325875, A325876.

Table[Length[Select[IntegerPartitions[n],!MemberQ[Union@@Table[Differences[#,i],{i,2,Length[#]}],0]&]],{n,0,30}]

A325849 Number of strict compositions of n with no three consecutive parts in arithmetic progression.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 9, 13, 19, 23, 51, 57, 91, 117, 179, 283, 381, 531, 737, 1017, 1335, 2259, 2745, 3983, 5289, 7367, 9413, 13155, 19461, 25129, 33997, 45633, 61225, 80481, 107091, 137475, 205243, 253997, 345527, 447003, 604919, 768331, 1026167, 1299227

Offset: 0

Gus Wiseman, May 31 2019

nonn

A composition of n is a finite sequence of positive integers with sum n. a(n) is the number of strict compositions of n with no two of their adjacent first-differences equal, or with no 0's in their second-differences.

			The a(1) = 1 through a(8) = 19 compositions:
  (1)  (2)  (3)   (4)   (5)   (6)    (7)    (8)
            (12)  (13)  (14)  (15)   (16)   (17)
            (21)  (31)  (23)  (24)   (25)   (26)
                        (32)  (42)   (34)   (35)
                        (41)  (51)   (43)   (53)
                              (132)  (52)   (62)
                              (213)  (61)   (71)
                              (231)  (124)  (125)
                              (312)  (142)  (134)
                                     (214)  (143)
                                     (241)  (152)
                                     (412)  (215)
                                     (421)  (251)
                                            (314)
                                            (341)
                                            (413)
                                            (431)
                                            (512)
                                            (521)

Wikipedia, Arithmetic progression

The non-strict case is A238423.

Cf. A007862, A049988, A175342, A279945, A295370, A325545, A325874, A325875.

Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&],!MemberQ[Differences[#,2],0]&]],{n,0,30}]

A325852 Number of (strict) integer partitions of n whose differences of all degrees are nonzero.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 5, 6, 6, 9, 11, 11, 15, 19, 19, 26, 31, 31, 41, 49, 53, 62, 75, 81, 97, 112, 124, 145, 171, 175, 215, 244, 274, 307, 344, 388, 446, 497, 561, 599, 700, 779, 881, 981, 1054, 1184, 1340, 1500, 1669, 1767, 2031, 2237, 2486, 2765, 2946, 3300

Offset: 0

Gus Wiseman, May 31 2019

nonn

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (6,3,1) are (-3,-2). The zeroth differences are the sequence itself, while k-th differences for k > 0 are the differences of the (k-1)-th differences. The differences of all degrees of a sequence are the union of its zeroth through m-th differences, where m is the length of the sequence.

			The a(1) = 1 through a(11) = 11 partitions (A = 10, B = 11):
  (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)    (9)    (A)    (B)
            (21)  (31)  (32)  (42)  (43)   (53)   (54)   (64)   (65)
                        (41)  (51)  (52)   (62)   (63)   (73)   (74)
                                    (61)   (71)   (72)   (82)   (83)
                                    (421)  (431)  (81)   (91)   (92)
                                           (521)  (621)  (532)  (A1)
                                                         (541)  (542)
                                                         (631)  (632)
                                                         (721)  (641)
                                                                (731)
                                                                (821)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..250

The case for only degrees > 1 is A325874.

Cf. A049988, A175342, A238423, A279945, A295370, A325328, A325468, A325545, A325850, A325851, A325875.

Table[Length[Select[IntegerPartitions[n],!MemberQ[Union@@Table[Differences[#,i],{i,Length[#]}],0]&]],{n,0,30}]

A325850 Number of permutations of {1..n} whose differences of all degrees are nonzero.

Original entry on oeis.org

1, 1, 2, 4, 18, 72, 446, 2804, 21560, 184364, 1788514

Offset: 0

Gus Wiseman, May 31 2019

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (6,3,1) are (-3,-2). The zeroth differences are the sequence itself, while k-th differences for k > 0 are the differences of the (k-1)-th differences. The differences of all degrees of a sequence are the union of its zeroth through m-th differences, where m is the length of the sequence.

			The a(1) = 1 through a(4) = 18 permutations:
  (1)  (12)  (132)  (1243)
       (21)  (213)  (1324)
             (231)  (1342)
             (312)  (1423)
                    (2134)
                    (2143)
                    (2314)
                    (2413)
                    (2431)
                    (3124)
                    (3142)
                    (3241)
                    (3412)
                    (3421)
                    (4132)
                    (4213)
                    (4231)
                    (4312)

Dominated by A295370, the case for only differences of degree 2.

Cf. A049988, A175342, A238423, A279945, A325545, A325851, A325852, A325874, A325875.

Table[Length[Select[Permutations[Range[n]],!MemberQ[Union@@Table[Differences[#,i],{i,Length[#]}],0]&]],{n,0,5}]

A325851 Number of (strict) compositions of n whose differences of all degrees are nonzero.

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 12, 21, 35, 58, 102, 171, 284, 485, 819, 1355, 2301, 3884, 6528, 10983, 18380, 30824, 51851

Offset: 0

Gus Wiseman, May 31 2019

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (6,3,1) are (-3,-2). The zeroth differences are the sequence itself, while k-th differences for k > 0 are the differences of the (k-1)-th differences. The differences of all degrees of a sequence are the union of its zeroth through m-th differences, where m is the length of the sequence.

			The a(1) = 1 through a(7) = 21 compositions:
  (1)  (2)  (3)   (4)    (5)    (6)     (7)
            (12)  (13)   (14)   (15)    (16)
            (21)  (31)   (23)   (24)    (25)
                  (121)  (32)   (42)    (34)
                         (41)   (51)    (43)
                         (131)  (132)   (52)
                         (212)  (141)   (61)
                                (213)   (124)
                                (231)   (142)
                                (312)   (151)
                                (1212)  (214)
                                (2121)  (232)
                                        (241)
                                        (313)
                                        (412)
                                        (421)
                                        (1213)
                                        (1312)
                                        (2131)
                                        (3121)
                                        (12121)

The case for only degrees > 1 is A325875.

Cf. A049988, A175342, A238423, A295370, A325328, A325545, A325850, A325852, A325874.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Union@@Table[Differences[#,i],{i,Length[#]}],0]&]],{n,0,10}]

A325875 Number of compositions of n whose differences of all degrees > 1 are nonzero.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 20, 38, 69, 129, 222, 407, 726, 1313, 2318, 4146, 7432, 13296, 23759, 42458, 75714

Offset: 0

Gus Wiseman, Jun 02 2019

The differences of a sequence are defined as if the sequence were increasing, so for example the differences of (6,3,1) are (-3,-2). The zeroth differences are the sequence itself, while k-th differences for k > 0 are the differences of the (k-1)-th differences. If m is the length of the sequence, its differences of all degrees are the union of the zeroth through m-th differences.
A composition of n is a finite sequence of positive integers with sum n.
The case for all degrees including 1 is A325851.

			The a(1) = 1 through a(6) = 20 compositions:
  (1)  (2)   (3)   (4)    (5)     (6)
       (11)  (12)  (13)   (14)    (15)
             (21)  (22)   (23)    (24)
                   (31)   (32)    (33)
                   (112)  (41)    (42)
                   (121)  (113)   (51)
                   (211)  (122)   (114)
                          (131)   (132)
                          (212)   (141)
                          (221)   (213)
                          (311)   (231)
                          (1121)  (312)
                          (1211)  (411)
                                  (1122)
                                  (1131)
                                  (1212)
                                  (1311)
                                  (2121)
                                  (2211)
                                  (11211)

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts

Cf. A049988, A238423, A325325, A325468, A325545, A325849, A325850, A325851, A325852, A325874, A325876.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Union@@Table[Differences[#,i],{i,2,Length[#]}],0]&]],{n,0,10}]

A238569 Number of compositions of n avoiding any 3-term arithmetic progression.

Original entry on oeis.org

1, 1, 2, 3, 7, 11, 19, 28, 53, 83, 140, 201, 332, 486, 775, 1207, 1716, 2498, 3870, 5623, 8020, 11276, 17168, 23323, 34746, 46141, 64879, 90467, 127971, 176201, 242869, 333508, 456683, 606403, 844818, 1125922, 1496466, 2005446, 2737912, 3543506, 4824442

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 28 2014

nonn

			a(3) = 3: [1,2], [2,1], [3].
a(4) = 7: [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1], [4].
a(5) = 11: [1,1,3], [1,2,2], [1,3,1], [1,4], [2,1,2], [2,2,1], [2,3], [3,1,1], [3,2], [4,1], [5].
a(6) = 19: [1,1,2,2], [1,1,4], [1,2,1,2], [1,2,2,1], [1,3,2], [1,4,1], [1,5], [2,1,1,2], [2,1,2,1], [2,1,3], [2,2,1,1], [2,3,1], [2,4], [3,1,2], [3,3], [4,1,1], [4,2], [5,1], [6].

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..85
Index entries related to non-averaging sequences

Cf. A003407 (the same for permutations).
Cf. A178932 (the same for strict partitions).
Cf. A238423 (the same for consecutive 3-term arithmetic progressions).
Cf. A238571 (the same for partitions).
Cf. A238686.

b:= proc(n, i, o) option remember; `if`(n=0, 1, add(
      `if`(j in o, 0, b(n-j, i union {j}, select(y->02*j-x, i)))), j=1..n))
    end:
a:= n-> b(n, {}, {}):
seq(a(n), n=0..30);

b[n_, i_List, o_List] := b[n, i, o] = If[n == 0, 1, Sum[If[MemberQ[o, j], 0, b[n - j, i  ~Union~ {j}, Select[o ~Union~ (2j-i), 0<# && # <= n &]]], {j, 1, n}]]; a[n_] := b[n, {}, {}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 06 2015, translated from Maple *)

cp's OEIS Frontend

A238424 Number of partitions of n without three consecutive parts in arithmetic progression.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A054519 Number of increasing arithmetic progressions of nonnegative integers ending in n, including those of length 1 or 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A295370 Number of permutations of [n] avoiding three consecutive terms in arithmetic progression.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A325874 Number of integer partitions of n whose differences of all degrees > 1 are nonzero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325849 Number of strict compositions of n with no three consecutive parts in arithmetic progression.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325852 Number of (strict) integer partitions of n whose differences of all degrees are nonzero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325850 Number of permutations of {1..n} whose differences of all degrees are nonzero.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325851 Number of (strict) compositions of n whose differences of all degrees are nonzero.

Views

Author

Keywords