A178470 -id:A178470 - cp's OEIS frontend

A328188 Number of strict integer partitions of n with all pairs of consecutive parts relatively prime.

1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 12, 15, 15, 19, 23, 25, 30, 35, 39, 47, 52, 58, 65, 75, 86, 95, 109, 124, 144, 165, 181, 203, 221, 249, 285, 316, 352, 392, 438, 484, 538, 599, 666, 737, 813, 899, 992, 1102, 1215, 1335, 1472, 1621, 1776, 1946, 2137, 2336

Offset: 0

Gus Wiseman, Oct 13 2019

nonn

			The a(1) = 1 through a(15) = 15 partitions (A..F = 10..15):
  1  2  3   4   5   6    7   8    9    A     B     C    D     E     F
        21  31  32  51   43  53   54   73    65    75   76    95    87
                41  321  52  71   72   91    74    B1   85    B3    B4
                         61  431  81   532   83    543  94    D1    D2
                             521  432  541   92    651  A3    653   E1
                                  531  721   A1    732  B2    743   654
                                       4321  731   741  C1    752   753
                                             5321  831  652   761   852
                                                   921  751   851   951
                                                        832   941   A32
                                                        5431  A31   B31
                                                        7321  B21   6531
                                                              5432  7431
                                                              6521  7521
                                                              8321  54321

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The case of compositions is A167606.
The non-strict case is A328172.
The Heinz numbers of these partitions are given by A328335.
Partitions with no pairs of consecutive parts relatively prime are A328187.
Cf. A000837, A018783, A178470, A328028, A328170, A328171, A328187, A328220.

b:= proc(n, i, s) option remember; `if`(i*(i+1)/2 igcd(i, j)=1, s), b(n-i, min(n-i, i-1),
           numtheory[factorset](i)), 0)+b(n, i-1, s)))
    end:
