1
$\begingroup$

Can someone give me a formula to calculate $ _nP_0 + _nP_1 +_ nP_2 + _nP_3 + .. + _nP_x$ ?

I need a simple formula to calculate this.

MY actual question is

In a certain programming language identifiers must meet the following requirements: - the first character must be an ASCII letter (A-Z, a-z) - other (than the first) characters must be an ASCII letter, digit (0-9) or an underscore - the maximum length of an identifier is 8 characters The total number of possible identifiers is:

[A] $53*(63^7)$
[B] $52*(63^8 - 1)/62$
[C] $52*(63^7 - 1)/63$
[D] $53*(63^8)$
[E] $(63^8)/(52^8)$

Choose the right answer.

For 1 letter variable ->
Here, First position can be filled with 52 chars.

For 2 letter variable ->
Then, First posision can be filled with 52 chars. And second char can be filled up $_{63}P_1$

For 3 letter variable ->
Then, First posision can be filled with 52 chars. And second char can be filled up $_{63}P_1$. And third char can be filled up with $_{63}P_2$

This goes on like this upto 8 letter variable.
So, the series should be $52 + 52(_{63}P_1) + 52(_{63}P_2) + \dots $
That implies $52(1 + _{63}P_1 + _{63}P_2 + _{63}P_3 +\dots + _{63}P_7)$

After this, I couldn't proceed.

  • 0
    viji what is P here2012-06-04
  • 0
    Permutation - nPr = n!/(n-r)!2012-06-04
  • 0
    There is no simple formula. Please post the context of your question. I suspect there is an easy way to avoid the task you are referring to.2012-06-04
  • 0
    @rschwieb I've posted my original question too.2012-06-04
  • 0
    @rschwieb: I dunno, I think this is a relatively simple formula: $$\sum_{k=0}^r k!\binom{n}{k}=n!\sum_{k=n-r}^n \frac{1}{k!}$$. Now, if you were thinking of the fact that the partial sum of the exponential function requires an expression in terms of incomplete gamma functions, then sure...2012-06-04
  • 0
    The problem is much clearer now, thank you. @J.M. I expected the answer to the (then invisible) problem might be even easier. The original question was so light on information I half expected that that author meant $_nC_x$, and was overlooking a complement argument.2012-06-04
  • 0
    There should be no permutations involved. For an identifier of length, say $3$, you have $52$ possibilities for the first character, $63$ for the second caracter and again $63$ for the third, so a total of $52 \cdot 63^2$ possibilities.2012-06-04
  • 0
    @AlexanderThumm: But the variable length can differ. It's not necessary that the variable length will always be 8.2012-06-04

1 Answers 1

2

There are $52 \cdot 63^{n}$ possible identifiers of length exactly $n+1$, and therefore $$\sum_{k=0}^{n} 52 \cdot 63^{k} = 52 \cdot \sum_{k=0}^{n} 63^{k} = 52 \cdot \frac{63^{n+1} - 1}{63 - 1} = 52 \cdot \frac{63^{n+1} - 1}{62}$$ possible identifiers of length $\leq n+1.$ The second equality comes from the closed form of the geometric series . Specializing to $n+1 = 8,$ we can see, that [B] is the correct answer.