0
$\begingroup$

So here is my problem. If we have a vector $\textbf{x}=(x_1,...,x_n)$ where $x_j \in \mathbb{N}$ for each $j \in \{1,...,n\}$, then is there a way to maximize the value of the following combinatorial identity:

$\sum_{j=1}^{n}\binom{2x_j}{2}$?

The problem here is that we do not know anything about the vector $\textbf{x}$ except for the fact that the entires are all natural numbers and that the constraint is $\sum_{j=1}^{n}x_{j}=k$ where $k\in \mathbb{N}$ is fixed.

$\endgroup$
2
  • 2
    $\begingroup$ The binomial coefficient $\binom{2x}{2} = x(2x - 1)$. This goes to infinity as $x$ goes to infinity, so you can make it as big as you want. Are you not missing some assumption? $\endgroup$
    – MEEL
    Commented Feb 22, 2021 at 2:36
  • $\begingroup$ Additionally, you use the phrase "combinatorial identity", but you in fact are working with a "combinatorial expression", i.e. there is no equals sign. $\endgroup$
    – Joshua P. Swanson
    Commented Feb 22, 2021 at 3:27

2 Answers 2

Reset to default
1
$\begingroup$

Note that whenever $x$ and $y$ are positive integers, $$ \binom{2(x+y)}2> \binom{2x}2+\binom{2y}2 $$ Therefore, if you have a vector $(x_1,\dots,x_n)$ where there are two nonzero components, then you get a larger value of $\sum_i \binom{2x_i}2$ by combining those two nonzero components into one. This means that the vector which attains the optimum must have only one nonzero component, so it is some permutation of $(k,0,0,\dots,0)$.

$\endgroup$
0
$\begingroup$

You want one component of $\bf x$ to have value $k$ and all the rest to be $0$. Because the term ${2x_j \choose 2}=x_j(2x_j-1)$ you will increase the sum every time you move $1$ to the largest component from any other component. This stops when one component equals $k$.

$\endgroup$

You must log in to answer this question.