A332002 Number of compositions (ordered partitions) of n into distinct parts all relatively prime to n.

1, 1, 0, 2, 2, 4, 2, 12, 4, 6, 4, 64, 4, 132, 6, 32, 32, 616, 6, 1176, 32, 120, 58, 4756, 32, 3452, 108, 1632, 132, 30460, 8, 55740, 376, 3872, 352, 18864, 132, 315972, 1266, 13368, 352, 958264, 108, 1621272, 2228, 10176, 6166, 4957876, 352, 2902866, 2132

Offset

0,4

Links

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

Index entries for sequences related to compositions

Example

a(9) = 6 because we have [8, 1], [7, 2], [5, 4], [4, 5], [2, 7] and [1, 8].

Maple

a:= proc(n) local b; b:=
      proc(m, i, p) option remember; `if`(m=0, p!, `if`(i<1, 0,
        b(m, i-1, p)+`if`(i>m or igcd(i, n)>1, 0, b(m-i, i-1, p+1))))
      end; forget(b): b(n$2, 0)
    end:
seq(a(n), n=0..63);  # Alois P. Heinz, Feb 04 2020

Mathematica

a[n_] := Module[{b}, b[m_, i_, p_] := b[m, i, p] = If[m == 0, p!, If[i < 1, 0, b[m, i-1, p] + If[i > m || GCD[i, n] > 1, 0, b[m-i, i-1, p+1]]]]; b[n, n, 0]];
a /@ Range[0, 63] (* Jean-François Alcover, Nov 26 2020, after Alois P. Heinz *)

Crossrefs

Cf. A032020, A036998, A057562, A100347, A331888, A332003.

Sequence in context: A353564 A067228 A356543 * A229756 A227450 A010026

Adjacent sequences: A331999 A332000 A332001 * A332003 A332004 A332005

Keyword

nonn

Author

Ilya Gutkovskiy, Feb 04 2020

Status

approved