Timeline for Sum of square of parts, and sum of binomials over integer partition
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2023 at 15:26 | comment | added | Max Alekseyev | @tony: My answer does say so if you read it carefully, except that $N$ is the sum of binomial coefficients, not squares. As for your current question, it loos like the paper you cited answers it. If not, please clarify why you are not happy with their results. | |
| Aug 28, 2023 at 12:51 | comment | added | tony | @MaxAlekseyev For this problem, I think what is needed is $\sum_{n_1+\cdots+n_k=n \\ n_1^2+\cdots+n_k^2=N\\1\leq k\leq L}\binom{L}{k}\binom{n}{n_1,\cdots,n_k}$ instead of $\sum_{n_1+\cdots+n_k=n\\1\leq k\leq L}\binom{L}{k}\binom{n}{n_1,\cdots,n_k}$ | |
| Aug 27, 2023 at 16:09 | comment | added | Max Alekseyev | @tony: This what we sum over, but we do not assume that we know them in advance. | |
| Aug 27, 2023 at 15:58 | comment | added | tony | @MaxAlekseyev In this answer $\sum_{n_1,\cdots,n_k}\binom{L}{k}\binom{n}{n_1,\cdots,n_k}$ we have to know the exact $(n_1,\cdots,n_k)$ otherwise we couldn't compute it. | |
| Aug 27, 2023 at 15:44 | comment | added | Max Alekseyev | @tony: No. It assumes that we are given only $n,N$. | |
| Aug 27, 2023 at 15:38 | comment | added | tony | @MaxAlekseyev Thanks! but I think This problem assumes we already know $(n_1,\cdots,n_k)$ instead of $\sum_{i=1}^k\binom{n_i}{2}$. | |
| Aug 27, 2023 at 14:39 | comment | added | Max Alekseyev | @tony: I've addressed your "another problem" in this answer to your previous question. | |
| Aug 27, 2023 at 14:36 | comment | added | Max Alekseyev | Relevant question: mathoverflow.net/q/444754 | |
| Aug 27, 2023 at 11:51 | comment | added | tony | @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? | |
| Aug 27, 2023 at 2:04 | comment | added | Brendan McKay | 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. | |
| Aug 26, 2023 at 20:57 | history | edited | tony | CC BY-SA 4.0 |
added 203 characters in body
|
| Aug 26, 2023 at 19:42 | comment | added | Richard Stanley | 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)$. | |
| Aug 26, 2023 at 17:58 | comment | added | tony | @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}$. | |
| Aug 26, 2023 at 17:55 | history | edited | tony | CC BY-SA 4.0 |
added 44 characters in body
|
| Aug 26, 2023 at 17:50 | comment | added | Daniel Weber | Note that $\binom n2$ is superadditive, so the maximum is obtained by $\binom n2$ and the minimum by $\binom12 + ... + \binom12 = 0$. | |
| Aug 26, 2023 at 17:12 | history | asked | tony | CC BY-SA 4.0 |