cp's OEIS Frontend

A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

%I A178470 #17 Nov 20 2019 09:34:01
%S A178470 1,1,1,1,2,1,5,1,8,4,17,3,38,5,67,25,132,27,290,54,547,163,1086,255,
%T A178470 2277,530,4416,1267,8850,2314,18151,4737,35799,10499,71776,20501,
%U A178470 145471,41934,289695,89030,581117,178424,1171545,365619,2342563,761051,4699711
%N A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.
%C A178470 A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.
%C A178470 a(0) = 1 vacuously for the empty composition. One could take a(1) = 0, on the theory that each composition is followed by infinitely many 0's, and thus the 1 is not relatively prime to its neighbor; but this definition seems simpler.
%H A178470 Alois P. Heinz, <a href="/A178470/b178470.txt">Table of n, a(n) for n = 0..1000</a>
%e A178470 The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
%e A178470 From _Gus Wiseman_, Nov 19 2019: (Start)
%e A178470 The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):
%e A178470   1  2  3  4   5  6    7  8     9    A      B
%e A178470            22     24      26    36   28     263
%e A178470                   33      44    63   46     362
%e A178470                   42      62    333  55
%e A178470                   222     224        64
%e A178470                           242        82
%e A178470                           422        226
%e A178470                           2222       244
%e A178470                                      262
%e A178470                                      424
%e A178470                                      442
%e A178470                                      622
%e A178470                                      2224
%e A178470                                      2242
%e A178470                                      2422
%e A178470                                      4222
%e A178470                                      22222
%e A178470 (End)
%p A178470 b:= proc(n, h) option remember; `if`(n=0, 1,
%p A178470       add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))
%p A178470     end:
%p A178470 a:= n-> `if`(n=1, 1, b(n, 1)):
%p A178470 seq(a(n), n=0..60);  # _Alois P. Heinz_, Oct 23 2011
%t A178470 b[n_, h_] := b[n, h] = If[n == 0, 1, Sum [If[h == 1 || GCD[j, h] > 1, b[n - j, j], 0], {j, 2, n}]]; a[n_] := If[n == 1, 1, b[n, 1]]; Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Oct 29 2015, after _Alois P. Heinz_ *)
%t A178470 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{___,x_,y_,___}/;GCD[x,y]==1]&]],{n,0,20}] (* _Gus Wiseman_, Nov 19 2019 *)
%o A178470 (PARI) am(n)=local(r);r=matrix(n,n,i,j,i==j);for(i=2,n,for(j=1,i-1,for(k=1,j,if(gcd(i-j,k)>1,r[i,i-j]+=r[j,k]))));r
%o A178470 al(n)=local(m);m=am(n);vector(n,i,sum(j=1,i,m[i,j]))
%Y A178470 The case of partitions is A328187, with Heinz numbers A328336.
%Y A178470 Partitions with all pairs of consecutive parts relatively prime are A328172.
%Y A178470 Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).
%Y A178470 Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220.
%K A178470 nonn
%O A178470 0,5
%A A178470 _Franklin T. Adams-Watters_, May 28 2010