A000837 -id:A000837 - cp's OEIS frontend

A328170 Number of integer partitions of n whose parts minus 1 are relatively prime.

0, 0, 1, 1, 2, 3, 5, 8, 12, 18, 27, 38, 53, 74, 102, 137, 184, 241, 317, 413, 536, 687, 880, 1112, 1405, 1765, 2215, 2755, 3424, 4229, 5216, 6402, 7847, 9572, 11662, 14148, 17139, 20688, 24940, 29971, 35969, 43044, 51438, 61311, 72985, 86678, 102807, 121675

Offset: 0

Gus Wiseman, Oct 09 2019

nonn

A partition is relatively prime if the GCD of its parts is 1. Zeros are ignored when computing GCD, and the empty set has GCD 0.

			The a(2) = 1 through a(9) = 18 partitions:
  (2)  (21)  (22)   (32)    (42)     (43)      (62)       (54)
             (211)  (221)   (222)    (52)      (332)      (63)
                    (2111)  (321)    (322)     (422)      (72)
                            (2211)   (421)     (431)      (432)
                            (21111)  (2221)    (521)      (522)
                                     (3211)    (2222)     (621)
                                     (22111)   (3221)     (3222)
                                     (211111)  (4211)     (3321)
                                               (22211)    (4221)
                                               (32111)    (4311)
                                               (221111)   (5211)
                                               (2111111)  (22221)
                                                          (32211)
                                                          (42111)
                                                          (222111)
                                                          (321111)
                                                          (2211111)
                                                          (21111111)

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

The Heinz numbers of these partitions are given by A328168.
Partitions whose parts are relatively prime are A000837.
Partitions whose parts plus 1 are relatively prime are A318980.
The GCD of the prime indices of n, all minus 1, is A328167(n).
Cf. A007359, A018783, A258409, A289509, A328163, A328164.

