minimal even partition among the ones $\geq$ a given partition

89 Views Asked by At

Let $N$ be an even integer. A partition of $N$ is a sequence $(a_1,a_2,\cdots, a_N)$ of integers such that $a_1 \geq a_2 \geq \cdots \geq a_N \geq 0$, and $\sum_{j=1}^Na_j =N$.

Let $\mathscr P_N$ be the set of partitions of $N$. A partition $\nu \in \mathscr P_N$ is said to be even if $\nu = (\nu_1,\nu_2,\cdots \nu_N)$ satisfy $\nu_i$ is even for $i=1,2,\cdots, N$.

The order "$\leq$" is defined as follows. Let $\nu^1 =(\nu^1_1,\nu^1_2,\cdots,\nu^1_N)$, $\nu^2=(\nu^2_1,\nu^2_2,\cdots,\nu^2_N) \in \mathscr P_N$. We say that $\nu^1 \leq \nu^2$ if $\sum_{j=1}^i \nu^1_j \leq \sum_{j=1}^i \nu^2_j$ for $i =1,2,\cdots,N$. (It is easy to notice that $\mathscr P_N$ has a unique maximal element, which is $(N,0,0,\cdots,0)$, and a unique minimal element, which is $(1,1,\cdots,1)$.)

Let $\lambda \in \mathscr P_N$. Let $$\Gamma =\{\nu \in \mathscr P_N | \lambda \leq \nu \text{ and } \nu \text{ is even}\}.$$

Then does $\Gamma$ always have a unique minimal element (under "$\leq$")? Is there any standard process for me to find a minimal element of $\Gamma$ from $\lambda$?

Thanks to everyone.

1

There are 1 best solutions below

3
On

To find a minimal element:

For convenience, let $\lambda=(\lambda_1, \lambda_2,\cdots, \lambda_N).$
If $\lambda $ is itself even then it is a minimal element. Otherwise, at least one $\lambda_i $ is odd. Since N is even, and $\sum_{i=1}^{N}{\lambda_i}=N$, number of $\lambda_i $ which are odd, is even. Now to find the minimal element $m=(m_1, m_2,\cdots, m_N)$ from $\lambda $:
Step-1: Keep/Retain all the even $\lambda_i$ as such in $m .$
Step-2: Add 1 to the first odd $\lambda_j$ and subtract 1 from the immediate next odd $\lambda_k .$ Do this till all $\lambda_i' s $ become even.
Step-3: Rearrange the resulting values so that $m_1\geq m_2\geq....\geq m_N.$ Does it help you?