0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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)!}$ $\endgroup$ – Richard Dec 2 '18 at 6:16
  • $\begingroup$ @Peter Taylor , How we get $a_k .k \le N$ if we set $W_1=0$. ? $\endgroup$ – linkho Dec 2 '18 at 7:13
  • $\begingroup$ @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? $\endgroup$ – linkho Dec 2 '18 at 7:24
  • $\begingroup$ @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$. $\endgroup$ – Peter Taylor Dec 2 '18 at 7:58
  • $\begingroup$ @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}$ $\endgroup$ – linkho Dec 2 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.