Table[Length[Select[IntegerPartitions[n],GCD@@(#-1)==1&]],{n,0,30}]

seq(n)=Vec(sum(d=1, n-1, moebius(d)*(-1/(1-x) + 1/prod(k=0, n\d, 1 - x*x^(k*d) + O(x*x^n)))), -(n+1)) \\ Andrew Howroyd, Oct 17 2019

G.f.: Sum_{d>=1} mu(d)*(-1/(1-x) + 1/(Prod_{k>=0} 1 - x^(k*d + 1))). - Andrew Howroyd, Oct 17 2019

A334965 Numbers with strictly increasing prime multiplicities.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 18, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 50, 53, 54, 59, 61, 64, 67, 71, 73, 75, 79, 81, 83, 89, 97, 98, 101, 103, 107, 108, 109, 113, 121, 125, 127, 128, 131, 137, 139, 147, 149, 151, 157, 162, 163, 167, 169

Offset: 1

Gus Wiseman, May 18 2020

nonn

First differs from A329131 in lacking 150.

Also numbers whose unsorted prime signature is strictly increasing.

			The sequence of terms together with their prime indices begins:
    1: {}            25: {3,3}           64: {1,1,1,1,1,1}
    2: {1}           27: {2,2,2}         67: {19}
    3: {2}           29: {10}            71: {20}
    4: {1,1}         31: {11}            73: {21}
    5: {3}           32: {1,1,1,1,1}     75: {2,3,3}
    7: {4}           37: {12}            79: {22}
    8: {1,1,1}       41: {13}            81: {2,2,2,2}
    9: {2,2}         43: {14}            83: {23}
   11: {5}           47: {15}            89: {24}
   13: {6}           49: {4,4}           97: {25}
   16: {1,1,1,1}     50: {1,3,3}         98: {1,4,4}
   17: {7}           53: {16}           101: {26}
   18: {1,2,2}       54: {1,2,2,2}      103: {27}
   19: {8}           59: {17}           107: {28}
   23: {9}           61: {18}           108: {1,1,2,2,2}

These are the Heinz numbers of the partitions counted by A100471.
Partitions with strictly decreasing run-lengths are A100881.
Partitions with weakly decreasing run-lengths are A100882.
Partitions with weakly increasing run-lengths are A100883.
The weakly decreasing version is A242031.
The weakly increasing version is A304678.
The strictly decreasing version is A304686.
Compositions with strictly increasing or decreasing run-lengths are A333191.
Cf. A000837, A032020, A098859, A100883, A329744, A332835, A333147, A333190.

Select[Range[100],Less@@Last/@FactorInteger[#]&]

A337452 Number of relatively prime strict integer partitions of n with no 1's.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 2, 1, 3, 2, 6, 3, 9, 7, 11, 11, 20, 15, 28, 24, 35, 36, 55, 47, 73, 71, 95, 96, 136, 123, 180, 177, 226, 235, 305, 299, 403, 406, 503, 523, 668, 662, 852, 873, 1052, 1115, 1370, 1391, 1720, 1784, 2125, 2252, 2701, 2786, 3348, 3520, 4116

Offset: 0

Gus Wiseman, Aug 31 2020

nonn

			The a(5) = 1 through a(16) = 11 partitions (A = 10, B = 11, C = 12, D = 13):
  32  43  53  54   73   65   75   76   95    87    97
      52      72   532  74   543  85   B3    B4    B5
              432       83   732  94   653   D2    D3
                        92        A3   743   654   754
                        542       B2   752   753   763
                        632       643  932   762   853
                                  652  5432  843   943
                                  742        852   952
                                  832        942   B32
                                             A32   6532
                                             6432  7432

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

A078374 is the version allowing 1's.
A302698 is the non-strict version.
A332004 is the ordered version allowing 1's.
A337450 is the ordered non-strict version.
A337451 is the ordered version.
A337485 is the pairwise coprime version.
A000837 counts relatively prime partitions.
A078374 counts relatively prime strict partitions.
A002865 counts partitions with no 1's.
A212804 counts compositions with no 1's.
A291166 appears to rank relatively prime compositions.
A337561 counts pairwise coprime strict compositions.
Cf. A007359, A101268, A289509, A337485, A337563.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MemberQ[#,1]&&GCD@@#==1&]],{n,0,15}]

A366842 Number of integer partitions of n whose odd parts have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 1, 4, 1, 8, 3, 13, 6, 21, 10, 36, 15, 53, 28, 80, 41, 122, 63, 174, 97, 250, 140, 359, 201, 496, 299, 685, 410, 949, 575, 1284, 804, 1726, 1093, 2327, 1482, 3076, 2023, 4060, 2684, 5358, 3572, 6970, 4745, 9050, 6221, 11734, 8115, 15060, 10609

Offset: 0

Gus Wiseman, Oct 28 2023

nonn

			The a(3) = 1 through a(11) = 13 partitions:
  (3)  .  (5)    (3,3)  (7)      (3,3,2)  (9)        (5,5)      (11)
          (3,2)         (4,3)             (5,4)      (4,3,3)    (6,5)
                        (5,2)             (6,3)      (3,3,2,2)  (7,4)
                        (3,2,2)           (7,2)                 (8,3)
                                          (3,3,3)               (9,2)
                                          (4,3,2)               (4,4,3)
                                          (5,2,2)               (5,4,2)
                                          (3,2,2,2)             (6,3,2)
                                                                (7,2,2)
                                                                (3,3,3,2)
                                                                (4,3,2,2)
                                                                (5,2,2,2)
                                                                (3,2,2,2,2)

This is the odd case of A018783, complement A000837.
The even version is A047967.
The complement is counted by A366850, ranks A366846.
A000041 counts integer partitions, strict A000009.
A000740 counts relatively prime compositions.
A113685 counts partitions by sum of odds, stat A366528, w/o zeros A365067.
A168532 counts partitions by gcd.
A239261 counts partitions with (sum of odd parts) = (sum of even parts).
A289508 gives gcd of prime indices, positions of ones A289509.
Cf. A007359, A051424, A055922, A066208, A078374, A087436, A116598, A337485, A366843, A366844, A366845.

Table[Length[Select[IntegerPartitions[n], GCD@@Select[#,OddQ]>1&]], {n,0,30}]

from math import gcd
from sympy.utilities.iterables import partitions
def A366842(n): return sum(1 for p in partitions(n) if gcd(*(q for q in p if q&1))>1) # Chai Wah Wu, Oct 28 2023

A366843 Number of integer partitions of n into odd, relatively prime parts.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 3, 4, 6, 6, 9, 11, 13, 17, 21, 23, 32, 37, 42, 53, 62, 70, 88, 103, 116, 139, 164, 184, 220, 255, 283, 339, 390, 435, 511, 578, 653, 759, 863, 963, 1107, 1259, 1401, 1609, 1814, 2015, 2303, 2589, 2878, 3259, 3648, 4058, 4580, 5119, 5672, 6364

Offset: 0

Gus Wiseman, Oct 28 2023

nonn

			The a(1) = 1 through a(8) = 6 partitions:
  (1)  (11)  (111)  (31)    (311)    (51)      (331)      (53)
                    (1111)  (11111)  (3111)    (511)      (71)
                                     (111111)  (31111)    (3311)
                                               (1111111)  (5111)
                                                          (311111)
                                                          (11111111)

Allowing even parts gives A000837.
The strict case is A366844, with evens A078374.
The complement is counted by A366852, with evens A018783.
The pairwise coprime version is A366853, with evens A051424.
A000041 counts integer partitions, strict A000009 (also into odds).
A000740 counts relatively prime compositions.
A168532 counts partitions by gcd.
A366842 counts partitions whose odd parts have a common divisor > 1.
Cf. A007359, A047967, A055922, A066208, A113685, A116598, A289509, A289508, A302697, A337485, A366845, A366848, A366849.

Table[Length[Select[IntegerPartitions[n],#=={}||And@@OddQ/@#&&GCD@@#==1&]],{n,0,30}]

from math import gcd
from sympy.utilities.iterables import partitions
def A366843(n): return sum(1 for p in partitions(n) if all(d&1 for d in p) and gcd(*p)==1) # Chai Wah Wu, Oct 30 2023

A074971 Number of partitions of n into distinct parts of order n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 6, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 32, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 25, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 1, 24, 1, 1, 1, 2, 1, 24, 1, 1, 1, 1, 1, 12, 1, 1, 1, 3, 1, 2

Offset: 1

Vladeta Jovovic, Oct 05 2002

nonn

Order of partition is lcm of its parts.

			The a(36) = 6 partitions are (36), (18,12,6), (18,12,4,2), (18,12,3,2,1), (18,9,4,3,2), (12,9,6,4,3,2). - _Gus Wiseman_, Aug 01 2018

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A000837, A074761, A285572, A290103, A305566, A316431, A316433, A317624.

Cf. also A033630.

A074971(n) = { my(q=0); fordiv(n,i,my(p=1); fordiv(i,j,p *= (1 + 'x^j)); q += moebius(n/i)*p); polcoeff(q,n); }; \\ Antti Karttunen, Dec 19 2018

Coefficient of x^n in expansion of Sum_{i divides n} mu(n/i)*Product_{j divides i} (1+x^j).

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Original entry on oeis.org

0, 1, 1, 4, 1, 13, 1, 33, 10, 94, 1, 327, 1, 913, 100, 3017, 1, 10233, 1, 34236, 919, 119372, 1, 432234, 91, 1574227, 9945, 5916177, 1, 22734231, 1, 89003059, 119378, 356058543, 1000, 1453509039, 1, 6044132797, 1574233, 25612601420, 1, 110509543144, 1, 485161348076

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is periodic if its multiplicities have a common divisor greater than 1. For this sequence neither the parts nor their multiset union are required to be periodic, only the multiset of parts.

			Non-isomorphic representatives of the a(4) = 4 multiset partitions are {{1,1},{1,1}}, {{1,2},{1,2}}, {{1},{1},{1},{1}}, {{1},{1},{2},{2}}.

Cf. A000740, A000837, A001055, A007716, A007916, A049311, A100953, A255906, A269134, A275024, A293993, A301700, A303386, A303431, A303546.

a(n) = 1 if n is prime.

a(n) = A007716(n) - A303546(n).

More terms from Jinyuan Wang, Jun 21 2020

A318731 Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.

Original entry on oeis.org

1, 0, 1, 2, 5, 7, 17, 27, 54, 93, 185, 324, 629, 1143, 2175, 4050, 7709, 14469, 27593, 52276, 99839, 190371, 364721, 698508, 1342170, 2580165, 4970952, 9585232, 18512789, 35787985, 69273665, 134211600, 260300799, 505278705, 981706783

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(6) = 7 relatively prime Lyndon compositions are 15, 114, 132, 123, 1113, 1122, 11112.
The a(7) = 17 relatively prime Lyndon compositions:
  16, 25, 34,
  115, 142, 124, 133, 223,
  1114, 1213, 1132, 1123, 1222,
  11113, 11212, 11122,
  111112.

Cf. A000740, A000837, A008965, A059966, A100953, A296302.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ[#]&&GCD@@#==1&]],{n,10}]

Moebius transform of A059966. Second Moebius transform of A008965.

A321283 Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.

Original entry on oeis.org

1, 1, 2, 7, 21, 84, 214, 895, 2607, 9591, 31134, 119313, 400950, 1574123, 5706112, 22572991, 86933012, 356058243, 1427784135, 6044132304, 25342935667, 110414556330, 481712291885, 2166488898387, 9784077216457, 45369658599779, 211869746691055, 1011161497851296, 4871413403219085

Offset: 0

Gus Wiseman, Nov 06 2018

nonn

Also the number of nonnegative integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which the row sums are relatively prime.
Also the number of non-isomorphic multiset partitions of weight n in which the multiset union of the parts is aperiodic, where a multiset is aperiodic if its multiplicities are relatively prime.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with relatively prime part-sizes:
  {{1}}  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}
         {{1},{2}}  {{1},{2,2}}    {{1},{1,2,2}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1},{2,3,3}}
                    {{1},{1},{1}}  {{1},{2,3,4}}
                    {{1},{2},{2}}  {{2},{1,2,2}}
                    {{1},{2},{3}}  {{3},{1,2,3}}
                                   {{1},{1},{1,1}}
                                   {{1},{1},{2,2}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{1,2}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{1},{1},{1}}
                                   {{1},{1},{2},{2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}
Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with aperiodic multiset union:
  {{1}}  {{1,2}}    {{1,2,2}}      {{1,2,2,2}}
         {{1},{2}}  {{1,2,3}}      {{1,2,3,3}}
                    {{1},{2,2}}    {{1,2,3,4}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1,2},{2,2}}
                    {{1},{2},{2}}  {{1},{2,3,3}}
                    {{1},{2},{3}}  {{1,2},{3,3}}
                                   {{1},{2,3,4}}
                                   {{1,2},{3,4}}
                                   {{1,3},{2,3}}
                                   {{2},{1,2,2}}
                                   {{3},{1,2,3}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

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

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303431, A303546, A303547, A320800-A320810.

\\ See links in A339645 for combinatorial species functions.
seq(n)={my(A=symGroupSeries(n)); NumUnlabeledObjsSeq(sCartProd(sExp(A), 1 + sum(d=1, n, moebius(d) * (-1 + sExp(O(x*x^n) + sum(i=1, n\d, polcoef(A,i*d)*x^(i*d)))) )))} \\ Andrew Howroyd, Jan 17 2023

\\ faster self contained program.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, my(u=vector(n, t, K(q, t, n\t))); s+=permcount(q)*polcoef(sum(d=1, n, moebius(d)*exp(sum(t=1, n\d, sum(i=1, n\(t*d), u[t][i*d]*x^(i*d*t))/t, O(x*x^n)) )), n)); s/n!)} \\ Andrew Howroyd, Jan 17 2023

a(n) = A007716(n) - A320810(n). - Andrew Howroyd, Jan 17 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 17 2023

A325357 Number of integer partitions of n whose augmented differences are strictly increasing.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 3, 5, 5, 4, 5, 6, 5, 7, 7, 7, 7, 9, 7, 10, 10, 8, 11, 13, 10, 13, 14, 12, 14, 17, 13, 17, 19, 17, 18, 22, 19, 22, 24, 21, 24, 28, 24, 29, 30, 28, 31, 35, 30, 35, 40, 36

Offset: 0

Gus Wiseman, Apr 23 2019

nonn

The augmented differences aug(y) of an integer partition y of length k are given by aug(y)i = y_i - y{i + 1} + 1 if i < k and aug(y)_k = y_k. For example, aug(6,5,5,3,3,3) = (2,1,3,1,1,3).

The Heinz numbers of these partitions are given by A325395.

			The a(28) = 10 partitions:
  (28)
  (18,10)
  (17,11)
  (16,12)
  (15,13)
  (14,14)
  (12,10,6)
  (11,10,7)
  (10,10,8)
  (8,8,7,5)
For example, the augmented differences of (8,8,7,5) are (1,2,3,5), which are strictly increasing.

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

Cf. A000837, A007294, A049988, A098859, A325351, A325356, A325360, A325391, A325395.

Mathematica
```
aug[y_]:=Table[If[i
				
```

cp's OEIS Frontend

A328170 Number of integer partitions of n whose parts minus 1 are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334965 Numbers with strictly increasing prime multiplicities.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337452 Number of relatively prime strict integer partitions of n with no 1's.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A366842 Number of integer partitions of n whose odd parts have a common divisor > 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

A366843 Number of integer partitions of n into odd, relatively prime parts.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

A074971 Number of partitions of n into distinct parts of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A318731 Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A321283 Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.

Views