Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $m$ letters (distinct letters), choose $n$ ($n < m$) letters to form words (the word doesn't need to be correct), and no letter can be used more than twice.

How many distinct word can be formed?

share|improve this question
1  
Do you mean that no letter is used more than once, as in the title, or that no letter is used more than twice, as in the question? –  Brian M. Scott Jun 26 '12 at 8:13
    
More than twice actually, sorry my mistake in the title –  Negative Zero Jun 26 '12 at 17:44
add comment

4 Answers

up vote 3 down vote accepted

If the constraint in the title is correct, the problem is quite easy: there are $\binom{m}n$ ways to choose which $n$ letters are used and $n!$ ways to arrange those $n$ letters, so the total number of words is

$$\binom{m}nn!=\frac{m!}{(m-n)!}=m^{\underline k}\;.$$

If the constraint in the question proper is correct, the problem is quite difficult.

Let $k=\lceil n/2\rceil$. The number $d$ of distinct letters in the word must satisfy $k\le d\le n$. For each of these values of $d$ there are $\binom{m}d$ ways to choose the distinct letters. In order to make a word of length $n$ we must use $n-d$ of these letters twice each and use the other $d-(n-d)=2d-n$ letters once each; there are $\binom{d}{n-d}$ ways to choose which $n-d$ letters are used twice each, so there are $$\binom{m}d\binom{d}{n-d}=\frac{m!}{(m-d)!(n-d)!(2d-n)!}$$ ways to select the letters.

Now we have to count the number of ways to arrange the selected letters. This is the multinomial coefficient $$\binom{n}{\underbrace{2,\dots,2}_{n-d\text{ times}},\underbrace{1,\dots,1}_{2d-n\text{ times}}}=\frac{n!}{2!^{n-d}1!^{2d-n}}=\frac{n!}{2^{n-d}}\;.$$ Thus, there are

$$\binom{m}d\binom{d}{n-d}\frac{n!}{2^{n-d}}\tag{1}$$

words of length $n$ using $d$ distinct letters. To get the total number of words, sum $(1)$ over the possible values of $d$:

$$\sum_{d=k}^n\binom{m}d\binom{d}{n-d}\frac{n!}{2^{n-d}}\;.\tag{2}$$

In fact you can take the summation from $d=0$ to $d=n$, since for $d<k$ the binomial coefficient $\binom{d}{n-d}=0$.

Now the question is whether $(2)$ has a nice closed form. We can rewrite it as

$$\begin{align*} \frac{n!}{2^n}\sum_{d=0}^n2^d\binom{m}d\binom{d}{n-d}&=\frac{n!}{2^d}\sum_{d=0}^n\frac{2^dm!}{(m-d)!(n-d)!(2d-n)!}\\\\ &=\frac{m!n!}{2^n}\sum_{d=0}^n\frac{2^d}{(m-d)!(n-d)!(2d-n)!}\;. \end{align*}$$

I do not at the moment see a closed form for this.

Added: The generating function is $$(1+x+x^2)^m=\left(\frac{1-x^3}{1-x}\right)^m\;,$$ and you want the coefficient of $x^n$.

share|improve this answer
    
What is the $m^{\underline k}$ in your first equation? –  Peter Phipps Jun 26 '12 at 9:20
    
@Peter: The falling $k$-th power, $m(m-1)\dots(m-k+1)$. –  Brian M. Scott Jun 26 '12 at 9:27
    
I've not seen that before, thanks. –  Peter Phipps Jun 26 '12 at 9:30
    
In the multinomial coefficient step: is the total number of letters supposed to be n instead of m? forming an n letters words with n-d number of letters use twice, and 2d-n letters use once. Or am I dreaming something... –  Negative Zero Jun 26 '12 at 18:53
    
$$\binom{m}{\underbrace{2,\dots,2}_{n-d\text{ times}},\underbrace{1,\dots,1}_{2d-n\text{ times}}}=\frac{m!}{2!^{n-d}1!^{2d-n}}=\frac{m!}{2^{n-d}}\;.$$ –  Negative Zero Jun 26 '12 at 18:58
show 1 more comment

This is not that difficult. If you need to use every letter once, you get $$ \left(\begin{array}{c} m \\ n \end{array} \right) n! $$ where the binomial coefficient comes from the possibilities to chose the letters and the $n!$ from their number of permutations.

share|improve this answer
add comment

The way of arranging $n$ letters such that no letter is used more than once to make a word n-length is $n!$. We don't have to worry about repetition since we know that the letters are distinct.

But now, it also turns into a 'choosing' question. We have $m$ letters to choose $n$ from, and we want distinct groups of such. That would be $m \choose n$.

By the Product Rule, we multiply both 'events' to get the total amount, which is

$$n! \cdot {m \choose n}$$

Which is $n!\cdot\frac{m!}{n!(m - n)!} = \frac{m!}{(m-n)!}$.

share|improve this answer
add comment

If the constraint is "not more than twice",then:
Let $i$ be the number of elements occurring twice in selected n elements,therefore,number of distinct elements = $(n-2i)+(i) = (n-i)$. Now, the number of ways of selecting $(n-i)$ elements out of $m$ = $mCn-i$ and number of permutations of these n elements = $\frac{n!}{2^i}$ giving total $mC(n-i).\frac{n!}{2^i}$.Now,Summation of this term for i=0 to $\floor{n/2}$ will give the required solution.

share|improve this answer
    
It is coming out to be $\frac{m!.3^n}{2^{n+1}}$(not sure with the computation). –  Aang Jun 26 '12 at 10:41
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.