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).

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,5

Comments

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).

Links

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.

Formula

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

Example

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)

Mathematica

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

Crossrefs

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.

Sequence in context: A306210 A133255 A354273 * A145972 A215204 A260876

Adjacent sequences: A282745 A282746 A282747 * A282749 A282750 A282751

Keyword

nonn,tabl

Author

N. J. A. Sloane, Mar 05 2017

Status

approved