A332004 -id:A332004 - cp's OEIS frontend

A101391 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (1<=k<=n).

1, 0, 1, 0, 2, 1, 0, 2, 3, 1, 0, 4, 6, 4, 1, 0, 2, 9, 10, 5, 1, 0, 6, 15, 20, 15, 6, 1, 0, 4, 18, 34, 35, 21, 7, 1, 0, 6, 27, 56, 70, 56, 28, 8, 1, 0, 4, 30, 80, 125, 126, 84, 36, 9, 1, 0, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0, 4, 42, 154, 325, 461, 462, 330, 165, 55, 11, 1, 0, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1

Offset: 1

Emeric Deutsch, Jan 26 2005

If instead we require that the individual parts (x_i,x_j) be relatively prime, we get A282748. This is the question studied by Shonhiwa (2006). - N. J. A. Sloane, Mar 05 2017.

			T(6,3)=9 because we have 411,141,114 and the six permutations of 123 (222 does not qualify).
T(8,3)=18 because binomial(0,2)*mobius(8/1)+binomial(1,2)*mobius(8/2)+binomial(3,2)*mobius(8/4)+binomial(7,2)*mobius(8/8)=0+0+(-3)+21=18.
Triangle begins:
   1;
   0,  1;
   0,  2,  1;
   0,  2,  3,   1;
   0,  4,  6,   4,   1;
   0,  2,  9,  10,   5,   1;
   0,  6, 15,  20,  15,   6,   1;
   0,  4, 18,  34,  35,  21,   7,   1;
   0,  6, 27,  56,  70,  56,  28,   8,   1;
   0,  4, 30,  80, 125, 126,  84,  36,   9,   1;
   0, 10, 45, 120, 210, 252, 210, 120,  45,  10,  1;
   0,  4, 42, 154, 325, 461, 462, 330, 165,  55, 11,  1;
   0, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1;
  ...
From _Gus Wiseman_, Oct 19 2020: (Start)
Row n = 6 counts the following compositions:
  (15)  (114)  (1113)  (11112)  (111111)
  (51)  (123)  (1122)  (11121)
        (132)  (1131)  (11211)
        (141)  (1212)  (12111)
        (213)  (1221)  (21111)
        (231)  (1311)
        (312)  (2112)
        (321)  (2121)
        (411)  (2211)
               (3111)
Missing are: (42), (24), (33), (222).
(End)

Alois P. Heinz, Rows n = 1..200, flattened
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.

Mirror image of A039911.
Row sums are A000740.
Columns 2-9 are: A000010, A000741, A000742, A000743, A023031, A023032, A023033, A023034.
A000837 counts relatively prime partitions.
A135278 counts compositions by length.
A282748 is the pairwise coprime instead of relatively prime version.
A282750 is the unordered version.
A291166 ranks these compositions (evidently).
T(2n+1,n+1) gives A000984.
Cf. A007359, A008683, A085411, A101268, A289508, A289509, A302697, A332004, A337485, A337563.

with(numtheory): T:=proc(n,k) local d, j, b: d:=divisors(n): for j from 1 to tau(n) do b[j]:=binomial(d[j]-1,k-1)*mobius(n/d[j]) od: sum(b[i],i=1..tau(n)) end: for n from 1 to 14 do seq(T(n,k),k=1..n) od; # yields the sequence in triangular form
# second Maple program:
b:= proc(n, g) option remember; `if`(n=0, `if`(g=1, 1, 0),
      expand(add(b(n-j, igcd(g, j))*x, j=1..n)))
    end:
T:= (n, k)-> coeff(b(n,0),x,k):
seq(seq(T(n,k), k=1..n), n=1..14);  # Alois P. Heinz, May 05 2025

t[n_, k_] := Sum[Binomial[d-1, k-1]*MoebiusMu[n/d], {d, Divisors[n]}]; Table[t[n, k], {n, 2, 14}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jan 20 2014 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],GCD@@#==1&]],{n,10},{k,2,n}] (* change {k,2,n} to {k,1,n} for the version with zeros. - Gus Wiseman, Oct 19 2020 *)

T(n, k) = sumdiv(n, d, binomial(d-1, k-1)*moebius(n/d)); \\ Michel Marcus, Mar 09 2016

T(n,k) = Sum_{d|n} binomial(d-1,k-1)*mobius(n/d).

Sum_{k=1..n} k * T(n,k) = A085411(n). - Alois P. Heinz, May 05 2025

