[seqfan] Re: Multiset defining partitions

peter.luschny peter.luschny at googlemail.com
Sat Mar 19 11:54:06 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.

A partition here means integer-partition or set-partition?
As far as I know the conventions of OEIS is to understand
by a partition an integer partition; only set partitions have
to qualified as 'set partitions'.

Clearly both are special cases of partitions of multisets.
An integer partition then is the same as the partition
of {1,1,...,1} (n 1s). This fact does not prevent major
writers on this subject to define an integer partition
as a finite nonincreasing sequence (see G. Andrews 'The
theory of partition', definition 1, as an example). I assume
authors like MacMahon, Andrews and Knuth are both familiar and
comfortable with the concept of a multiset.

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

Since your first comment makes me unsure whether I understand
you right I will refrain to go into details. But the terminology
'block' and 'k-block' might apply here.

> Regarding (3), there are quite a few arrays that have the form:
> #
> 0,#
> 0,#,#
> 0,#,#,#
> ...
> where the top corner is T(0,0). Generally, these are entered in the
> with column 0 omitted.

Yes, this is clear and your Stirling number example A008277/A048993
works because the 0s fit the general definition a priori. Perhaps
A008277 is just an artifact, a byte saving trick from the dark ages
of limited memory, I don't know.

But you cannot enter something like

0|  5
1|  3
2|  7,3
3|  4,5,6
4|  6,8,9,7

with keyword 'tabl'; the table would not correctly display. All
you can do, if you wish this sequence to be shown as a triangular
array, is to omit the very first entry.

For instance how do you correctly enter the ternary digits shown
in the table in A182929 for n >= 0? In fact I resorted to
encode the sequence as decimal numbers just for this reason
although I think the sequence of ternary digits is the more
important one.

> 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"?

I do not know but I doubt. A reason might be that things become
a little complex at the level of equivalence classes of multisets
without introducing new concepts. So it would be better to shift
gears and realize that multisets are just special cases of more
natural concepts associated with morphisms. You end then with
something like the cardinality of kernels of morphisms.

However, I am quite sure that not everyone is familiar or
comfortable with these concepts so it might be better to go
with ad hoc names.

More information about the SeqFan mailing list