Htykuut

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

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 leftlfloor frac{N}{i} rightrfloor$.

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 + leftlfloor frac{N-3}{2} rightrfloor = leftlfloor frac{N-1}{2} rightrfloor$. 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 + leftlfloor frac{N-k}{k-1} rightrfloor W_{k-1} + W_{(N - k) bmod (k-1)}$ The dominant term is $leftlfloor frac{N-k}{k-1} rightrfloor 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}$).