# [seqfan] Re: what are "sorted tuples" called?

William Keith william.keith at gmail.com
Wed May 6 18:03:04 CEST 2020

The usual trick for counting these with generating functions is to imagine
subtracting a staircase of size 1, 3, 5, etc. from the parts.  The result
is a partition without restriction except for the maximum number and sizes
of parts again.  The staircase will have added k^2 to the weight if there
are k parts, and if the original maximum part size is m, the remaining
maximum part size will be m-(2k+1).

Ex.: the "neighbor-free sorted tuples on alphabet 1-10 with exactly 3
parts" are in correspondence with "partitions into at most 3 parts of sizes
at most 5," and hence have generating function

q^9 \left[ {8 \atop 3} \right]_q .

Best,
William