Definition clarified by N. J. A. Sloane, Mar 05 2017

Edited by Alois P. Heinz, May 05 2025

A337697 Number of pairwise coprime compositions of n with no 1's, where a singleton is not considered coprime.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 0, 4, 2, 4, 8, 8, 14, 10, 16, 12, 30, 38, 46, 46, 48, 52, 62, 152, 96, 156, 112, 190, 256, 338, 420, 394, 326, 402, 734, 622, 1150, 802, 946, 898, 1730, 1946, 2524, 2200, 2328, 2308, 3356, 5816, 4772, 5350, 4890, 6282, 6316, 12092, 8902

Offset: 0

Gus Wiseman, Oct 06 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. These compositions must be strict.

			The a(5) = 2 through a(12) = 14 compositions (empty column indicated by dot):
  (2,3)  .  (2,5)  (3,5)  (2,7)  (3,7)    (2,9)  (5,7)
  (3,2)     (3,4)  (5,3)  (4,5)  (7,3)    (3,8)  (7,5)
            (4,3)         (5,4)  (2,3,5)  (4,7)  (2,3,7)
            (5,2)         (7,2)  (2,5,3)  (5,6)  (2,7,3)
                                 (3,2,5)  (6,5)  (3,2,7)
                                 (3,5,2)  (7,4)  (3,4,5)
                                 (5,2,3)  (8,3)  (3,5,4)
                                 (5,3,2)  (9,2)  (3,7,2)
                                                 (4,3,5)
                                                 (4,5,3)
                                                 (5,3,4)
                                                 (5,4,3)
                                                 (7,2,3)
                                                 (7,3,2)

A022340 intersected with A333227 is a ranking sequence (using standard compositions A066099) for these compositions.
A212804 does not require coprimality, with unordered version A002865.
A337450 is the relatively prime instead of pairwise coprime version, with strict case A337451 and unordered version A302698.
A337462 allows 1's, with strict case A337561 (or A101268 with singletons), unordered version A327516 with Heinz numbers A302696, and 3-part case A337461.
A337485 is the unordered version (or A007359 with singletons considered coprime), with Heinz numbers A337984.
A337563 is the case of unordered triples.
Cf. A078374, A178472, A302568, A302697, A305713, A307719, A332004, A337562.

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

For n > 1, the version where singletons are considered coprime is a(n) + 1.

A282748 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 4, 3, 4, 1, 1, 2, 9, 4, 5, 1, 1, 6, 3, 16, 5, 6, 1, 1, 4, 15, 4, 25, 6, 7, 1, 1, 6, 9, 28, 5, 36, 7, 8, 1, 1, 4, 21, 16, 45, 6, 49, 8, 9, 1, 1, 10, 9, 52, 25, 66, 7, 64, 9, 10, 1, 1, 4, 39, 16, 105, 36, 91, 8, 81, 10, 11, 1, 1, 12, 9, 100, 25, 186, 49, 120, 9, 100, 11, 12, 1, 1, 6, 45, 16, 205, 36, 301, 64, 153, 10, 121, 12, 13, 1

Offset: 1

N. J. A. Sloane, Mar 05 2017

See A101391 for the triangle T(n,k) = number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (2 <= k <= n).

			Triangle begins:
  1;
  1,  1;
  1,  2,  1;
  1,  2,  3,   1;
  1,  4,  3,   4,   1;
  1,  2,  9,   4,   5,   1;
  1,  6,  3,  16,   5,   6,  1;
  1,  4, 15,   4,  25,   6,  7,   1;
  1,  6,  9,  28,   5,  36,  7,   8,  1;
  1,  4, 21,  16,  45,   6, 49,   8,  9,   1;
  1, 10,  9,  52,  25,  66,  7,  64,  9,  10,  1;
  1,  4, 39,  16, 105,  36, 91,   8, 81,  10, 11,  1;
  1, 12,  9, 100,  25, 186, 49, 120,  9, 100, 11, 12, 1;
  ...
From _Gus Wiseman_, Nov 12 2020: (Start)
Row n = 6 counts the following compositions:
  (6)  (15)  (114)  (1113)  (11112)  (111111)
       (51)  (123)  (1131)  (11121)
             (132)  (1311)  (11211)
             (141)  (3111)  (12111)
             (213)          (21111)
             (231)
             (312)
             (321)
             (411)
(End)

