+0

# Combinations and permutations

0
543
8

How many 4-letter permutations and 4-letter combinations can be formed from the word "STATISTICS"? Any help would be greatly appreciated. Thank you.

Apr 2, 2019

#1
+6210
+2

$$\text{STATISTICS = SSSTTTIIAC}\\ \text{So in forming distinct permutations we must consider the various cases }\\ \text{of how many pairs or triples are in a given choice of 4 letters}\\$$

$$\text{case 1: 1 triplet, 1 singleton}\\ \text{There are }\dbinom{2}{1}=2 \text{ ways to select the triplet,}\\ \dbinom{4}{1}=4 \text{ ways to select the singleton, }\\ \text{and }\dbinom{4}{1}=4 \text{ ways to select where the singleton falls}\\ n_1 = 2\cdot 4\cdot 4 = 32$$

$$\text{case 2: 2 pairs}\\ \dbinom{3}{2}=3 \text{ ways to select which letters form the two pairs}\\ \dbinom{4}{2}=6 \text{ ways to select which slots for the first pair}\\ n_2 = 3\cdot 6 = 18$$

$$\text{case 3: 1 pair}\\ \dbinom{3}{1}=3 \text{ ways to select which letter is the pair}\\ \dbinom{4}{2} = 6 \text{ ways to select the singleton letters}\\ \dbinom{4}{2} = 6 \text{ ways to assign the pair of letters}\\ \dbinom{2}{1}=2 \text{ ways to assign the first singleton}\\ n_3 = 216$$

$$\text{case 4: 4 singletons}\\ \dbinom{5}{4}=5 \text{ ways to select the letters}\\ 4!=24 \text{ ways of arranging them }\\ n_4 = 120$$

$$n_p = 32+18+216+120 = 386$$

$$\text{Combinations is much easier. }\\ \text{We still have to consider cases}\\ \text{case 1: 1 triplet }c_1=\dbinom{2}{1}\dbinom{4}{1} = 8$$

$$\text{case 2: }c_2=\dbinom{3}{2}=3$$

$$\text{case 3: }c_3 = \dbinom{3}{1}\dbinom{4}{2} = 18$$

$$\text{case 4: }c_4=\dbinom{5}{4} =5$$

$$n_c = 8+3+18+5 = 34$$

Note that you can separate the permutations calculations into factors related to selecting the letters

and factors related to arranging the letters.

Combination calculations just omit the factors related to arranging the letters.

.
Apr 2, 2019
edited by Rom  Apr 2, 2019
edited by Rom  Apr 2, 2019
edited by Rom  Apr 2, 2019
#2
0

Thank you very much Rom. I greatly appreciate your time. However, the answers given to us are:

Permutations = 386,  Combinations = 125. Both of them are supposed to be "Distinct". But, as of yet, no detailed explanations as to how they were arrived at!. They are also listed in some sort of "lexicographic" order, which I have.

Apr 2, 2019
#3
+6210
0

If no ordering matters at all then 34 is the correct answer.

I'm not sure what ordering they consider distinct to come up with 125

Rom  Apr 2, 2019
#4
0

Thanks Rom. Here are the "combinations" listed:

