|
%I #17 Nov 20 2019 09:34:01
%S 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 2277,530,4416,1267,8850,2314,18151,4737,35799,10499,71776,20501,
%U 145471,41934,289695,89030,581117,178424,1171545,365619,2342563,761051,4699711
%N Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.
%C A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.
%C 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 Alois P. Heinz, <a href="/A178470/b178470.txt">Table of n, a(n) for n = 0..1000</a>
%e The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
%e From _Gus Wiseman_, Nov 19 2019: (Start)
%e The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):
%e 1 2 3 4 5 6 7 8 9 A B
%e 22 24 26 36 28 263
%e 33 44 63 46 362
%e 42 62 333 55
%e 222 224 64
%e 242 82
%e 422 226
%e 2222 244
%e 262
%e 424
%e 442
%e 622
%e 2224
%e 2242
%e 2422
%e 4222
%e 22222
%e (End)
%p b:= proc(n, h) option remember; `if`(n=0, 1,
%p add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))
%p end:
%p a:= n-> `if`(n=1, 1, b(n, 1)):
%p seq(a(n), n=0..60); # _Alois P. Heinz_, Oct 23 2011
%t 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 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{___,x_,y_,___}/;GCD[x,y]==1]&]],{n,0,20}] (* _Gus Wiseman_, Nov 19 2019 *)
%o (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 al(n)=local(m);m=am(n);vector(n,i,sum(j=1,i,m[i,j]))
%Y The case of partitions is A328187, with Heinz numbers A328336.
%Y Partitions with all pairs of consecutive parts relatively prime are A328172.
%Y Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).
%Y Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220.
%K nonn
%O 0,5
%A _Franklin T. Adams-Watters_, May 28 2010
|
