Random strings that don't repeat.. How many possible

Hi all.. I have a math problem.. well two of them..

Problem #1

Given a pool of 29 different characters how many UNIQUE 5 character strings are possible?


The pool is 3456789ABCDEFGHJKMNPQRSTUVWXY

Stings can be anything like 33333 or 34567.. The only catch is that no two strings can be the same..

Problem #2

Given a pool of 15 different characters how many UNIQUE 10 character strings are possible?


The pool is 123456789ABCDEF

Stings can be anything like 3333333333 or 123456789A.. Again, the only catch is that no two strings can be the same..


Rudy

Im not 100% but I assume that for the first problem it would be 29^5 and for the second 15^10.

Quote:

---

Originally Posted by 03myersd

Im not 100% but I assume that for the first problem it would be 29^5 and for the second 15^10.

---

Thanks, that is what I was thinking but for soem reason it just didn't seem right..

Im sure it should be base^no.digits (well it will be that number -1 obviously)

10^3 = 1000
10^2 = 100

2^8 = 256
2^2 = 4

A professor of mine (who's hugely in to combinatorics--the math of counting) taught us to think about these situations in terms of the number of choices that can be made at each step. If you can find an algorithm to construct *any* of the objects in question using some choices, each with some number of equally-likely possibilities, you can multiply the number of possibilities at each choice to get the number of unique objects. Note that the algorithm has to give each object in only one way, to avoid double-counting.


Here in your second example, we could construct a 10 character string by:
1. Choose the first character. (How many possibilities here? 15)
2. Choose the second character. (15 possibilities again; no restrictions have been placed on repeating characters)
3. Choose the third character. (...)
...
10. Choose the tenth character. (15 possibilities)


How many different ways can you go to get through just the first two steps? Well, you can choose any of the 15 characters in the first step, giving 15 ways there. Each of those 15 ways has another 15 ways it can go when choosing the second character, so you have 15+15+15+...+15 [15 times] = 15*15 possible paths through just the first two steps. In the same way you can figure out how many ways you can go to get through the 10th step. In this case, you just multiply all the number of possible choices at each step, giving 15*15*15*...*15 [10 times] = 15^10, like you thought originally.

This method of counting relies heavily on intuition to make sure your algorithm works properly, but it does make things like this somewhat more obvious :)

i presume a string can have repeating characters?
so that eg: 12341, aa123, 22233, are allowabe??