I think there are three prototypical string counting problems:

(1) Find the number of strings of a given length that use elements from a given set.

(2) Find the number of rearrangements of a given word.

(3) Find the number of words of a given length from a given set of letters, if each letter must occur at least once in the word.

Does everything written below make sense?

This problem looks like the first one above except in this case the set we source the elements from is not given explicitly. Let $S = \{x_1, x_2, y_1, y_2, y_3, y_4, z\}$ be the source set. Then there are $7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot2 \cdot 1$ $7$-strings with no repetition whose elements are sourced from $S.$ For example, $(y_4,y_1,z,x_2,y_3,x_1,y_2).$ Call such lists raw. This particular raw list can be fleshed out as $(c,d,a,5,f,3,k)$ or $(v,r,e,9,d,2,j)$ or $(q,b,a,4,f,1,p)$ etc These fleshed out lists correspond to the sets $\{3, 5, c, d, f, k, a\}, \{2, 9, d, j, r, v, e\}, \{1, 4, q, b, f, p, a\}, \ldots$ Generally, each raw list corresponds to a set $\{\text{$integer_1, integer_2, consonant_1, consonant_2, consonant_3, consonant_4, vowel$}\}.$ There are $\binom {10}{2}\binom {21}{4} \binom51$ such sets. So each of $7!$ lists can be fleshed out in $\binom {10}{2}\binom {21}{4} \binom51$ ways meaning there are $7!\binom {10}{2}\binom {21}{4} \binom51$ strings with the given property.

Or we could solve this problem following the logic of problem (2) above. To do that we need an actual fleshed out string first. Consider $(1,2,b,c,d,f,a).$ There are $P(10, 2)P(21, 4) \cdot 5$ ways to make such lists. In all these lists the first two elements are fixed to be integers followed by four consonants and a vowel for the last element. But we want integers, consonants and the vowel occur anywhere in a string so we want every rearrangement of each one of the $P(10, 2)P(21, 4) \cdot 5$ lists. Every string of the form $(int_1, int_2, cons_1, cons_2, cons_3, cons_4, vowel)$ can be rearranged in $\binom72\binom54$ ways so there are $P(10, 2)P(21, 4) \cdot 5 \cdot \binom72\binom54$ strings with the given property.

  • $\begingroup$ @ChristianBlatter, first we count all the sets like $\{1, 2, c, d, f, u, m\}, \{w,9, a, d, f, c, y\}, \{h, q, x, 0, 8, p, e\}, \ldots$ Then we permute every one of these sets in $7!$. Is that right? $\endgroup$ – user451131 May 31 '17 at 16:33

You can select $2$ of $10$ digits, $4$ of $21$ consonants, and $1$ of $5$ vowels in $${10\choose 2}\cdot{21\choose 4}\cdot {5\choose 1}=1\,346\,625$$ ways. After you have made these choices you have $7$ different objects before you. You can arrange these $7$ objects in $7!=5040$ ways. The total number of admissible strings therefore is $$1\,346\,625\cdot 5040=6\,786\,990\,000\ .$$


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.