Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

mwc
Member
Registered: 2006-11-20
Posts: 2

Expressing # of different character combinations for a given character

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)

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

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

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?


igloo myrtilles fourmis

Offline

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

pi man
Member
Registered: 2006-07-06
Posts: 251

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

Is this what you mean:

Offline

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

pi man
Member
Registered: 2006-07-06
Posts: 251

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

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)

Offline

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

mwc
Member
Registered: 2006-11-20
Posts: 2

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

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.

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

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

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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

er.neerajsrivastava
Member
Registered: 2006-12-27
Posts: 9

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

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?

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

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

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)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

Board footer

Powered by FluxBB