Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is the sort of problems in combinatorics with a rather innocent look that turn out to be quite challenging - at least for a bunch of physicists! :)

Suppose we have a multiset $\mathbf{M}$ on a finite alphabet $\alpha$. Given a length $L$, what is the maximum number of different words of size $L$ we can produce (assuming, obviously, no replacement -- (EDIT: i.e. no re-use of elements of $M$ (?)))?

Let me further specify the problem with a simple example. Now we take $\alpha=\{a,b,c \}$ and $\mathbf{M}=\{a,a,a,a,b,c\}$. Taking $L=2$, we could have, for instance, $W_{1}=\{ aa,bc\}$ or $W_{2}=\{ab,ac,aa\}$. In this case it is easy to see that we cannot form more than 3 different words.

Perhaps someone more familiar with combinatorics than me could give the correct phrasing to the problem!

share|improve this question
1  
I conjecture that you don't really mean $L>|M|$. –  Andreas Blass Nov 12 '12 at 18:18
    
Yes, sorry. Fixed. –  Pluvio Nov 12 '12 at 18:20
    
Nice problem! I'd suggest starting by considering the case $|\alpha|=2$ and $|M| = KL$ for some integer $K$. Then your question more or less reduces to asking if there exist $K$ distinct binary strings of length $L$ that collectively use a predetermined number of 0's and 1's. This already looks nontrivial to me, but perhaps tractable, and may give some insight into the general problem. –  Timothy Chow Nov 14 '12 at 16:13
1  
@Pluvio The precise answer in full generality is certainly out of reach. How much do you really need to know? @Timothy $\alpha=2$ case is simple. Assume that you have $n$ zeroes and $N$ ones with $n\le N$. Try to form as many words as possible using as few zeroes as you can until you need to use more than $n$ at the next step (greedy algorithm). If you use not more than $N$ ones by the end, this is your answer. If you use more than $N$ ones, then it is $[\frac{n+N}L]$ (just take that many first words in the original list and start moving them up replacing 0 with 1 in one word every time). –  fedja Nov 17 '12 at 0:36
add comment

6 Answers

You can probably get pretty close to the answer with linear programming. We can restate the problem in terms of an integer linear programming problem -- suppose $M$ has $n_1$ copies of the letter a, $n_2$ of b, and so on. There are $$K_{c_1,\dots, c_k}=\frac{(\sum c_i)!}{c_1!\dots c_k!}$$ ways to make a word with $c_1$ a's, $c_2$ b's, etc. So if $x_{c_1,\dots, c_k}$ is the unknown number of words in $W$ with the given number of each type of letter, we have two sorts of constraints. First, $$x_{c_1,\dots, c_k}\le K_{c_1,\dots, c_k},$$ (all the words are distinct) and second, $$\sum c_i x_{c_1,\dots, c_k}\le n_i$$ (you don't use more than $n_i$ of each letter.) You want to maximize $\sum x_{c_1,\dots, c_k}$ subject to these constraints and subject to the $x$'s being integers. If you allow the $x$'s to be real numbers, this is just a linear programming problem, and there are algorithms to solve it. My guess is that the solution over the reals is probably close to the solution over the integers.

share|improve this answer
add comment

Often similar problems are treated by Transfer Matrix method in enumerative combinatorics, see R.Stanley's book, Sect. 4.7. In particular 4.7.7 and 4.7.8 can in principle help here, if you reformulate your problem as a problem of enumerating length $L$ sequences from $\alpha$ with forbidden factors (i.e. patterns). E.g. in your 1st examples the forbidden factors are $bb$ and $cc$.

However, it looks as if in your examples you do not allow your symbols being re-used in different words (is this what you mean by no replacement?), so this is actually something rather different. You appear to ask for the maximum number of "ordered" bins of size $L$ each, where you pack elements of $M$ in such a way that no two bins get the same ordered content. Note that it is easy to solve if the multiplicities of the elements of $\alpha$ in $M$ are small, compared to $L$. In general, a greedy approach might produce good results: you try to get rid of elements of $\alpha$ with high multiplicity first, by packing as many of them as possible into one bin (e.g. you would produce your $W_2$ by packing $aa$ first, then $ab$, then $ac$). It could even happen to give you an optimal packing all the time (I am not convinced that this is a computationally difficult problem).

share|improve this answer
add comment

First suppose that L=2. In this case imagine that each element of $\alpha$ is the vertex of a graph and its multiplicity in M is its required degree. (Except that you also allow words like aa, moreover, ab and ba count distinct, but I don't think this really changes the problem.) So whether we can produce |M|/L words or not depends on whether the given sequence is graphic or not. See http://mathworld.wolfram.com/GraphicSequence.html

Now if L>2, then we don't know the answer to the corresponding hypergraph problem, so probably also your problem is hard. (In the sense that it is probably NP-hard.) See http://www.math.uiuc.edu/~west/regs/hypergraphic.html

share|improve this answer
    
Interesting. I am in fact interested not in the proposition " $|M|/L$ different words of length $L$ can be formed with this given multiset " but in the \textit{maximum} number of such different words - and yes, words with repeated letters are allowed. I also believe this is an NP-hard problem... –  Pluvio Nov 12 '12 at 20:30
    
If you have M/L distinct symbols, then you can achieve the maximum. The problem gets hard only for small values of L and very few distinct symbols. Even then, if you have L occurences of each symbol, you can get L distinct words for each pair (from a partition into pairs) of symbols. So the cases where the maximum is not achievable seem pretty rare to me. Gerhard "Ask Me About System Design" Paseman, 2012.11.12 –  Gerhard Paseman Nov 12 '12 at 21:09
    
@Pluvio: Yes, but if it is already NP-hard to decide whether M/L words can be formed, then maximizing the number of words is also NP-hard, as M/L is a trivial upper bound. Also, if you are looking for a NP-hardness result, then maybe you should ask your question on cstheory.stackexchange.com –  domotorp Nov 12 '12 at 21:31
    
@Domotorp: yes, I understand. My gut feelings say that this is perhaps analytically intractable, but I am largely ignorant about combinatorics in general, so perhaps I am wrong. –  Pluvio Nov 14 '12 at 14:42
add comment

If you know L is small and M/L is large compared to the number of symbols available, you might start with crude estimates such as $A^L$ words requiring $LA^{(L-1)}$ symbols of each kind from an alphabet of size A. If A=2 you can use partial sums $\sum \binom{L}{i}$ to guess how many words you get using a sea of b's and $\sum i\binom{L}{i}$ many a's. Of course it gets more complex with more letters, but you could use the above result as a sort of multiplier. For exact estimates for every case, that is likely to be NP, possibly NP complete.

Gerhard "Ask Me About System Design" Paseman, 2012.11.16

share|improve this answer
add comment

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 < n - 1 - (f - 1), 0, 1], {k, l - 1}], 0], temp}]; prune[par_?PartitionQ, p_:0] := If[Max[par]<=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;

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.

share|improve this answer
add comment

erratum: read not "k< n-1 -(f-1) " but "k< l+1 -(f-1)"

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.