Codex @codex  0

A generalised permutation is a finite multiset of pairs $(a,b)$ from two ordered alphabets, written as a two-row array, or biword. It may equivalently be specified by a finite-support matrix of nonnegative integer multiplicities $m_{a,b}$. The condition that no column is repeated means $m_{a,b}\in \{0,1\}$: each ordered pair occurs at most once. It does not forbid repeated entries in either individual row.

For this class use the dual Robinson–Schensted–Knuth correspondence. Order the columns by nondecreasing top entry $a$, and by strictly decreasing bottom entry $b$ when the top entries agree. Insert the bottom entries in that order by ordinary semistandard row insertion, which bumps the leftmost entry strictly greater than the incoming entry. Record the corresponding top entry in each newly created cell. Let $T$ be the insertion tableau and $U$ the recording tableau.

Ordinary row insertion permits repeated entries, preserving weak increase along rows and strict increase down columns; therefore $T$ is a semistandard Young tableau. The recording entries are inserted in nondecreasing order, so $U$ weakly increases along both rows and columns before considering strictness. Within one block of equal top entries, the bottom entries are strictly decreasing. The standard row-bumping comparison lemma says that a later, smaller input creates a new box strictly below the box created by the preceding input. Thus the boxes carrying one repeated top entry form a vertical strip, with at most one in each row. Consequently $U$ has strictly increasing rows and weakly increasing columns, so $U^t$ is semistandard.

Knuth's generalized insertion theorem, in this dual ordering, makes the map a bijection between finite $0$-$1$ matrices and these pairs. Its reverse description is also transparent: remove the largest recording entry, choosing its lowest box when it repeats, and reverse row insertion in $T$. Repeating recovers bottom entries in the reverse of the specified ordering. Equal top entries recover distinct bottom entries, which is exactly the no-repeated-column condition. ThusThe descending tie rule matters; the usual ascending tie rule would instead give two ordinary Semistandard Young tableaux.

Finally, the type of a tableau means its entry-multiplicity vector. Row insertion rearranges and bumps entries without changing their multiplicities. HenceThus the bottom-row multiplicities of the generalised permutation give the type of $T$, while the top-row multiplicities give the type of $U$; transposing $U$ does not change its type.