# How many 8-character passwords can be created with given constrains

How many unique 8-character passwords can be made from the letters $\{a,b,c,d,e,f,g,h,i,j\}$ if

a) The letters $a,b,c$ must appear at least two times.

b) The letters $a,b,c$ must appear only once and $a$ and $b$ must appear before $c$.

So for the first part I tried:

The format of the password would be $aabbccxy$ , where $x$ and $y$ can be any of the given characters.

So for $xy$, I have $10^2=100$ variations and for the rest, I can shuffle them in $\frac{6!}{(2! \cdot 2! \cdot 2!)}=90$ ways (the division is so they won't repeat) which makes total of $100*90=9000$ possibilities.

Now I don't know how to count the permutations when $x$ and $y$ are on different places. I wanted to do another permutation and multiply by $9000$, this time taking all $8$ characters in account, so I get $\frac{8!}{(2!\cdot 2! \cdot 2!)}$, but when $x$ and $y$ have the same value there still will be repetition.

As for the second I have no idea how to approach.

-
I'm a little confused by your conditions: the letters a,b,c must appear "at least two times" and "only once"? –  angryavian Jan 22 '13 at 14:50
I assume he means for point b that the letters a, b, and c, there cannot exist a letter which separates two of the same type. In other words $abab$ would not be possible but $aabb$ would. –  Neil Jan 22 '13 at 14:56
@blf a) and b) are different problems, not constrains of the same problem. And as for b) you can have abcxxxxx or bacxxxxx or axbcxxxxx or bxxacxxx and so on as long as the characters a and b appear before c and appear only once. –  Random Jan 22 '13 at 15:10

For the second one, let $Z(n)$ be the number of strings of length $n$ with none of $a,b,c$, $A(n)$ the number of strings of length $n$ that contain exactly one $a$ and no $b$ or $c$, $b(n)$ the number of strings of length $n$ that contain exactly one $b$ and no $a$ or $c$, $AB(n)$ the number of strings of length $n$ that contain exactly one $a$, exactly one $b$, and no $c$, and $C(n)$ the number of strings of length $n$ that contain one each of $a,b,c$ with the $c$ last. Then you can set up recurrences such as $Z(1)=7, Z(n)=7Z(n-1), A(1)=1, A(n)=7A(n-1)+Z(n-1)$. Do you see where these come from? A spreadsheet will make it easy to go through $n$-put $n$ in the rows and each of the functions in a column. Once you fill the formulas into the $n=2$ row, copy down gets you all the rows you want.

For the first, I would follow a similar approach to count the strings that don't have two of each and subtract that from the total number of strings.

Added: probably the solution your teacher is looking for in the second is that there are ${8 \choose 3}$ ways to choose the locations of $a,b,c$, $2$ ways to choose the order of $a,b,c$, and $7^5$ ways to choose the rest of the letters. This is easier than my earlier approach.

-
I don't understand the A(n)=7A(n−1)+Z(n−1) part. I know this is valid solution, but i need to use combinatorics to solve it and i know the professor won't accept a different approach on the exam. –  Random Jan 22 '13 at 15:28
@NikolaÐiÐoNelovski: The idea is that to form a string that has exactly one a and no b or c is to take a string that has exactly one a and add a non-a,b,c character, which gives 7 choices, or take one that doesn't have any of abc and add an a. –  Ross Millikan Jan 22 '13 at 15:36
Ok i understand now, thanks. –  Random Jan 22 '13 at 15:51
So the total number would be 2 * 7^5 * 8!/(3!*5!)? –  Random Jan 22 '13 at 16:27
@NikolaÐiÐoNelovski: That is correct. –  Ross Millikan Jan 22 '13 at 17:22

For the first:

count the number of passwords that do not satisfy the condition, then subtract from the total number of passwords

For the second:

Lay down your 5 "non-a,b,c" letters in order. There are $7^5$ ways to do this. Then you have to lay down the letters a,b,c in the 6 "gaps" between the 5 letters (don't forget the ends):

$|x|x|x|x|x|$ where "|" denotes a gap and $x$ denotes one of the 7 non-a,b,c letters.

We just have to count the number of ways to place a,b,c in the gaps. Place c first, and see how many ways you can place a,b such that they appear before c.

-
For the first part i would need to count the passwords that contain a,b,c only once and none at all and subtract from the total number of passwords? However counting the passwords that contain a,b,c only once is the same problem and i don't know how to do that. As for the second, if i can place a,b,c only in the gapes then i won't count the passwords where a,b,c are next to each other like abcxxxxx. –  Random Jan 22 '13 at 15:50
For the first, you want to count the number of ways that at least one of {a,b,c} occurs 0 or 1 times. Count the number of passwords where "a" appears exactly once, and count the number of passwords where "a" doesn't appear, then multiply that sum by 3 to account for b and c (the counting is the same). –  angryavian Jan 22 '13 at 16:05
For the second part, yes I was ambiguous in my answer, and you caught the delicacy in this method: you can put multiple letters in a gap. You just have to be careful in your counting. Let's say c is placed in the third gap. You can place a in either the first, second, or third gaps (where it is next to c if you choose the third gap!). Now, for b, you can place it in a gap not already occupied by a. If you decide to put b in a gap that is already occupied by a, you need to account for the fact that you can place it either before or after it, in the same gap. –  angryavian Jan 22 '13 at 16:06
So for the first part, i would have 8*(9^7)*3 ways that a,b,c would appear only once? –  Random Jan 22 '13 at 16:18
Ah, I made a mistake; I forgot to account for cases where "a" appears exactly once AND "b" appears exactly once... double/triple counting... –  angryavian Jan 22 '13 at 16:26