most recent 30 from http://mathoverflow.net 2013-05-18T15:50:15Z http://mathoverflow.net/feeds/user/28190 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112195/max-of-words-with-restricted-total-content/112722#112722 Wouter Meeussen 2012-11-17T21:52:36Z 2012-11-17T21:52:36Z

<p>just for the bunch of Physicists: look at the Multiset as a partition, in your example {4,1,1}; specialising for word length 2: to get a maximal pairing, use a recursion by pruning. Pair off the first (=most frequent : the 4 a's) with one each of all the remaining parts. Note that the first 2 a's can be paired together, and any excess a's need to be pruned off. Then, define the residue as the decapitated partition in wich the k-1 last parts are decremented by 1, with k= number of parts-first part+1; then recurse on the residu while keeping track of the pruning count. In Mathematica 4.1 : (* start def *) residu[par : {1 ...}, p_:0] := p + Mod[Length[par], 2]; residu[par_?PartitionQ, p_:0] := Block[{f = First[par], l = Length[par], n = Tr[par], temp = p}, If[f - 1 > l, temp += f - 1 - l]; {DeleteCases[ Rest[par] - Table[If[k &lt; n - 1 - (f - 1), 0, 1], {k, l - 1}], 0], temp}]; prune[par_?PartitionQ, p_:0] := If[Max[par]&lt;=1, residu @@ {par, p}, prune @@ residu @@ {par, p}]; maxwords[par_?PartitionQ] := Floor[(Tr[par] - prune[par])/2]; (* end def *) Example: the 2+10^8 'th and 3+10^8 'th partitions of 100 (in reverse lexicographic order) are {20, 14, 8, 8, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2} :: maxwords=50 and {20, 14, 8, 8, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1} :: maxwords=49;</p> <p>generalising on length 3 can in principle be done along the same lines, by forming trio's {a,a,a}, {a,a,u},{a,a,v} .. etc, and pruning off excess a's, decapitation, tail decrement and recursion.</p>