login
Number of relatively prime compositions of n with no 1's.
11

%I #34 Feb 02 2021 19:07:33

%S 0,0,0,0,0,2,0,7,5,17,17,54,51,143,168,358,482,986,1313,2583,3663,

%T 6698,9921,17710,26489,46352,70928,121137,188220,317810,497322,832039,

%U 1313501,2177282,3459041,5702808,9094377,14930351,23895672,39084070,62721578

%N Number of relatively prime compositions of n with no 1's.

%C A composition of n is a finite sequence of positive integers summing to n.

%H Alois P. Heinz, <a href="/A337450/b337450.txt">Table of n, a(n) for n = 0..2000</a> (first 171 terms from Fausto A. C. Cariboni)

%e The a(5) = 2 through a(10) = 17 compositions (empty column indicated by dot):

%e (2,3) . (2,5) (3,5) (2,7) (3,7)

%e (3,2) (3,4) (5,3) (4,5) (7,3)

%e (4,3) (2,3,3) (5,4) (2,3,5)

%e (5,2) (3,2,3) (7,2) (2,5,3)

%e (2,2,3) (3,3,2) (2,2,5) (3,2,5)

%e (2,3,2) (2,3,4) (3,3,4)

%e (3,2,2) (2,4,3) (3,4,3)

%e (2,5,2) (3,5,2)

%e (3,2,4) (4,3,3)

%e (3,4,2) (5,2,3)

%e (4,2,3) (5,3,2)

%e (4,3,2) (2,2,3,3)

%e (5,2,2) (2,3,2,3)

%e (2,2,2,3) (2,3,3,2)

%e (2,2,3,2) (3,2,2,3)

%e (2,3,2,2) (3,2,3,2)

%e (3,2,2,2) (3,3,2,2)

%p b:= proc(n, g) option remember; `if`(n=0,

%p `if`(g=1, 1, 0), add(b(n-j, igcd(g, j)), j=2..n))

%p end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..42);

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[#,1]&&GCD@@#==1&]],{n,0,15}]

%Y A000740 is the version allowing 1's.

%Y 2*A055684(n) is the case of length 2.

%Y A302697 ranks the unordered case.

%Y A302698 is the unordered version.

%Y A337451 is the strict version.

%Y A337452 is the unordered strict version.

%Y A000837 counts relatively prime partitions.

%Y A002865 counts partitions with no 1's.

%Y A101268 counts singleton or pairwise coprime compositions.

%Y A212804 counts compositions with no 1's.

%Y A291166 appears to rank relatively prime compositions.

%Y A337462 counts pairwise coprime compositions.

%Y Cf. A000010, A007359, A023023, A101268, A178472, A289509, A302568, A337485.

%K nonn

%O 0,6

%A _Gus Wiseman_, Aug 31 2020