Sunday, 23 September 2007

co.combinatorics - Why are multinomial coefficients with same entropy equal? (usually)

Suppose p1,ldots,pd and q1,ldots,qd are positive real numbers such that



p1+cdots+pd=q1+cdots+qd=n



and



p1logp1+cdots+pdlogpd=q1logq1+cdots+qdlogqd



Then the following seems to hold



fracn!p1!cdotspd!=fracn!q1!cdotsqd!



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}]]

No comments:

Post a Comment