|
|
A178472
|
|
Number of compositions (ordered partitions) of n where the gcd of the part sizes is not 1.
|
|
41
|
|
|
0, 1, 1, 2, 1, 5, 1, 8, 4, 17, 1, 38, 1, 65, 19, 128, 1, 284, 1, 518, 67, 1025, 1, 2168, 16, 4097, 256, 8198, 1, 16907, 1, 32768, 1027, 65537, 79, 133088, 1, 262145, 4099, 524408, 1, 1056731, 1, 2097158, 16636, 4194305, 1, 8421248, 64, 16777712, 65539
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Of course, all part sizes must be greater than 1; that condition alone gives the Fibonacci numbers, which is thus an upper bound.
Also the number of periodic compositions of n, where a sequence is periodic if its cyclic rotations are not all different. Also compositions with non-relatively prime run-lengths. - Gus Wiseman, Nov 10 2019
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{d|n & d<n} 2^(d-1) * (-mu(n/d)).
|
|
EXAMPLE
|
For n=6, we have 5 compositions: <6>, <4,2>, <2,4>, <2,2,2>, and <3,3>.
The a(2) = 1 through a(9) = 4 non-relatively prime compositions:
(2) (3) (4) (5) (6) (7) (8) (9)
(2,2) (2,4) (2,6) (3,6)
(3,3) (4,4) (6,3)
(4,2) (6,2) (3,3,3)
(2,2,2) (2,2,4)
(2,4,2)
(4,2,2)
(2,2,2,2)
The a(2) = 1 through a(9) = 4 periodic compositions:
11 111 22 11111 33 1111111 44 333
1111 222 1313 121212
1212 2222 212121
2121 3131 111111111
111111 112112
121121
211211
11111111
The a(2) = 1 through a(9) = 4 compositions with non-relatively prime run-lengths:
11 111 22 11111 33 1111111 44 333
1111 222 1133 111222
1122 2222 222111
2211 3311 111111111
111111 111122
112211
221111
11111111
(End)
|
|
MAPLE
|
A178472 := n -> (2^n - add(mobius(n/d)*2^d, d in divisors(n)))/2:
|
|
MATHEMATICA
|
Table[2^(n - 1) - DivisorSum[n, MoebiusMu[n/#]*2^(# - 1) &], {n, 51}] (* Michael De Vlieger, Jan 20 2018 *)
|
|
PROG
|
(PARI) vector(60, n, 2^(n-1)-sumdiv(n, d, 2^(d-1)*moebius(n/d)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|