CF 103575B - Even Tree

Rating: -
Tags: -
Solve time: 2m 38s
Verified: no

Solution

Let the alphabet be ${x_1 < x_2 < \cdots < x_t}$ with multiplicities $n_1,\ldots,n_t$ and $\sum_{i=1}^t n_i = n$. Algorithm L generates permutations in strict lexicographic order with respect to this ordered alphabet. The rank of a permutation $a_1 \ldots a_n$ is therefore the number of distinct multiset permutations that are lexicographically smaller.

Fix a prefix $a_1 \ldots a_{i-1}$. At position $i$, suppose the remaining available multiplicities are $m_1,\ldots,m_t$ with total $m = n-i+1$. If a symbol $x_k$ is placed at position $i$, the number of completions is the multinomial coefficient

$$\frac{(m-1)!}{m_1!\cdots (m_k-1)!\cdots m_t!}.$$

Summing this over all $x_k < a_i$ gives the contribution of position $i$ to the rank. This is exactly the standard multinomial Lehmer code adapted to repeated symbols.

Now consider the permutation

$$314159265.$$

The underlying ordered symbols are

$$1 < 2 < 3 < 4 < 5 < 6 < 9,$$

with multiplicities

$$n_1 = 2,\quad n_5 = 2,\quad n_2 = n_3 = n_4 = n_6 = n_9 = 1.$$

We compute the rank incrementally.

At $a_1 = 3$, the symbols smaller than $3$ are $1$ and $2$.

If $1$ is placed first, remaining multiplicities give a count

$$\frac{8!}{2!,1!,1!,2!,1!,1!} = \frac{40320}{2} = 20160.$$

If $2$ is placed first, the same denominator occurs, giving another $20160$. Hence the first position contributes $40320$.

After fixing $3$, the remaining multiset is

$${1^2,2,4,5^2,6,9}.$$

At $a_2 = 1$, there is no symbol smaller than $1$, so the contribution is $0$.

At $a_3 = 4$, the remaining symbols smaller than $4$ are $1$ and $2$.

If $1$ is placed, the remaining multiset has size $6$ with only a duplicated $5$, giving

$$\frac{6!}{2!} = 360.$$

If $2$ is placed, the same value occurs, so the contribution is $720$.

At $a_4 = 1$, no contribution arises.

After processing $a_5 = 5$, the remaining multiset is ${2,6,9}$ together with one additional $5$ already accounted for, and the symbols smaller than $5$ are $1$ and $2$.

If $1$ is placed, the remaining three symbols are distinct, contributing $3! = 6$.

If $2$ is placed, the same value occurs, giving contribution $12$, hence total $48$.

At $a_6 = 9$, the symbols smaller than $9$ among the remaining multiset ${2,5,6,9}$ are $2$, $5$, and $6$.

Each choice leaves three distinct symbols, contributing $3! = 6$, hence total $18$.

At $a_7 = 2$, no smaller available symbol contributes.

At $a_8 = 6$, the only smaller available symbol is $5$, and placing it leaves a single completion, contributing $1$.

At $a_9 = 5$, no further contribution occurs.

Summing all contributions,

$$40320 + 720 + 48 + 18 + 1 = 41107.$$

The rank of $314159265$ under Algorithm L is therefore

$$\boxed{41107}.$$