What is the appropriate weight ($W_k$) (for two arbitrary partitions)?

Question

I already asked a similar question, And from the answer I received, another question came to my mind.

A positive integer can be partitioned, for example, the number 7 can be partitioned into the following:

$ 7=6+1$ , $ \ \ 7=5+2$,$ \ \ 7=4+3$ ,$ \ \ 7=4+2+1$,$ \ \ 7=3+3+1$,$ \ \ 7=3+2+2$,...

suppose that

$n_k$:=the number of times that a number is used. ( For example, in partitioning $ 7 = 3 + 2 + 2$, we have $n_2 = 2$ and $ n_3 = 1$)

suppose $K$ as largest number in every partiotioning , For example, in partitioning $ 7 = 3 + 2 + 2$ , $K$ is $3$ , and in the partitioning $ 7 = 5 + 2 $ , we have $K=5$ .

suppose that $P1 $ and $P2$ are two partitions.

$n_k$:=the number of times that a number is used in partitioning $P1 $ .
$n'_k$:=the number of times that a number is used in partitioning $P2 $ .

$K$ as largest number in every partiotioning.

if The largest number in both partitions be the same.( I mean, for $P1 $ and $P2 $, the value of $K$ is the same. For example,$P1$ be $12 = 5 + 5 + 2 $and $P2$ be $12 = 5 + 4 + 3$ in both partitions $K$ is $5$.)

What is the appropriate positive weight ($W_k$) for two arbitrary partitions to maintain the following relationship?

$n_K \gt n'_K $ $\implies$ $\sum_{t=1}^T W_t n_t \gt \sum_{t=1}^T W_t n'_t$

thanks

Answer 1

Rephrased with more standard notation:

Suppose we have two partitions $\lambda, \mu \vdash N$ where $\lambda = \lambda_1 + \lambda_2 + \cdots = 1^{a_1} 2^{a_2} \cdots$ and $\mu = \mu_1 + \mu_2 + \cdots = 1^{b_1} 2^{b_2} \cdots$.

Can we find suitable weights $W_k$ such that for arbitrary $\lambda, \mu$ subject only to the constraint that $\lambda_1 = \mu_1$, $$a_{\lambda_1} > b_{\mu_1} \implies \sum_i W_i a_i > \sum_j W_j b_j$$?

Yes. A sufficient condition is that $W_k > \sum_{i=1}^{k-1} W_i n_i$ for any partition $1^{n_1} 2^{n_2} \cdots \vdash N$. (Actually this condition is stronger than needed: it guarantees that the lexicographically greater partition has a larger sum).

The simplest way to meet this condition is to set $W_k = (N+1)^{k-1}$, interpreting the frequency representation of the partition as a number in a base which is guaranteed to be larger than any of the digits.

A more efficient way would be to set $W_1 = 0$ and observe that $a_k k \le N$ so that for $k > 1$ we can set $W_k = 1 + \sum_{i=1}^{k-1} W_i \left\lfloor \frac{N}{i} \right\rfloor$.

The most efficient way to meet the condition given above would be to set $W_1 = 0$, $W_2 = 1$. For $W_3$, in the worst case we need to distribute $N-3$ among parts less than 3, so we get $W_3 = 1 + \left\lfloor \frac{N-3}{2} \right\rfloor = \left\lfloor \frac{N-1}{2} \right\rfloor$. In general, for $W_k$ in the worst case we have $\lambda = k + k + 1 + \cdots + 1$, $\mu = k + \nu$ where $\nu$ is the highest weight partition of $n-k$ into parts less than $k$. Since the "average" weight $\frac{W_k}{k}$ is increasing, $\nu$ will have as many parts as possible of size $k-1$, and one left-over part, so $W_k = 1 + \left\lfloor \frac{N-k}{k-1} \right\rfloor W_{k-1} + W_{(N - k) \bmod (k-1)}$ The dominant term is $\left\lfloor \frac{N-k}{k-1} \right\rfloor W_{k-1} \approx \frac{N-k}{k-1} W_{k-1}$ so by induction $W_k \approx \frac{N^{k-2}}{(k-1)!}$. (Actually we could perhaps say $W_k \approx \frac{N-k}{k-1} \cdots \frac{N-3}{2} = \frac{(N-3)^{\underline{k-2}}}{(k-1)!} = \frac{1}{k-1} \binom{N-3}{k-2}$).