1
$\begingroup$

I am working on a combinatorics library of mine, where Partitions and Compositions are also included. For unrestricted partitions, the definition of conjugate partition is fine. Conjugates are used in some transformations that swap between LEX and COLEX orderings.

Now I would like to use same principles for restricted partitions (eg with fixed number of parts). But in this case, the definition of conjugate/transpose partition produces partitions which are outside the class of partitions required (i.e no more with fixed num of parts, but with fixed greater part).

Ideally, I would expect "restricted conjugate" of $(5311)$ (LEX) to be $(3331)$ (COLEX), or alternatively the "restricted conjugate" of $(4222)$ (REVLEX) would be $(3331)$ (COLEX). Both are fine for what is needed, I can use any of the two (both cannot hold at the same time).

enter image description here

Is there an extension or alternative to the usual conjugate/transpose of a partition that maintains the restrictions applied (i.e maintains number of parts, maximum part, minimum part)?

$\endgroup$
12

1 Answer 1

1
$\begingroup$

Here's a modified conjugation that fixes the number of parts. I'll describe it in terms of Ferrers diagrams.

Conjugate the partition. If the result has $k$ too few rows (parts), turn the first $k$ columns into rows. For instance, with $k=4$, 3322 has conjugate 442 and then the mapping gives 3331---removing the leftmost column from 442 leaves 331 and that removed column became another 3. (This column-to-row operation is known as Bulgarian Solitaire.)

If the conjugate has too many rows, remove the partition from the $(k+1)$st row down, conjugate it, and append it to the remaining four rows. E.g., still with $k = 4$, 6411 has conjugate 422211 with 11 below the intended 4 rows; the conjugate of the small partition (guaranteed to have at most 4 parts) is 2 so the mapping gives 6222.

If the result of conjugation has the desired number of rows, you're done!

The map definitions may need tweaking and there are certainly details to check (for at least the two examples and a few small $n$ for which I worked everything out, this is an involution).

By the way, this made me think of Wilf partitions, where the (nonzero) multiplicities of its parts are all different. This class is closed by the involution that swaps parts and multiplicities, e.g., 422111 or $4^1 2^2 1^3$ becomes $3221111$ or $3^1 2^2 1^4$.

$\endgroup$
5
  • $\begingroup$ Nice, I have thought of some extensions of conjugation that preserve number of parts. However the conjugation needed in this case is not an involution as seen in the LEX/COLEX examples (assuming they are related by a kind of conjugation). Fixed num parts is only one of the restrictions supported for partitions, others are fixed min part anf fixed max part (and all combinations of those). Any idea how applying conjugate can accomodate these restrictions? $\endgroup$
    – Nikos M.
    Jul 9, 2021 at 13:03
  • $\begingroup$ @NikosM. Let me just say that if you require too many restrictions, then only the identity map will work. In your example of 4-part partitions of 10, fixing both largest and smallest part means that most of the partitions can only be mapped to themselves, with switching only possible in the pairs 4411 & 4321 and 5311 & 5221. $\endgroup$ Jul 10, 2021 at 0:53
  • $\begingroup$ See for example this restricted partition that is in lex order. A "conjugation" that maps this to colex order is somewhat involved, but it is not the identity map. $\endgroup$
    – Nikos M.
    Jul 10, 2021 at 9:13
  • $\begingroup$ @NikosM. It's nice to see Abacus. Of course, "only" in my previous comment was too strong, as my own example showed. For the 248 partitions of 25 with 7 parts (the setting of your linked example), at least 20 have to fixed under any involution preserving number of parts, min, and max: 9 of the min/max combinations have size 1 (so these are fixed points under any map preserving these stats) and another 11 of those have odd size (so at least one fixed point each under an involution). In contract, 3 of these are self-conjugate under "normal" conjugation (7752222, 7643221 , and 7553311). $\endgroup$ Jul 10, 2021 at 13:44
  • $\begingroup$ Yes exactly, it seems the "conjugation" I am after (one that relates LEX and COLEX), is quite involved. The idea is an extrapolation of the usual/ferres conjugation which relates LEX and COLEX orders (the conjugate of an item in LEX order gives the associated item in COLEX order). One can define many proposals for restricted conjugation, but the one asked is the one which relates these two combinatorial orderings $\endgroup$
    – Nikos M.
    Jul 10, 2021 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.