How many arrangements of the letters AAABBBCCCDDDEEE are there such that there are no triple letters in the sequence?
There are 13!/(3!^4) ways of AAA occurring.
Same for BBB, CCC, DDD, EEE. Totaling 5*13!/(3!^4) = 24024000
There are 11!/(3!^3) ways of AAA and BBB.
Same for all C(5,2)= 10 double triples. Total is 10*11!/(3!^3) = 1848000
There are 9!/(3!^2) ways of AAA and BBB and CCC
Same for all C(5,3)= 10 triple triples. Total is 10*9!/(3!^2) = 100800
There are 7!/(3!) ways of AAA and BBB and CCC and DDD
Same for all C(5,4)= 5 quad triples. Total is 5*7!/(3!) = 4200
There are 5! ways of getting all of AAA, BBB, CCC, DDD and EEE. = 120
By inclusion/exclusion, ways of getting at least 1 triple = 24024000 - 1848000 + 100800 - 4200 + 120 = 22,272,720
Since we want no triples, the number of ways of that is 15!/3!^5 - 22272720 = 145,895,280.
Check against a simulation:
In a million trials we'd expect around 132443 cases of finding at least one triple letter sequence. That way we can test the result with a simulation:
a='aaabbbcccdddeee';
ct=0;
for i=1:1000000
b=a(randperm(15));
found=false;
for j=1:3:13
f=strfind(b,a(j:j+2));
if ~isempty(f)
found=true;
end
end
ct=ct+found;
end
fprintf('%d vs 132443',ct)
Three runs show
133132 vs 132443
132654 vs 132443
131935 vs 132443
a pretty good match.
A 10-million-trial run shows 1323536 vs 1324433.
|
Posted by Charlie
on 2023-11-14 14:46:20 |