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

1, 1, 1, 1, 2, 1, 5, 1, 8, 4, 17, 3, 38, 5, 67, 25, 132, 27, 290, 54, 547, 163, 1086, 255, 2277, 530, 4416, 1267, 8850, 2314, 18151, 4737, 35799, 10499, 71776, 20501, 145471, 41934, 289695, 89030, 581117, 178424, 1171545, 365619, 2342563, 761051, 4699711

Offset

0,5

Comments

A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.

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.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Example

The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
From Gus Wiseman, Nov 19 2019: (Start)
The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):
  1  2  3  4   5  6    7  8     9    A      B
           22     24      26    36   28     263
                  33      44    63   46     362
                  42      62    333  55
                  222     224        64
                          242        82
                          422        226
                          2222       244
                                     262
                                     424
                                     442
                                     622
                                     2224
                                     2242
                                     2422
                                     4222
                                     22222
(End)

Maple

b:= proc(n, h) option remember; `if`(n=0, 1,
      add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))
    end:
a:= n-> `if`(n=1, 1, b(n, 1)):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 23 2011

Mathematica

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 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#, {___, x_, y_, ___}/; GCD[x, y]==1]&]], {n, 0, 20}] (* Gus Wiseman, Nov 19 2019 *)

Prog

(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
al(n)=local(m); m=am(n); vector(n, i, sum(j=1, i, m[i, j]))

Crossrefs

The case of partitions is A328187, with Heinz numbers A328336.

Partitions with all pairs of consecutive parts relatively prime are A328172.

Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).

Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220.

Sequence in context: A178472 A337667 A331888 * A093127 A115123 A132081

Adjacent sequences: A178467 A178468 A178469 * A178471 A178472 A178473

Keyword

nonn

Author

Franklin T. Adams-Watters, May 28 2010

Status

approved