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

Author

N. J. A. Sloane, Mar 05 2017

Keywords

• nonn
• tabl

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

Examples

			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)
		

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.

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.

Programs

Mathematica

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

Formula

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