How many distinct 12-letter “words” are able to be formed from the string of letters “ABBBBBBBBBBBBBBBBBCDEFGHIJKLMOPQRSTUVWXYZ”

combinationscombinatorics

So this is a follow up on a previous question I asked. Previously, I was asking how many ways there were to take a 4-letter "word" from the word BUBBLES, where two Bs are indistinguishable. If you want to take a look at that post, here is the link: How many ways are there to organize the letters in the word BUBBLES into a 4-letter permutation? . Now I wanted to see a more general formula for these kinds of problems, so I figured a new post with a bit more of a complex example would help to bring some attention to it (and someone also suggested this in a comment to that previous post). The new question goes as follows:

Given the string of letters ABBBBBBBBBBBBBBBBBCDEFGHIJKLMOPQRSTUVWXYZ (that's 17 Bs and the other 25 letters of the alphabet), how many distinct ways are there to pick a string of 12 letters from it? Assume that order (so AB is different from BA) and letter (so the letters A and B are able to be told apart from each other) is the only distinguishing factor (i.e. two Bs are the same as each other).

So far, I've taken a look at a few scenarios for this. The thing that I figured would be most important is the amount of Bs that would end up going in the final 12-letter word, so I took a look at that first. Now if we start at all 12Bs going into the word (the absolute maximum), we can only get $1$ possibility. But if we drop a B, lowering the count to 11Bs, then we will have one extra spot for another letter. I figured this spot could take on any of the $12$ spaces between or besides the 11Bs, and would have to be one of the $25$ remaining letters, so $12 \cdot 25$. But from here, I can proceed to get more casework, but I'm not sure that's very feasible here. And I am not seeing an obvious formula that I can derive from those steps. Does anyone have any formulas or ideas to solve this problem? And if so, is there a specific explanation behind it or even a way to derive it?

Best Answer

Suppose that your word contains $i$ B's. There are then $\binom{25}{12-i}$ ways to select the other letters to use. Then there are $12!/i!$ ways of ordering the $12-i$ distinct letters and the $i$ copies of B. Thus, there are a total of $$\frac{25!}{(12-i)!(13+i)!} \cdot \frac{12!}{i!}$$ words of this form.

We wish to find $$\sum_{i=0}^{12} \frac{25! \cdot 12!}{(12-i)!(13+i)!i!}.$$

Unfortunately, such a sum does not have a simple closed form. You may find a (terrible) 'closed form' in terms of hypergeometric functions, but the most efficient way I can see to evaluate this sum is to just do it.

Related Solutions

Probability – How Many Distinct n-Letter Words Can Be Formed from a Set of k Letters with Repetitions?

There is a fairly systematic way to work this type of question. You were specifically wondering about:

How many 4-letter words can be formed from the letters: ABBCCC?

First, you write the 'source partition' for your word:

[C,B,A]
[3,2,1]  <-- this is the `source partition`

Note that the source partition provides for 1 triple, 1 double, and 1 single. Corresponding to that, you write every possible 'target partition' of 4-letters.

[3,1]    requests one triple and 1 single
[2,2]    requests 2 doubles
[2,1,1]  requests one double and 2 singles

For each 'target partition', you write an expression that gives the number of ways that the given target type can occur. An example of the target type [3,1] is:

CCBC                                   # type [3,1]

The expression for that type is:

nCr(1,1)*nCr(2,1) * fac(4)/fac(3)

'nCr( n, r)' is the function for 'combinations', which gives the number of ways you can make a unique selection from n distinct things, taking r at a time. 'fac( n)' is the function for the factorial of n.

Note that source [3,2,1] provides 1 triple, and target [3,1] requests 1 triple. Hence nCr(1,1). After the triple is used up, the source [3,2,1] can provide 2 singles, and the target [3,1] requests 1 single. Hence nCr(2,1) The call to fac(4), in each expression, always corresponds to the 4-letter word. Any division, if it occurs in an expression, corresponds to each multiple request of the corresponding target partition. That's all there is to the method, but it isn't always easy to get every last detail correct. The entire computation, as I did it in the programming language Python, follows:

# The `source partition` for the word 'ABBCCC' is:
#                 [3,2,1]
#                                                # target
w = 0                                            # ------
w += nCr(1,1)*nCr(2,1) * fac(4)/fac(3)           # [3,1]
w += nCr(2,2)          * fac(4)/(fac(2)*fac(2))  # [2,2]
w += nCr(2,1)*nCr(2,2) * fac(4)/fac(2)           # [2,1,1]
#
# The answer is 38

[Math] How many 5-letter words from ABRACADABRA

Let's only consider the case when there is only one pair of repeated letters, such as VVXYZ.

You're correct to think that VVXYZ has $5!$ configurations with $2!$ repeated letters, so the number of ways of arranging VVXYZ is $\frac{5!}{2!}$.

But we're not just arranging VVXYZ in this example. There are many ways to get one pair of repeated letters, such as AABRC or BBRCD or RRCDA...

So there are 3 possibilities for the double-letter pair (either AA or BB or RR) - that's why you need to multiply by 3.

Then, for each double-letter pair, there are four possibilities (technically, 4C3) for the remaining letters (such as AABRC, AABRD, AABCD, AARCD). That's why you also need to multiply by 4.

Best Answer

Related Solutions

Probability – How Many Distinct n-Letter Words Can Be Formed from a Set of k Letters with Repetitions?

[Math] How many 5-letter words from ABRACADABRA

Related Question