I have a homework question to find the number of ways to sort 1112223334444 while not having the complete groups of numbers together. Or not having 111 or 4444 for example.
Can someone please help? Thanks
I have a homework question to find the number of ways to sort 1112223334444 while not having the complete groups of numbers together. Or not having 111 or 4444 for example.
Can someone please help? Thanks
Hint: The first thing that we need to know is how to count the total number of patterns. We are producing a $13$-digit number. The positions where the $1$'s will go can be chosen in $\binom{13}{3}$ ways. For every way of choosing where the $1$'s will go, there are $\binom{10}{3}$ ways to decide where the $2$'s will go. So there are $\binom{13}{3}\binom{10}{3}$ of placing the $1$'s and the $2$'s. But for every way of placing the $1$'s and the $2$'s, $\dots$. Continue.
Now for the various questions you were asked, we need to find the number of bad numbers, the $13$-digit numbers that do have, for example, all the identical digits together. Counting these is particularly easy.
For say all the $1$'s together, there is a cute idea. Tie the three $1$'s together, to make a supersymbol. Then you have three $2$'s, three $3$'s, four $4$'s, and the supersymbol. How many ways can these be arranged? We use the same basic idea as the one we described for counting the total number of patterns.
I hope this helps you to get a good start. If tomorrow you are still having trouble, I will solve one of the problems in full detail.
Added: We look at the most unpleasant of the problems, that of finding the number of $13$-digit numbers that nowhere have three consecutive $1$'s, or three consecutive $2$'s, or three consecutive $3$'s, or four consecutive $4$'s. Call such a $13$-digit number good. And call a $13$-digit number bad if it is not good. We had already described how to find the total number of $13$-digit numbers that can be formed with our digits. For the record, this is $\binom{13}{3}\binom{10}{3}\binom{7}{3}.$ We show how to count the number of bad $13$-digit numbers. Then we can find the number of good ones by subtraction. The recipe for counting the bad ones is a bit complicated, but only involves binomial coefficients. From the recipe we could then find an explicit numerical answer, but we will not do the actual calculations.
The problem is messy, and it is useful to introduce some notation. Let $A$ be the set of numbers with three $1$'s in a row, $B$ the set with three $2$'s in a row, $C$ the set with three $3$'s in a row, and $D$ the set with four $4$'s in a row. Note that $A$ includes, for example, the numbers that have three $1$'s in a row and three $3$'s in a row, so there is overlap between our sets $A$, $B$, $C$, and $D$.
For any finite set $X$, denote by $|X|$ be the number of elements in the set $X$. The set of bad numbers is $A\cup B\cup C\cup D$. So we want to find $|A\cup B\cup C\cup D|$.
A sensible way to start is to to find $|A|$, $|B|$, $|C|$, and $|D|$, and add them up. That will turn out to be not quite right. But it is the start of a standard procedure called inclusion-exclusion.
Let us find $|A|$, the number of strings with all the $1$'s together. Tie the $1$'s together to make a supersymbol. To find the number of strings with the $1$'s together, we count the number of strings we can make with the supersymbol, three $2$'s, three $3$'s, and four $4$'s, a total of $11$ "letters." The position of the supersymbol can be chosen in $\binom{11}{1}$ ways. For each such way, the $2$'s can be placed in $\binom{10}{3}$ ways. And once we have placed the $2$'s, the $3$'s can be placed in $\binom{7}{3}$ ways. And once we have done that, the $4$'s must fall in the remaining slots. We conclude that $|A|=\binom{11}{1}\binom{10}{3}\binom{7}{3}.$
We get exactly the same answers for $|B|$ and for $|C|$. The answer for $|D|$ is a little different, because the supersymbol has length $4$, so there are $10$ "letters." We get $|D|=\binom{10}{1}\binom{9}{3}\binom{6}{3}.$ Imagine adding up our four numbers. This overcounts the bad strings, because, for example, it double-counts the strings that have, for example, three consecutive $1$'s and three consecutive $2$'s, as well as several other types of bad string. So we must do some subtractions, to get rid of the double-counting.
For example, how many strings have three consecutive $1$'s and also three consecutive $2$'s? Use the tying together idea. We now have two types of supersymbol, as well as three loose $3$'s and four loose $4$'s. We want to find the number of strings in $A\cap B$. By using I hope by now familiar reasoning, we find that $|A\cap B|=\binom{9}{1}\binom{8}{1}\binom{7}{3}.$ We get the same counts for $A\cap C$ and $B\cap C$.
Unfortunately, the counts for $A\cap D$, $B\cap D$, and $C\cap D$ are a little different. For $A\cap D$, we have two supersymbols, and three loose $2$'s and three loose $3$'s. So $|A\cap D|=\binom{8}{1}\binom{7}{1}\binom{6}{3},$ with the same count for $B\cap D$ and $C\cap D$.
Subtract these six numbers from $|A|+|B|+|C|+|D|$. Are we finished? No! We have subtracted too much, namely all the strings that are triply bad, having say three consecutive $1$'s, and $2$'s and $3$'s, or three consecutive $1$'s, $2$'s, and four consecutive $4$'s (there are two other types).
These are all easy to count. For example, using our tying strategy we find that $|A\cap B \cap C| =\frac{7}{1}\frac{6}{1}\frac{5}{1}.$ For the other three types, we get, as a sample, $|A\cap B \cap D| =\frac{6}{1}\frac{5}{1}\frac{4}{1}.$
So take the four numbers we obtain at this stage, add them back. Are we finished? No, we have added back one too many times the strings that have the $1$'s and the $2$'s and the $3$'s and the $4$'s all consecutive. There are $(4)(3)(2)$ of these, so we need to subtract this. And now it's over!
Comment: To summarize, our answer is the sum of the sizes of our sets $A$, $B$, $C$, $D$, minus the sum of the sizes of their intersections in pairs, plus the sum of the sizes of their intersections in triples, minus the size of the intersection of all of them. The general idea, called Inclusion-Exclusion is useful in quite a few combinatorial calculations.
If you are familiar with multinomial coefficients, we can get more compact expressions for the various counts. For instance, the total number of arrangements is $\binom{13}{3,3,3,4}$, the number of arrangements in $A$ is $\binom{11}{1,3,3,4}$, and so on. We used the more cumbersome binomial coefficients because somehow they seem more concrete.
The number can be computed in GAP via e.g.:
A:=[1,1,1,2,2,2,3,3,3,4,4,4,4]; n:=Size(A); S:=PermutationsList(A);; T:=Filtered(S,L->ForAll([1..n-2],i->L[i]<>1 or L[i+1]<>1 or L[i+2]<>1));; T:=Filtered(T,L->ForAll([1..n-2],i->L[i]<>2 or L[i+1]<>2 or L[i+2]<>2));; T:=Filtered(T,L->ForAll([1..n-2],i->L[i]<>3 or L[i+1]<>3 or L[i+2]<>3));; T:=Filtered(T,L->ForAll([1..n-3],i->L[i]<>4 or L[i+1]<>4 or L[i+2]<>4 or L[i+3]<>4));; Print(Size(T),"\n");
which returns 1056174
.