{s, t, a, t} | {s, t, a, i} | {s, t, a, s} | {s, t, a, c} | {s, t, t, i} | {s, t, t, s} | {s, t, t, t} | {s, t, t, c} | {s, t, i, s} | {s, t, i, t} | {s, t, i, i} | {s, t, i, c} | {s, t, s, t} | {s, t, s, i} | {s, t, s, c} | {s, t, s, s} | {s, t, c, s} | {s, a, t, i} | {s, a, t, s} | {s, a, t, t} | {s, a, t, c} | {s, a, i, s} | {s, a, i, t} | {s, a, i, i} | {s, a, i, c} | {s, a, s, t} | {s, a, s, i} | {s, a, s, c} | {s, a, s, s} | {s, a, c, s} | {s, i, s, t} | {s, i, s, i} | {s, i, s, c} | {s, i, s, s} | {s, i, t, i} | {s, i, t, c} | {s, i, t, s} | {s, i, i, c} | {s, i, i, s} | {s, i, c, s} | {s, s, t, i} | {s, s, t, c} | {s, s, t, s} | {s, s, i, c} | {s, s, i, s} | {s, s, c, s} | {t, a, t, i} | {t, a, t, s} | {t, a, t, t} | {t, a, t, c} | {t, a, i, s} | {t, a, i, t} | {t, a, i, i} | {t, a, i, c} | {t, a, s, t} | {t, a, s, i} | {t, a, s, c} | {t, a, s, s} | {t, a, c, s} | {t, t, i, s} | {t, t, i, t} | {t, t, i, i} | {t, t, i, c} | {t, t, s, t} | {t, t, s, i} | {t, t, s, c} | {t, t, s, s} | {t, t, t, i} | {t, t, t, c} | {t, t, t, s} | {t, t, c, s} | {t, i, s, t} | {t, i, s, i} | {t, i, s, c} | {t, i, s, s} | {t, i, t, i} | {t, i, t, c} | {t, i, t, s} | {t, i, i, c} | {t, i, i, s} | {t, i, c, s} | {t, s, t, i} | {t, s, t, c} | {t, s, t, s} | {t, s, i, c} | {t, s, i, s} | {t, s, c, s} | {a, t, i, s} | {a, t, i, t} | {a, t, i, i} | {a, t, i, c} | {a, t, s, t} | {a, t, s, i} | {a, t, s, c} | {a, t, s, s} | {a, t, t, i} | {a, t, t, c} | {a, t, t, s} | {a, t, c, s} | {a, i, s, t} | {a, i, s, i} | {a, i, s, c} | {a, i, s, s} | {a, i, t, i} | {a, i, t, c} | {a, i, t, s} | {a, i, i, c} | {a, i, i, s} | {a, i, c, s} | {a, s, t, i} | {a, s, t, c} | {a, s, t, s} | {a, s, i, c} | {a, s, i, s} | {a, s, c, s} | {i, s, t, i} | {i, s, t, c} | {i, s, t, s} | {i, s, i, c} | {i, s, i, s} | {i, s, c, s} | {i, t, i, c} | {i, t, i, s} | {i, t, c, s} | {i, i, c, s}=125

Apr 2, 2019
#5
+6210
+1

I can see that (for example) they treat stat and atst as two different combinations.

They aren't.

They are both the combination astt.

Rom  Apr 3, 2019
#6
+2165
+4

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

Apr 3, 2019
edited by GingerAle  Apr 4, 2019
#7
+6210
+1

Thank you.  I don't generally use generating functions to answer these sorts of questions because

if the OP doesn't understand the counting method, generating functions just seem to come from

outer space and magically provide answers.

Rom  Apr 3, 2019
#8
+2165
+4

Interesting metaphors.  Generating functions seemed magical to me the first time I saw them demonstrated.  Along with usable numbers popping up like dandelions in May, I actually understood the counting methods used for its derivation, without having to spend hours studying. That was magical for sure.  My mentor, Lancelot Link, who taught the concepts to me wasn’t completely human, and he certainly was from high-up and far-out, but not quite to outer space –though I still do wonder sometimes.

In the case of this OP, while I’m sure he doesn’t (and never will) understand the counting methods for generating functions; he does know what they are. Twice, here and here, he’s referenced this post  https://web2.0calc.com/questions/probability_882, where Nauseated uses a generating function for type 2 Sterling numbers to solve a dice probability problem.

Of course this OP is the one of the forum’s principal (higher functioning) village idiots, the arch idiot, !!!Mr. BB!  (Triple Deranged Mr. BB!). Because he has such an affinity for generating functions, I thought it apropos to use one to solve a combination problem he posted.

Mr. BB likes to solve math problems using his computer, but his coding skills are as dubious as his math skills and he screws-it-up almost all the time. The “lexicographic” output list, which isn’t lexicographic at all, is his work via his computer.  He looks at this slop output, and though on some level knowing it’s wrong, still believes there are gold nuggets hidden in them-there iterations.  So in the guise of a student, he presents a question on the forum, in the hopes that a high-level mathematician will answer it. ...

...  One did: you. Mr. BB then presents his non-lexicographic, slop output list as an official answer, in the hopes that your advanced skills will magically detect a unique pattern buried in the rubbish that will give it some validity.   Of course, only a god with the power to change mathematical and physical constants could do this; unfortunately, most of them disappeared with the ancient Greeks. Something Mr. BB has lamented about for years, I’m sure.

... And the cycle begins again...

GA

GingerAle  Apr 4, 2019