0
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ It might be easier to separate the problem into 13 cases, with 0 B's, 1 B's, 2 B's, ..., 12 B's. Do you know the formula for each of these cases? $\endgroup$ – player3236 Oct 25 '20 at 4:30
  • $\begingroup$ Hint: In the previous problem, the general formula was $$T(k) = \binom{4}{4-k} \times \frac{4!}{k!}.$$ $\endgroup$ – user2661923 Oct 25 '20 at 4:33
  • $\begingroup$ Yeah I figured something pretty similar would apply for this problem. So we would end up getting $T(k) = {25 \choose 25 - k} \cdot \frac{25!}{k!}$. But I'm not sure how we can easily add that together for the total of the problem. $\endgroup$ – Boris Poris Oct 25 '20 at 4:36
  • $\begingroup$ As far as I can see, there is no reason to make any attempt to add these numbers together. If you have a closed form expression then you are done. Sometimes, it is nice to try to simplify the expression to see if you get any elegant insights. However, a summation formula is a perfectly acceptable answer. $\endgroup$ – user2661923 Oct 25 '20 at 4:39
  • $\begingroup$ I understand that, a summation is already a good formula. But I was still curious if anyone already has a further simplified expression (perhaps not involving the summation), so I guess I will leave the problem up if that ever happens. $\endgroup$ – Boris Poris Oct 25 '20 at 4:42
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I guess that answers my question then, there's not really a good simple closed form for it. I was really hoping that given what would seem like such a simple problem that there might be a simple formula for it, but I guess there actually isn't from the looks of the answer. $\endgroup$ – Boris Poris Oct 25 '20 at 4:45
1
$\begingroup$

If you are looking for a general method for such problems, you might consider generating functions. The answers to this question point to many resources for learning about generating functions: How can I learn about generating functions?

We will use an exponential generating function. It will simplify matters if we both alter the question slightly and make it more general. Seventeen B's are an essentially unlimited supply of B's if we are looking at twelve-letter words, so we might as well consider the supply of B's to be unlimited, with all other letters of the alphabet used at most once each. Let's say $a_r$ is the number of possible words of length $r$ that can be formed from that set of letters, and define $f(x)$ to be the exponential generating function of $\{a_r\}$, i.e. $$f(x) = \sum_{r=0}^{\infty} a_r \frac{x^r}{r!}$$ It turns out that in our problem $f(x)$ is fairly simple: $$f(x) = e^x (1+x)^{25}$$ In a sense we are done at this point, but what is the answer to the original problem? In our formulation, the answer is $a_{12}$, which is ${12!} [x^{12}]f(x)$, i.e. $12!$ times the coefficient of $x^{12}$ in $f(x)$. The easy way is to use a computer algebra system, which can provide the answer in the time it takes to type in the formula for $f(x)$. Mathematica yields $a_{12}=5595650767265101$.

Another way that is perhaps more satisfying mathematically is to use the infinite series for $e^x$ and the Binomial Theorem to expand $f(x)$: $$f(x) = \sum_{i=0}^{\infty} \frac{x^i}{i!} \cdot \sum_{j=0}^{25} \binom{25}{j} x^j$$ From this expression we can read off the coefficient of $x^{12}$: $$[x^{12}]f(x) = \sum_{j=0}^{12} \frac{1}{(12-j)!}\binom{25}{j}$$ and then $a_{12} = 12![x^{12}] f(x)$, which yields the same number given previously.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.