0
$\begingroup$

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?

  • 0
    More than twice actually, sorry my mistake in the title2012-06-26

4 Answers 4

3

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

  • 0
    @NegativeZero: Oops. Yes, you’re right; I’ll have to go through and fix that. (I’d have used $n$ for the number of letters and $m$ for the word length, and apparently I inadvertently did so at that point.)2012-06-26
0

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.

0

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

0

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.

  • 0
    It is coming out to be $\frac{m!.3^n}{2^{n+1}}$(not sure with the computation).2012-06-26