Expressing # of different character combinations for a given character

mwc · 2006-11-20 02:52:28

Expressing the number of different character combinations for a given character length...

Where n = the number of characters.
and x = number of possible characters.

e.g
for alphanumeric characters, case sensitive x = 62.
up to say 5 characters in length n = 5. I could express
the number of combinations as:

(x^n) + (x^(n-1)) + (x^(n-2)) + (x^(n-3) + x

or//

62^5 + 62^4 + 62^3 + 62^2 + 62 = 931,151,402 combinations.

I ask, how would i simplify it so it could be written for any n?

i.e. in the above example replacing the "62^4 + 62^3 + 62^2" with
something else.

It's got to be simple. I'm just not seeing it.

----------
Other examples, in case you didn't notice the obvious pattern:
where n = 4:
(x^n) + (x^(n-1)) + (x^(n-2)) + x
or// x^4 + x^3 + x^2 + x
where n = 3
(x^n) + (x^(n-1)) + x
or// x^3 + x^2 + x

Last edited by mwc (2006-11-20 02:55:38)

John E. Franklin · 2006-11-20 04:15:05

I think your equation is wrong, but I may be wrong.
Maybe I don't understand what you mean?
Isn't it (62)(61)(60)(59)(58), if you don't want repeated letters?
Just multiply them together?

pi man · 2006-11-20 04:15:16

Is this what you mean:

pi man · 2006-11-20 04:19:54

I took it to mean that characters are allowed to be repeated. But you want to find the number of combinations for UP TO n characters. So for N=3 you need to find all the 3 character combinations plus the number of 2 character combinations plus the number of 1 character combinations. And to be technically correct, you should probably add in the number of 0 character combinations (1 - the null set).

Last edited by pi man (2006-11-20 04:20:11)

mwc · 2006-11-20 04:58:50

Thanks "pi man". You were correct in assuming I meant characters
"UP TO" n. Sorry about the ambiguity in my explanation.

I was trying to come to some solution with just three terms. I never
thought of using summation notation.

Yes, "technically" I should have the null set. But filenames don't
have 0 characters. So your solution models it fine, if I change it to
start at 1 rather than 0.

I'm no mathematician I just found myself working out the complexity
of a little C program that I've just bashed together.

Thanks for your help.

M.

krassi_holmz · 2006-12-27 22:11:31

This gives a polynomial of degree n, so your program should have complexity:

er.neerajsrivastava · 2006-12-29 03:27:38

well for c program you can just use simple looping concept
like
sum=0;
for(i=n;i>=0;i--)
{
sum=sum+pow(x,i);
}
isn't it simple?
is that helped you or you did it in another way?

krassi_holmz · 2006-12-29 06:42:03

er.neerajsrivastava wrote:

well for c program you can just use simple looping concept
like
sum=0;
for(i=n;i>=0;i--)
{
sum=sum+pow(x,i);
}
isn't it simple?
is that helped you or you did it in another way?

Yep. But maths helps better, because we know:

.
This gives us simplier program:

double sum(double x, int n){
return (pow(x,n+1)-1)/(x-1)
}
(and more efficient, too)

Math Is Fun Forum

#1 2006-11-20 02:52:28

Expressing # of different character combinations for a given character

#2 2006-11-20 04:15:05

Re: Expressing # of different character combinations for a given character

#3 2006-11-20 04:15:16

Re: Expressing # of different character combinations for a given character

#4 2006-11-20 04:19:54

Re: Expressing # of different character combinations for a given character

#5 2006-11-20 04:58:50

Re: Expressing # of different character combinations for a given character

#6 2006-12-27 22:11:31

Re: Expressing # of different character combinations for a given character

#7 2006-12-29 03:27:38

Re: Expressing # of different character combinations for a given character

#8 2006-12-29 06:42:03

Re: Expressing # of different character combinations for a given character

Board footer