# Distribution of N balls numbered 1 to N with replacement

An urn contains N balls numbered 1.2.3...N.

I draw at random n balls, one by one with replacement.

Let X the smallest number, the largest Y and S the sum of all the n numbers

How to compute:

-the probability P(X=x,Y=y) that X=x AND Y=y

-the probability that S=s

-
If this is homework, tag it, and tell us what have you tried. To start with a simpler problem, can you obtain P(X)? –  leonbloy May 11 '11 at 14:08
No, it is not. Unfortunately, I am not a student for a long time (I am 70 years old). I think P(x)= –  Jean-Pierre May 12 '11 at 12:16
P(x) = 1/N^n [ (n-x+1)^n - (N-x)^] –  Jean-Pierre May 12 '11 at 12:18

You should count the number of the "good" instances and divide by the total number of instances.
For the first question - if the smallest is $x$ and the largest is $y$, then you are writing words of length $n$ using only the symbols $x,x+1,...,y-1,y$ (why?). How many such words do you have?
For the second question - it's equivalent to counting the number of solutions to $X_1+...+X_n=s$ where $1\leq X_i\leq N$, and then dividing by the total number of words of length $n$ over $1,...,N$ (why?). As to finding the number of solutions to this equation: it's the same as the number of solutions to $Y_1+...+Y_n=s-n$ where $0\leq X_i\leq N-1$. This can be done with exclusion-inclusion principle.
The other question, in your second post, is very similar. You can use the same approach, but there each letter/value can appear only once.

-

Thanks to Dennis for his comments.

So, I think the answer to the first question is:

P(X=x,Y=y) = 1/(N^n) * [ (y-x+1)^n -2 (y-x)^n + (y-x-1)^n ]

-