Witt's formula and montonicity

[wouter meeussen]

P. Moree's formula can be translated into Mathematica as:

moree[li : {__Integer}] := Module[
     {n = Plus @@ li},
      Fold[#1 + MoebiusMu[#2]Apply[Multinomial, li/#2] &, 0,
         Divisors[ GCD @@ li] ] /n]

if we choose to operate on all sets of integers summing to n
(the partitions of n), we get:

 Table[moree /@ Partitions[n], {n, 7}]

{ {1},
 {0, 1},
 {0, 1, 2},
 {0, 1, 1, 3, 6},
 {0, 1, 2, 4, 6, 12, 24},
 {0, 1, 2, 5, 3, 10, 20, 14, 30, 60, 120},
 {0, 1, 3, 6, 5, 15, 30, 20, 30, 60, 120, 90, 180, 360, 720}
}

Summing over all partitions of n (altough that wasn't asked for) gives:

 Table[Plus @@ (moree /@ Partitions[n]), {n, 12}]

{1, 1, 3, 11, 49, 265, 1640, 11932, 96780, 887931, 8939050, 99298073}

not yet known to the flock, 'tough its inverse Moebius transform is:
{1, 2, 4, 13, 50, 270, 1641, 11945, 96784, 887982, 8939051, 99298354}
and, oh joy, that looks almost exactly like
http://www.research.att.com/projects/OEIS?Anum=A072605
better known as "Necklaces of n beads and up to n unlabeled (interchangeable) colors".

If Christian Bower would see this, he might offer a combinatorial argument *why* both formulae (P.
moree's and A072605) are each others Moebius transform, and (so) why P. Moree's sequence must be
non-decreasing.

As peculiar side-observation:
moree[] without dividing by n gives sums_over_partitions equal to
1,2,9,44,245,1590,11480,95456,871020,8879310,98329550,1191576876
which SuperSeeker recognises as the Moebius transform of:

1,1,3,10,47,246,1602,11481,95503,871030
A005651 Sum of multinomial coefficients

is this simply turning in rounds, or something unexpected?


Wouter.