# Why are multinomial coefficients with same entropy equal? (usually)

Suppose $p_1,\ldots,p_d$ and $q_1,\ldots,q_d$ are positive real numbers such that

$$p_1+\cdots+p_d=q_1+\cdots+q_d=n$$

and

$$p_1 \log p_1+\cdots+p_d\log p_d=q_1 \log q_1+\cdots+q_d \log q_d$$

Then the following seems to hold

$$\frac{n!}{p_1!\cdots p_d!}=\frac{n!}{q_1!\cdots q_d!}$$

why?

Edit: JBL correctly notices that it doesn't always hold. I just didn't go far enough. Still, it's surprising to me that it holds so frequently.

If we put a black disk at x,y if equality seems to hold (in machine precision) for x=n,y=d, and positive integer coefficients, it'll look like this

Red circle is JBL's example. Blue circle is n=18,d=3 which fails for (12,3,3) and (9,8,1).

docheck[n_, d_] := (
coefs = IntegerPartitions[n, {d}, Range[1, n]];
entropy[x_] := N[Total[# Log[#] & /@ x]];
groupedCoefs = GatherBy[coefs, entropy];
allEqual[list_] := And @@ (First[list] == # & /@ list);
multinomials = Apply[Multinomial, groupedCoefs, {2}];
And @@ (allEqual /@ multinomials)
);
vals = Table[docheck[#, d] & /@ Range[1, 30], {d, 1, 20}];
Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, 30}]]


Edit: Updated version that does exact checking and allows coefficients with 0 components. Still only one example of failure for d=3.

docheck[n_, d_] := (coefs = IntegerPartitions[n, {d}, Range[0, n]];
entropy[x_] := Exp[Total[If[# == 0, 0, # Log[#]] & /@ x]];
groupedCoefs = GatherBy[coefs, entropy];
allEqual[list_] := And @@ (First[list] == # & /@ list);
multinomials = Apply[Multinomial, groupedCoefs, {2}];
And @@ (allEqual /@ multinomials));
maxn = 30; maxd = 20;
vals = Table[docheck[#, d] & /@ Range[1, maxn], {d, 1, maxd}];
Graphics[Table[Disk[{n, d}, If[vals[[d, n]], .45, .1]], {d, 1, Length[vals]}, {n, 1, maxn}]]

-
Can you construct two partitions of $n$ with the same entropy that are not rearrangements of each other? (Also, why do you apply Permutations over IntegerPartitions? Every permutation of a partition of $n$ clearly has the same entropy and multinomial coefficient, so you can just take what IntegerPartitions spits out instead.) – dvitek Sep 1 '10 at 21:04
Permutations/IntegerPartitions is a Mathematica speed trick for listing all multinomial coefficients --stackoverflow.com/questions/3563762/… – Yaroslav Bulatov Sep 1 '10 at 21:09
but yes, you could make the checking faster by ignoring permutations – Yaroslav Bulatov Sep 1 '10 at 21:10
After all, $p_1 \log p_1+\cdots+p_d\log p_d=c$ defines a certain hypersurface in $\mathbb{R}_+^d$. In a sense, it is more surprising that in some cases it can meets more than one point of the lattice $\mathbb{Z}^d$, as in JBL's example. – Pietro Majer Sep 1 '10 at 23:49
Note that for the entropies to be equal, any prime that divides one of the $p_i$ must also divide one of the $q_i$, and vice versa. That alone may rule out many chances. Note that the blue and red circles are on the same diagonal of slope 1. Does absence of a black disk indicate existence of a counterexample or just ignorance of the status? – Gerry Myerson Sep 2 '10 at 0:02

It's false: consider the two nine-part partitions $\langle 8, 2^8\rangle$ and $\langle 4^5, 1^4\rangle$ of $24$, where exponentiation represents multiplicities. They have equal entropy, but not the same multinomial coefficient.

(I have no idea whether this example is minimal. I generated it by considering partitions whose parts are all powers of 2, since this simplifies the entropy condition. If we allow only three powers of $2$ to appear in our equations, we must solve $a + b + c = d + e + f$, $a + 2b + 4c = d + 2e + 4f$ and $2b + 8c = 2e + 8f$, with unique solution $d = a, e = b, f = c$. However, if we allow our partitions to include 1, 2, 4 and 8 then we still have only three constraints but now four variables, and we can find nontrivial solutions.)

-

The asymptotics of multinomial coefficients for large values of $n$ can be expressed in terms of entropy using Stirling's formula to find $\ln(p_1!p_2!\ldots p_n!)$ approximately. This approximation works well even for small values of $p_k$'s.

-
Terence Tao gives a statement of this approximation for binomial coefficients here: terrytao.wordpress.com/2010/01/02/… – Qiaochu Yuan Sep 2 '10 at 1:57
Stirling's implies that coefficient with entropy H has value approximately Exp[n H], but that approximation seems too loose to explain observed closeness of equal entropy coefficients. IE, for d=3, n=18, that approximation can be off by a factor of 10, yet coefficients with equal entropy tend to be equal – Yaroslav Bulatov Sep 2 '10 at 3:33

EDIT

You still have not given interesting examples of equal multinomal coefficients with equal entropy. I'm not saying there aren't any (or many) but it would help to see some. Or even interesting examples (especially for d=3) with at least the same prime divisors showing up.

Either of these tasks is pretty easy (I added the condition disjoint which is no loss) :

1. find n and d and two disjoint d-tuples of integers A and B both with sum n and $\prod_A a!=\prod_B b!$ (equal multinomials with the same n and d)
2. find n and d and two disjoint d-tuples of integers A and B with sum n $\prod_A a^a=\prod_B b^b$ (equal entropy)

I'd venture that most of the time a solution of one is not a solution of the other.

For equal entropy: There is a 4 parameter family of solutions to the equal entropy problem (usually with d large) using 1,2,3,4,6,8,9,12 spread out between the sets A and B (Choose the number of 4s,8s,9s and 12s and where they go, there is a unique way to choose the 1s,2s,3s and 6s) . If one of the sets uses 12 then there will be a discrepancy in the multinomial coefficients related to the prime 11.

for equal multinomials: $<x,y,xy-1>$ and $<x-1,y-1,xy>$ give equal product of factorials so $<x,y,xy-1,u-1,v-1,uv>$ and $<x-1,y-1,xy,u,v,uv-1>$ gives a d=6 case of the multinomial problem. It is easy to arrange for cancelation. Set u=y and v=xy-1 to get a d=3 multinomial $<x,xy-2,(xy-1)y>$ and $<x-1,xy,(xy-1)y-1>$. Here there will be primes present in one side but not the other so even the shifted entropy won't be exactly the same.

previous answer - The missing black dot at n=19,d=4 is from $<6,6,6,1>,<9,2,4,4>$ which have equal entropy yet the corresponding multinomial coefficients have ratio 25/28. - The missing black dot at n=20,d=5 is from $<8,3,3,3,3>,<6,6,4,2,2>$ which have equal entropy yet the corresponding multinomial coefficients have ratio 21/20 . - What are some interesting examples of equal entropy and equal multinomial coefficients? - The ratio of similar binomial coeffcients will usually consist of powers of relatively small primes so coincidences are likely. - There are an enormous number of equal multinomial coefficients and they do not lead to equal entropy in most cases (not that you say they will).

-
$(19,4)$ and $(20,5)$ lie on that same diagonal as the red and blue circles in the first diagram. Time to look at $(21,6)$, $(22,7)$, ...? – Gerry Myerson Sep 2 '10 at 6:51
btw, the grid of n,d for which equality always holds seems to get more filled out if we offset entropy by 1/2, ie, look for difference in coefficient values for which the following quantity is equal $(k_1−1/2)\log k_1+⋯+(k_d−1/2)\log k_d$ yaroslavvb.com/upload/multinomial-equality3.png – Yaroslav Bulatov Sep 2 '10 at 7:46
Since Stirlings formula is $ln(k!)=(k+1/2)ln(k)-k+ln(2 \pi)/2$ (approx) I would expect $(k+1/2)log(k)$ to be even better. But do you have examples? – Aaron Meyerowitz Sep 2 '10 at 20:50