a:= n-> b(n$2, {}):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 13 2019

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]>1]&]],{n,0,30}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[i(i + 1)/2 < n, 0, If[n == 0, 1, If[AllTrue[s,  GCD[i, #] == 1&], b[n - i, Min[n - i, i - 1], FactorInteger[i][[All, 1]]], 0] + b[n, i - 1, s]]];
a[n_] := b[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

A328508 Number of compositions of n with no part divisible by the next or the prior.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 6, 4, 8, 14, 14, 27, 30, 55, 69, 97, 155, 200, 312, 421, 630, 893, 1260, 1864, 2600, 3813, 5395, 7801, 11196, 15971, 23126, 32917, 47514, 67993, 97670, 140334, 200913, 289147, 414119, 595109, 853751, 1225086, 1759405, 2523151, 3623984, 5198759

Offset: 0

Gus Wiseman, Oct 17 2019

nonn

			The a(1) = 1 through a(11) = 14 compositions (A = 10, B = 11):
  (1)  (2)  (3)  (4)  (5)   (6)  (7)    (8)    (9)    (A)     (B)
                      (23)       (25)   (35)   (27)   (37)    (29)
                      (32)       (34)   (53)   (45)   (46)    (38)
                                 (43)   (323)  (54)   (64)    (47)
                                 (52)          (72)   (73)    (56)
                                 (232)         (234)  (235)   (65)
                                               (252)  (253)   (74)
                                               (432)  (325)   (83)
                                                      (343)   (92)
                                                      (352)   (254)
                                                      (523)   (272)
                                                      (532)   (353)
                                                      (2323)  (434)
                                                      (3232)  (452)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The case of partitions is A328171.
If we only forbid parts to be divisible by the next, we get A328460.
Compositions with each part relatively prime to the next are A167606.
Compositions with no part relatively prime to the next are A178470.
Cf. A328026, A328028, A328161, A328172, A328189.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;Divisible[y,x]||Divisible[x,y]]&]],{n,0,10}]

seq(n)={my(r=matid(n)); for(k=1, n, for(i=1, k-1, r[i,k]=sum(j=1, k-i, if(i%j && j%i, r[j, k-i])))); concat([1], vecsum(Col(r)))} \\ Andrew Howroyd, Oct 19 2019

Terms a(26) and beyond from Andrew Howroyd, Oct 19 2019

A328609 Number of compositions of n whose circularly adjacent parts are relatively prime.

Original entry on oeis.org

1, 1, 1, 3, 6, 12, 23, 42, 81, 150, 284, 534, 1004, 1882, 3532, 6630, 12459, 23406, 43951, 82537, 154998, 291087, 546673, 1026686, 1928117, 3621016, 6800299, 12771085, 23984328, 45042958, 84591338, 158863806, 298348612, 560303341, 1052258401, 1976157509

Offset: 0

Gus Wiseman, Oct 26 2019

nonn

Circularity means the last part is followed by the first.

			The a(1) = 1 through a(6) = 23 compositions:
  (1)  (11)  (12)   (13)    (14)     (15)
             (21)   (31)    (23)     (51)
             (111)  (112)   (32)     (114)
                    (121)   (41)     (123)
                    (211)   (113)    (132)
                    (1111)  (131)    (141)
                            (311)    (213)
                            (1112)   (231)
                            (1121)   (312)
                            (1211)   (321)
                            (2111)   (411)
                            (11111)  (1113)
                                     (1131)
                                     (1212)
                                     (1311)
                                     (2121)
                                     (3111)
                                     (11112)
                                     (11121)
                                     (11211)
                                     (12111)
                                     (21111)
                                     (111111)

Andrew Howroyd, Table of n, a(n) for n = 0..200

The necklace version is A328597 or A318728 (with singletons).
The aperiodic version is A328670.
The Lyndon word version is A318745.
The version with singletons is A318748.
The non-circular version is A167606.
Relatively prime compositions are A000740.
Compositions with no part circularly followed by a divisor are A328598.
Cf. A008965, A178470, A318726, A325680, A328172, A328335, A328599, A328600.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],And@@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q, ]}
seq(n)={concat([1], sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019

a(n > 1) = A318748(n) - 1.

A357185 Numbers k such that the k-th composition in standard order has the same length as the absolute value of its alternating sum.

Original entry on oeis.org

0, 1, 9, 12, 19, 22, 28, 34, 40, 69, 74, 84, 97, 104, 132, 135, 141, 144, 153, 177, 195, 198, 204, 216, 225, 240, 265, 271, 274, 283, 286, 292, 307, 310, 316, 321, 328, 355, 358, 364, 376, 386, 400, 451, 454, 460, 472, 496, 520, 523, 526, 533, 538, 544, 553

Offset: 1

Gus Wiseman, Sep 28 2022

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

			The sequence together with the corresponding compositions begins:
    0: ()
    1: (1)
    9: (3,1)
   12: (1,3)
   19: (3,1,1)
   22: (2,1,2)
   28: (1,1,3)
   34: (4,2)
   40: (2,4)
   69: (4,2,1)
   74: (3,2,2)
   84: (2,2,3)
   97: (1,5,1)
  104: (1,2,4)
  132: (5,3)
  135: (5,1,1,1)
  141: (4,1,2,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
For sum equal to twice alternating sum we have A348614, counted by A262977.
For product equal to sum we have A335404, counted by A335405.
These compositions are counted by A357183.
This is the absolute value version of A357184, counted by A357183.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A025047 counts alternating compositions, ranked by A345167.
A032020 counts strict compositions, ranked by A233564.
A124754 gives alternating sums of standard compositions.
A238279 counts compositions by sum and number of maximal runs.
A357136 counts compositions by alternating sum.
Cf. A000120, A070939, A114220, A114901, A178470, A242882, A262046, A301987.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Select[Range[0,100],Length[stc[#]]==Abs[ats[stc[#]]]&]

A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 2, 69, 3, 111, 24, 190, 13, 384, 31, 646, 102, 1212, 113, 2348, 227, 4254, 613, 7993, 976, 15459, 1915, 28825, 4357, 54988, 7868, 105826, 15760, 201115, 33376, 385590, 63974, 744446, 128224, 1428047, 262914, 2754037

Offset: 1

Gus Wiseman, Oct 25 2019

nonn

A necklace composition of n (A008965) is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

Circularity means the last part is followed by the first.

			The a(2) = 1 through a(10) = 8 necklace compositions:
  (2)  (3)  (4)    (5)  (6)      (7)  (8)        (9)      (10)
            (2,2)       (2,4)         (2,6)      (3,6)    (2,8)
                        (3,3)         (4,4)      (3,3,3)  (4,6)
                        (2,2,2)       (2,2,4)             (5,5)
                                      (2,2,2,2)           (2,2,6)
                                                          (2,4,4)
                                                          (2,2,2,4)
                                                          (2,2,2,2,2)
The a(19) = 3 necklace compositions are: (19), (3,6,4,6), (2,2,6,3,6).

Andrew Howroyd, Table of n, a(n) for n = 1..200

The non-necklace, non-circular version is A178470.
The version for indivisibility (rather than co-primality) is A328600.
The circularly coprime (as opposed to anti-coprime) version is A328597.
Partitions with no consecutive parts relatively prime are A328187.
Cf. A000031, A000740, A008965, A032153, A318728, A318729, A318748, A328172, A328188, A328220, A328335, A328336, A328601, A328609.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@Not/@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q,]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->gcd(i,j)<>1))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019

Terms a(26) and beyond from Andrew Howroyd, Oct 26 2019

A178471 Triangle where T(n,k) is the number of compositions of n where no pair of consecutive part sizes is relative prime, starting with a part of size k.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 2, 0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 8, 0, 4, 1, 2, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 16, 4, 8, 0, 5, 0, 2, 1, 1, 0, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 33, 1, 16, 0, 8, 1, 4, 0, 2, 0, 1, 0

Offset: 1

Franklin T. Adams-Watters, May 28 2010

			The array starts:
1
0 1
0 0 1
0 1 0 1
0 0 0 0 1
0 2 1 1 0 1

Cf. A178470 (row sums).

am(n)=local(r);r=matrix(n,n,i,j,i==j);for(i=2,n,for(j=1,i-1,for(k=1,j,if(gcd(i-j,k)>1,r[i,i-j]+=r[j,k]))));r

cp's OEIS Frontend

A328188 Number of strict integer partitions of n with all pairs of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A328508 Number of compositions of n with no part divisible by the next or the prior.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A328609 Number of compositions of n whose circularly adjacent parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A357185 Numbers k such that the k-th composition in standard order has the same length as the absolute value of its alternating sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A178471 Triangle where T(n,k) is the number of compositions of n where no pair of consecutive part sizes is relative prime, starting with a part of size k.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI