+2489 I can offer a guess from where this lexicographic order of BS originated. A mathematics professor usually creates this type of teaching material and he or she will recruit an undergrad (or graduate) student to provide solutions with answers as a paid assignment. The students, and the professors who recruit them, are notorious for not checking and cross checking their solutions for accuracy. (This is why the answers in the “back of the book” are often wrong.)
Obviously, this lexicographic output was generated by a miscoded computerized algorithm that cataloged the correct set along with a massive amount of rubbish. Even if correctly presented, computerized solution algorithms of this type are of limited use beyond verifying a solution.
-----------------------
Along with Rom’s use of binomial counting for each case, there are two other methods for solving this: A Markov matrix and a generating function.
Though sometimes difficult to create, the generating function is relatively simple for this application. For “SSSTTTIIAC” the counts are 3, 3, 2, 1, and 1 for each of the letters. This corresponds to a generating function of (1+x+x^3) (1+x+x^3) (1+x+x^2)(1+x)(1+x)
Expanding this series produces the coefficients. (Doing this manually takes about 45 minutes. The “Wolf” takes about 10 seconds.)
\(x^{10} + 5 x^9 + 13 x^8 + 24 x^7 + 34 x^6 + 38 x^5 + \mathbf {34 x^4} + 24 x^3 + 13 x^2 + 5 x + 1\\\)
Here, the coefficient of 34 for x4 corresponds to the 34 unique-element subsets of four (4) from a set of 10 elements (S,S,S,T,T,T,I,I,A,C). Note the inclusion of all coefficients for subsets ranging from zero (0) to ten (10).
GA
