0
$\begingroup$

Let $n$ be positive integer. Consider its integer partitions denoting as $(m_1,\cdots,m_k)$, where $m_1+\cdots+m_k=n$ and the order does not matter. We ignore the case of $(m_1,\cdots,m_k)=n$.

I am interested in

$$\binom{m_1}{2}+\cdots+\binom{m_k}{2}$$

My question is, what property of partition $m_1,\cdots,m_k\vdash n$ makes two quantities large or small? What is the tight upper bound of each of them, in the sense that it reflects difference on different partitions? If it is not possible to derive non-asymptotic bound, it is good enough to have asymptotic bound (for large $n$) in my case.

Here are few points I've thought of to the best of my ability:

  1. I am not familiar with integer partition and combinatorics, thus am not sure whether this problem is trivial or too hard. If this is too hard, could we somehow simplify the problem to make it solvable? As far as I could think of, maybe classify partitions according to certain property (maybe, the size of parts?).

  2. I think in general, this is a type of problem that asking: given a function on variables representing partitions, when does this function large or small, depending on the partition. Is there any other problem within this type such that I could refer to their methods?

  3. A graph interpretation of the quantity: Consider a graph with $n$ isolated nodes, now we add edges such that the resulting new graph is a cluster graph, i.e. a union of disjoint $k$ cliques (complete graph $K_n$ and $n$ isolated nodes as two extremes of cluster graph). The number of edges is equal to $\binom{m_1}{2}+\cdots+\binom{m_k}{2}$.

Moreover, it is pointed out that $\binom{m_1}{2}+\cdots+\binom{m_k}{2}=\frac{(\sum_{i=1}^km_k^2)-n}{2}$ in this paper.

  1. This problem seems can be seen as combinatorial optimization over integer partitions. I am not sure.

I would be very appreciate for any comment/suggestion.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Note that $\binom n2$ is superadditive, so the maximum is obtained by $\binom n2$ and the minimum by $\binom12 + ... + \binom12 = 0$. $\endgroup$
    – Daniel Weber
    Commented Aug 26, 2023 at 17:50
  • $\begingroup$ @CommandMaster I think so too. It seems the second largest is obtained by $\binom{n-1}{2}+\binom{1}{2}=\frac{(n-1)(n-2)}{2}$. $\endgroup$
    – tony
    Commented Aug 26, 2023 at 17:58
  • 5
    $\begingroup$ Let $\lambda=(\lambda_1,\lambda_2,\dots)$ and $\mu=(\mu_1,\mu_2,\dots)$ be two partitions of $n$, where $\lambda_1\geq \lambda_2\geq \cdots$ and similarly for $\mu$. Dominance (or majorization) order is defined on partitions of $n$ by $\lambda\leq\mu$ if $\lambda_1+\cdots\lambda_i\leq \mu_1+\cdots+\mu_i$ for all $i$. Superadditivity implies that your function $f(\lambda)$ strictly respects dominance, i.e., $\lambda<\mu\Rightarrow f(\lambda)<f(\mu)$. Thus $(n-1,1)$ does give the second largest value. But there can be incomparable partitions in dominance order, such as $(5,2,1)$ and $(4,4)$. $\endgroup$
    – Richard Stanley
    Commented Aug 26, 2023 at 19:42
  • 3
    $\begingroup$ This question is very similar to another. Namely, given $N$, what is the smallest $n$ such that $\binom{n_1}2+\cdots+\binom{n_k}2=N$ for some sequence with $n_1+\cdots+n_k=n$? It seems reasonable that the optimum will include the largest $n_i$ such that $\binom{n_i}2\le N$, but that's not always true. RW Robinson and I found 40 years ago that there are 148 exceptional values of $N$ of which the largest is 87140. As far as I can tell, we didn't publish it. $\endgroup$
    – Brendan McKay
    Commented Aug 27, 2023 at 2:04
  • $\begingroup$ @BrendanMcKay Thank you very much for your input! When I am thinking of this problem, I met another problem that similar to yours: given $n,N$, how many $(n_1,\cdots,n_k)$ are there such that $\binom{n_1}{2}+\cdots+\binom{n_k}{2}=N$, $n_1+\cdots+n_k=n$? Would this be solvable? $\endgroup$
    – tony
    Commented Aug 27, 2023 at 11:51

0

Reset to default

You must log in to answer this question.