max # of words with restricted total content 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!
 A: 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.  
A: 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).
A: 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
A: 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
A: 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.
A: erratum: read not "k< n-1 -(f-1) " but "k< l+1 -(f-1)"
