Let $\operatorname{Part}(n)$ be the set of integer partitions of $n$.


A partition $p \in \operatorname{Part}(n)$ has $k$ summands and $d$ distinct summand $n\_i$, with $d \leq k$ and $d$ frequencies $f\_i$ such that $\sum\_i^d f\_i \cdot n\_i = n$.


Notice that $\sum\_i^d f\_i = k$.


The probability of $n\_i$ within a given partition $p$ is thus $P(n\_i) = f\_i/k$.


This allows to define an entropy function on $\operatorname{Part}(n)$, $H(p) = -\sum\_i^d P(n\_i)\cdot \log(P(n\_i))$.


Note that I etched this definition of $H$ of a partition of $n$ myself so that it may be non-standard.


I am looking for the maximal value of $H$ for a given $n$: $H\_{\max}(n)$.


I have crunched some values for small $n$ by enumerating $k$-compositions of $n$ and computing $H$ on the underlying partition.


The minimum of $H$ is $0$ and occurs notably when $k=1$ or $k=n$. The maximum is more interesting. For $n=12$, it apparently occurs when $k=4$. For $n=16$, when $k=5$. For $n=24$, when $k=6$. For $n=32$, when $k=7$.


I was initially looking for the maximum values for given $k$ and $n$. I am now interested in the maximum for a given $n$, regardless of $k$.


I believe this may have musical applications. My intent is to filter rhythms by the entropies of their underlying partitions using fuzzy logic. Having an easily computable function for the maximum value of $H$ would make it possible to normalize its values for a specific $p$ and filter by percentage for any $n$.


Next thing I'll try is to compute $H\_{\max}(n)$ for small $n$ then fit the curve with some regression model.


**UPDATE:**
Enlightened by *aorq*'s comment on how to obtain the optimal $k$ given $n$, I was able to compute $H\_{max}(n)$ quite rapidly for the specific values I wanted by enumerating the compositions of $k$ to obtain frequencies $f\_i$ that maximize $H$.


Here are the values if you are interested:


$n=12, k=4, H\_{max}=1.3862943611198906$


$n=16, k=5, H\_{max}=1.6094379124341005$


$n=24, k=6, H\_{max}=1.7917594692280547$


$n=32, k=7, H\_{max}=1.945910149055313$


$n=96, k=13, H\_{max}=2.5649493574615376$


$n=192, k=19, H\_{max}=2.9444389791664403$


$n=384, k=27, H\_{max}=3.2958368660043296$


Thanks again sir!!


**OTHER UPDATE:** $H\_{max} = \log(\lfloor (\sqrt{1+8n}-1)/2\rfloor)$ or $\log(k)$.



Maximal entropy of integer partitions of $n$
To summarize and make more complete what has already been figured out:


**Claim:** Let $T\_i = {i+1 \choose 2}$ for all $i$. Let $j$ be the integer such that $T\_j \leq n < T\_{j+1}$. Then $H\_{max}(n) = \log(j)$.


*Proof:* Write $T\_j = 1 + \dots + (j-1) + j$. By increasing the last summand, we obtain a partition of $n$ containing $j$ unique summands each with frequency one, achieving entropy $\log(j)$. On the other hand, there is no partition of $n$ with greater than $j$ unique summands. If there were, then $n$ would be at least $1+\dots +(j+1) = T\_{j+1}$. As every partition contains at most $j$ unique summands, $H\_{max}(n)$ is at most the maximum entropy of a distribution on $j$ items, $\log(j)$.




---


*More detailed proof.* Given a partition $p \in Part(n)$, let $d\_p$ be the number of distinct summands and $P\_p$ the induced probability distribution. Observe that the support size of $P\_p$ is $d\_p$, so $H(p) = H(P\_p) \leq \log(d\_p)$. *(Recall $H(p)$ is defined to be the Shannon entropy of $P\_p$.)*


We have $\max\_{p \in Part(n)} d\_p = j$ where $j$ is defined in the claim. To prove this, observe that if $d\_p \geq j+1$, then $n \geq 1+2+\cdots+(j+1) = T\_{j+1}$, a contradiction. (In more detail, for any partition of $n$ containing at least $j+1$ distinct summands, we can sort them ascending and obtain $n \geq n\_1+\cdots+n\_{j+1}$ with $n\_i \geq i$ for all $i$, hence $n \geq T\_{j+1}$.)


By the above claims, $H\_{\max}(n) \leq \max\_{p \in Part(n)} \log(d\_p) = \log(j)$. We now exhibit a partition $p$ of $n$ achieving this upper bound. The partition is $1+\cdots+(j-1)+x=n$, where $x = n - T\_{j-1} = n - (1+\cdots+(j+1))$. By assumption of $n \geq T\_j$, we have $x \geq j$, so $x$ is distinct from all other summands, which are all pairwise distinct. So $d\_p = j$ and $P\_p$ is the uniform distribution on $\{1,\dots,j-1,x\}$. We have $H(p) = H(P\_p) = \log(j)$.


We have shown that $H\_{\max}(n) \leq \log(j)$, and found a partition $p$ of $n$ with $H(p) = \log(j)$, so $H\_{\max}(n) = \log(j)$.