Alois P. Heinz, Rows n = 1..200, flattened (first 100 rows from Chai Wah Wu)
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.

A072704 counts the unimodal instead of coprime version.
A087087 and A335235 rank these compositions.
A101268 gives row sums.
A101391 is the relatively prime instead of pairwise coprime version.
A282749 is the unordered version.
A000740 counts relatively prime compositions, with strict case A332004.
A007360 counts pairwise coprime or singleton strict partitions.
A051424 counts pairwise coprime or singleton partitions, ranked by A302569.
A097805 counts compositions by sum and length.
A178472 counts compositions with a common divisor.
A216652 and A072574 count strict compositions by sum and length.
A305713 counts pairwise coprime strict partitions.
A327516 counts pairwise coprime partitions, ranked by A302696.
A335235 ranks pairwise coprime or singleton compositions.
A337462 counts pairwise coprime compositions, ranked by A333227.
A337562 counts pairwise coprime or singleton strict compositions.
A337665 counts compositions whose distinct parts are pairwise coprime, ranked by A333228.
Cf. A000837, A007359, A302568, A337461, A337561, A337667.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],Length[#]==1||CoprimeQ@@#&]],{n,10},{k,n}] (* Gus Wiseman, Nov 12 2020 *)

It seems that no general formula or recurrence is known, although Shonhiwa gives formulas for a few of the early diagonals.

A338468 Odd squarefree numbers whose prime indices have no common divisor > 1.

Original entry on oeis.org

15, 33, 35, 51, 55, 69, 77, 85, 93, 95, 105, 119, 123, 141, 143, 145, 155, 161, 165, 177, 187, 195, 201, 205, 209, 215, 217, 219, 221, 231, 249, 253, 255, 265, 285, 287, 291, 295, 309, 323, 327, 329, 335, 341, 345, 355, 357, 381, 385, 391, 395, 403, 407, 411

Offset: 1

Gus Wiseman, Oct 29 2020

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

Also Heinz numbers of relatively prime strict integer partitions with no 1's (A337452). The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

			The sequence of terms together with their prime indices begins:
     15: {2,3}      145: {3,10}     249: {2,23}     355: {3,20}
     33: {2,5}      155: {3,11}     253: {5,9}      357: {2,4,7}
     35: {3,4}      161: {4,9}      255: {2,3,7}    381: {2,31}
     51: {2,7}      165: {2,3,5}    265: {3,16}     385: {3,4,5}
     55: {3,5}      177: {2,17}     285: {2,3,8}    391: {7,9}
     69: {2,9}      187: {5,7}      287: {4,13}     395: {3,22}
     77: {4,5}      195: {2,3,6}    291: {2,25}     403: {6,11}
     85: {3,7}      201: {2,19}     295: {3,17}     407: {5,12}
     93: {2,11}     205: {3,13}     309: {2,27}     411: {2,33}
     95: {3,8}      209: {5,8}      323: {7,8}      413: {4,17}
    105: {2,3,4}    215: {3,14}     327: {2,29}     415: {3,23}
    119: {4,7}      217: {4,11}     329: {4,15}     429: {2,5,6}
    123: {2,13}     219: {2,21}     335: {3,19}     435: {2,3,10}
    141: {2,15}     221: {6,7}      341: {5,11}     437: {8,9}
    143: {5,6}      231: {2,4,5}    345: {2,3,9}    447: {2,35}

A302568 is the prime or pairwise coprime version, counted by A007359.
A302697 is not required to be squarefree, counted by A302698 (ordered version: A337450).
A302796 allows evens, counted by A078374 (ordered version: A332004).
A337452 counts partitions with these Heinz numbers (ordered version: A337451).
A337984 is the pairwise coprime version, counted by A337485 (ordered version: A337697).
A005117 lists squarefree numbers.
A005408 lists odd numbers.
A056911 lists odd squarefree numbers.
A289509 lists Heinz numbers of relatively prime partitions, counted by A000837 (ordered version: A000740).
Cf. A000010, A007359, A051424, A055684, A056239, A101268, A289508, A302505, A302569, A302696, A302798, A337694.

Select[Range[1,100,2],SquareFreeQ[#]&&GCD@@PrimePi/@First/@FactorInteger[#]==1&]

cp's OEIS Frontend

A101391 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A337697 Number of pairwise coprime compositions of n with no 1's, where a singleton is not considered coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A282748 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A338468 Odd squarefree numbers whose prime indices have no common divisor > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica