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

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 \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}$$).

• Hi @peter Taylore , Thanks very very much. I understood the first and the second but Can you explain a little about "a more efficient way...."I did not understand how it got and how it works. $W_k = 1 + \left\lfloor \frac{N-k}{k-1} \right\rfloor W_{k-1} + W_{(N - k) \bmod (k-1)} \approx \frac{N^{k-2}}{(k-1)!}$ – Richard Dec 2 '18 at 6:16
• @Peter Taylor , How we get $a_k .k \le N$ if we set $W_1=0$. ? – linkho Dec 2 '18 at 7:13
• @Peter Taylor , in your Rephrased ,shouldn't you write as this? " Can we find suitable weights $W_k$ such that for arbitrary $\lambda, \mu$ subject only to the constraint that $\lambda_K = \mu_K$, $$a_{\lambda_K} > b_{\mu_K} \implies \sum_i W_i a_i > \sum_j W_j b_j$$? " I think that's right, no? – linkho Dec 2 '18 at 7:24
• @linkho, your first question doesn't make sense. $a_k k \le N$ is a consequence of $\lambda$ being a partition of $N$. $\sum_{k=1}^\infty a_k k = N$ and all of the $a_k$ are non-negative integers. To your second question, the convention is that $\lambda_1 \ge \lambda_2 \ge \cdots$, so $K = \lambda_1 = \mu_1$. – Peter Taylor Dec 2 '18 at 7:58
• @Peter Taylor , yes .you are right. but I asked it because you wrote $\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$ , I thought you meant that $\lambda_1 = 1^{a_1}$ – linkho Dec 2 '18 at 8:09