n different characters namely
d. Use them to compose
n-length string. Count the number of different
n-length strings which at least contain
one b and
My previous idea is like:
A contains strings with at least
one a. Similarly we have set
|A| = |B| = |C| = n * 4^(n-1). Firstly, choose one place of
n (n possibilities) to set it to character
n-1 places left with 4^(n-1) possibilities.
But some guys say this is not right. He suggests that the right answer should be
|A| = |B| = |C| = 4^n - 3^n. Could you guys explain why it does not work?
I think there is a
rule out there that I should follow when counting this kind of permutations. I need to find it out. Otherwise, I would make similar mistake next time without consciousness. It is essential to summarize the tip when and how I avoid this kind mistake.
Could someone figure the rule out?
I think there is rule somehow:
When counting elements with property
P, we cannot split the counting process into pieces. That is to say we cannot split property
P = P1 + P2 + ... + Pk. This usually repeats one element several times.
For the above problem, I split the
number of at least 1 a of a
n-length string into two sub-properties as
1 a and
0 and/or more a's. This will repeatedly count some strings with more than
1 a. Like n = 5,
abcaa will be counted 3 times since it has