# choose n letters to form possible words from m letters, restraint no letter should be used more than twice

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?

-
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

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$.

-
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

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.

-

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)!}$.

-

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.

-
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