Multiset Signatures and Partitions

[franktaw at netscape.net]

Let us define the signature of a (finite) multiset to be the partition composed of the multiplicities of the members of the multiset.  For example, for the multiset {1,1,1,1,2,2,3,4}, the signature is {1,1,2,4}.  The prime signature of a number is then the signature of its prime factor multiset.
 
(I don't know if anybody has identified this concept before, possibly with a different name.)
 
Since a partition is also a multiset, the signature operation can be applied repeatedly.  Starting with any non-empty multiset, repeated application will eventually lead to {1}.  The number of steps required to get there is:
 
0,1,2,1,3,2,1,3,2,4,2,1,3,3,4,4,4,2,1,3,3,2,4,3,2,4,3,4,2,1,3,3,
3,4,3,4,4,4,5,4,4,4,4,2,1,3,3,3,2,4,3,3,4,4,4,5,3,5,2,4,5,4,4,4,
4,2,1,3,3,3,3,4,3,3,4,4,3,2,4,5,5,5,5,4,4,5,4,5,4,4,5,3,4,4,4,2
 
for partitions in Abramowitz and Stegun order.  This is not (yet) in the OEIS.
 
The smallest partition requiring n steps is:
1
2
1,1
1,2
1,1,2
1,1,2,3
1,1,1,2,2,3,4
1,1,1,1,2,2,2,3,3,4,4,5,6,7
...
 
which is A012257, with an initial 1,2.  ("Smallest" partition is in general an ambiguous concept, but there in this case, any other partition requiring the same number of steps has a larger total.)
 
Another application is A048996, which counts the number of compositions associated with a partition.  (A072811 is the Mathematica version of this sequence, but they do not cross-reference each other, and the description in A048996 does not describe them well.)  A048996(P)=Multinomial(Signature(P)), where Multinomial is A036038 (in A&S order, no Mma equivalent is present).
 
One should probably also add:
1
1, 2,
1, 1,1, 3,
1, 1,1, 2, 1,2, 4, (or 1, 1,1, 2, 2,1, 4,)
...
The sequence of signatures of partitions, with an associated sequence giving their lengths:
1, 1,1, 1,2,1, 1,2,1,2,1, ...
 
The number of items on each line of the former sequence is A000070, as indicated by the comment line there beginning "Also the total number of all different ...".
 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060117/b9ba3216/attachment.htm>