A295370 -id:A295370 - 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 *)

A335434 Number of separable factorizations of n into factors > 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 6, 1, 2, 2, 4, 1, 5, 1, 5, 2, 2, 2, 8, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 10, 1, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 11, 1, 2, 4, 6, 2, 5, 1, 4, 2, 5, 1, 15, 1, 2, 4, 4, 2, 5, 1, 10, 3, 2, 1, 11, 2

Offset: 1

Gus Wiseman, Jul 03 2020

nonn

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

			The a(n) factorizations for n = 2, 6, 16, 12, 30, 24, 36, 48, 60:
  2  6    16     12     30     24     36       48       60
     2*3  2*8    2*6    5*6    3*8    4*9      6*8      2*30
          2*2*4  3*4    2*15   4*6    2*18     2*24     3*20
                 2*2*3  3*10   2*12   3*12     3*16     4*15
                        2*3*5  2*2*6  2*2*9    4*12     5*12
                               2*3*4  2*3*6    2*3*8    6*10
                                      3*3*4    2*4*6    2*5*6
                                      2*2*3*3  3*4*4    3*4*5
                                               2*2*12   2*2*15
                                               2*2*3*4  2*3*10
                                                        2*2*3*5

The version for partitions is A325534.
The inseparable version is A333487.
The version for multisets with prescribed multiplicities is A335127.
Factorizations are A001055.
Anti-run compositions are A003242.
Inseparable partitions are A325535.
Anti-runs are ranked by A333489.
Separable partitions are ranked by A335433.
Inseparable partitions are ranked by A335448.
Anti-run permutations of prime indices are A335452.
Cf. A106351, A292884, A295370, A333628, A333755, A335463, A335125, A335126, A335407, A335457, A335474, A335516, A335838.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],Select[Permutations[#],!MatchQ[#,{_,x_,x_,_}]&]!={}&]],{n,100}]

A333487(n) + a(n) = A001055(n).

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

A333487 Number of inseparable factorizations of n into factors > 1.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Jul 01 2020

nonn

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

			The a(n) factorizations for n = 4, 16, 96, 144, 64, 192:
  2*2  4*4      2*2*2*12     12*12        8*8          3*4*4*4
       2*2*2*2  2*2*2*2*6    2*2*2*18     4*4*4        2*2*2*24
                2*2*2*2*2*3  2*2*2*2*9    2*2*2*8      2*2*2*2*12
                             2*2*2*2*3*3  2*2*2*2*4    2*2*2*2*2*6
                                          2*2*2*2*2*2  2*2*2*2*3*4
                                                       2*2*2*2*2*2*3

The version for partitions is A325535.
The version for multisets with prescribed multiplicities is A335126.
The separable version is A335434.
Anti-run compositions are A003242.
Anti-runs are ranked by A333489.
Separable partitions are ranked by A335433.
Inseparable partitions are ranked by A335448.
Anti-run permutations of prime indices are A335452.
Patterns contiguously matched by compositions are A335457.
Cf. A106351, A292884, A295370, A333628, A333755, A335463, A335125, A335127, A335407, A335474, A335516, A335838.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],Select[Permutations[#],!MatchQ[#,{_,x_,x_,_}]&]=={}&]],{n,100}]

a(n) + A335434(n) = A001055(n).

A238423 Number of compositions of n avoiding three consecutive parts in arithmetic progression.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 22, 42, 81, 149, 278, 516, 971, 1812, 3374, 6297, 11770, 21970, 41002, 76523, 142901, 266779, 497957, 929563, 1735418, 3239698, 6047738, 11289791, 21076118, 39344992, 73448769, 137113953, 255965109, 477835991, 892023121, 1665227859

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 26 2014

nonn

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

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

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..400
Wikipedia, Arithmetic progression

Cf. A238424 (equivalent for partitions).
Cf. A238569 (equivalent for any 3-term arithmetic progression).
Cf. A238686, A295370.
Cf. A007862, A049988, A175342, A325545, A325849, A325851, A325874, A325875.

# b(n, r, d): number of compositions of n where the leftmost part j
#             does not have distance d to the recent part r
b:= proc(n, r, d) option remember; `if`(n=0, 1,
      add(`if`(j=r+d, 0, b(n-j, j, j-r)), j=1..n))
    end:
a:= n-> b(n, infinity, 0):
seq(a(n), n=0..45);

b[n_, r_, d_] := b[n, r, d] = If[n == 0, 1, Sum[If[j == r + d, 0, b[n - j, j, j - r]], {j, 1, n}]]; a[n_] := b[n, Infinity, 0]; Table[a[n], {n, 0, 45}] (* Jean-François Alcover, Nov 06 2014, after Maple *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Differences[#,2],0]&]],{n,0,10}] (* Gus Wiseman, Jun 03 2019 *)

a(n) ~ c * d^n, where d = 1.866800016014240677813344121155900699..., c = 0.540817940878009616510727217687704495... - Vaclav Kotesovec, May 01 2014

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}]

A174080 Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.

Original entry on oeis.org

1, 1, 2, 5, 21, 100, 597, 4113, 32842, 292379, 2925367, 31983248, 383514347, 4966286235, 69508102006, 1039315462467, 16627618496319, 282023014602100, 5075216962675445, 96263599713301975, 1925002914124917950

Offset: 0

Isaac Lambert, Mar 15 2010

			For n=4, there are 4!-a(4)=3 permutations with some consecutive triple i,i+d,i+2d. Note for n=4, only d=1 applies. Hence those three permutations are (0,1,2,3), (1,2,3,0), and (3,0,1,2). Since here only d=1, this is the same value of a(4) in A002628.

Cf. A002628, A174072, A174081, A174082, A174083, A295370.

b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
      `if`(x=0 or xy-j,
         b(s minus {j}, y, j), 0), j=s))
    end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..14);  # Alois P. Heinz, Apr 13 2021

b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[If[x == 0 || x < y || x-y != y-j, b[s~Complement~{j}, y, j], 0], {j, s}]];
a[n_] := b[Range[n], 0, 0];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Sep 27 2022, after Alois P. Heinz *)

a(0)-a(3) and a(10)-a(20) from Alois P. Heinz, Apr 13 2021

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

A335434 Number of separable factorizations of n into factors > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

A333487 Number of inseparable factorizations of n into factors > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A238423 Number of compositions of n avoiding three consecutive parts in arithmetic progression.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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