[seqfan] Re: Multiset defining partitions

franktaw at netscape.net franktaw at netscape.net
Sat Mar 19 04:57:23 CET 2011

I think the only reason one would define a partition as a decreasing 
finite sequence of positive integers is that one is not familiar or 
comfortable with the concept of a multiset. I prefer to define them as 
a finite multiset of positive integers. With that definition, the order 
in which they are presented is immaterial; one retains the list in 
decreasing order as the standard presentation. (This is a response more 
to Peter's home page, cited below, rather than to this email.)

Regarding (1), I don't currently have access to the TAOCP IV fascicles; 
is there something there useful in this context?

Regarding (2), I am not uninterested in looking at equivalence classes 
of partitions and multisets. My objection is to confounding equivalence 
classes of multisets with the multisets themselves.

Regarding (3), there are quite a few arrays that have the form:


where the top corner is T(0,0). Generally, these are entered in the 
with column 0 omitted. In a few cases, the array with the 0's as shown 
is also in the OEIS. For example, for Stirling numbers of the 2nd kind, 
the main entry is A008277, with offset 1; there is a secondary entry 
A048993 with offset 0. So leaving off n=0 is the correct thing to do 
for these cases. However, when generating a list of f(P) for some 
function f defined on partitions P, the case n=0 (P empty) should be 

I guess I'm really looking for answers to 2 questions:

A) Is there a standard name for the equivalence classes of multisets 
that are being incorrectly identified as simply multisets in A176723 
and other sequences? If not, is there a good name that can be adopted 
for them?

(Note, by the way, that the equivalent concept for sets has a name: 
they are called cardinals.)

B) Is there a standard name for the partitions defined in A176723 as 
"multiset defining partitions"? If not, is "monotonic partitions" a 
good name for them? Or does anyone have another suggestion to make?

Franklin T. Adams-Watters

-----Original Message-----
From: peter.luschny <peter.luschny at googlemail.com>

> is calling "multisets" are apparently equivalence classes of
> multisets, where one multiset can be turned into another by
> "renaming" the elements. It might be nice if there was a simple term
> for such an equivalence class, but I don't know of one.

A good place to look for terminology is the section
subsection "partitions of a multiset" in Knuth TAOCP IV.
(fascicle 3, p.74). Also surprising is the fact that the
"Multipartition numbers" P(k,n) as given there on page 141
are unknown (as a table) in OEIS.

Without using equivalence classes when working with partitions
you effectively bypass the whole systematic of the subject.
I have tried to give a sketch on this topic on my homepage [1].

Many of the earlier sequences of Wolfdieter are based on a special
type of equivalence, equivalence by equal length. Other types of
equivalences correspond to the types

    equal length       -> "len"
    equal biggest part -> "big"
    coarse-grained     -> "sum"
    fine-grained       -> "part"

Only if one looks at these cases side by side on the same generators
one gets an impression of the larger picture. I have compiled some
special cases which go on OEIS under the name generalized Stirling1
and generalized Stirling2 triangles (see [2] and [3]).

> There should be an initial term 1 with offset 0, representing
> the empty partition.

This is an old problem effecting hundreds of sequences in the
database. The consequences of the basic definitions set by A000070
and A000041 were never enforced.

Related to this is another problem: When I added my share of
triangles to the pool of generalized Stirling triangles I started
with the offset 0 in accordance to A000041. However soon I switched
back to the offset 1 because I wanted the triangles to be displayed
as a triangular array, i.e. I wanted to give them the keyword 'tabl'.

So if consistency (and correctness) as well as the desirable
display as a triangular array is wanted one has to introduce
a new type of triangle (keyword 'tabl0'?)

0           a
1           b
2          c,d
3         e,f,g

[1] http://www.luschny.de/math/seq/CountingWithPartitions.html
[2] http://oeis.org/wiki/User:Peter_Luschny/IndexGeneralStirling1
[3] http://oeis.org/wiki/User:Peter_Luschny/IndexGeneralStirling2



Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list