MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 subject describes the question better now...

# Acombinatoricsproblemmax#ofwordswithrestrictedtotalcontent

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)? 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!

3 added 156 characters in body

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)?

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!

2 deleted 15 characters in body

Suppose we have a multiset $\mathbf{M}$ on a finite alphabet $\alpha$. Given a length $L > |\mathbf{M}|$L$, what is the maximum number of different words of size $L$ we can produce (assuming, obviously, no replacement)? 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!

1