Combinatorial argument probabilities

[Dassinia]

Hello
1. Homework Statement
Consider f_k N*→N, k≥0
f_k(n)=Σ j^k n>0

We're looking to establish these identities, using a combinatorial argument
f_k(n)=n if k=0
f_k(n)= 1/(k+1) [ n^k+1 + Σ ( i , k+1) (-1)^k+1-if_i(n) ] if k>0
the sum is about i from i=0 to i=k-1 and (i, k+1) is the combination.

Consider the experience of k+1 drawing with handoff from a box of n balls numbered
Ej : the maximum of the values obtained on the k+1 draw is j , j=1,...,n
Fj : The drawing are made on {1,...,j} j=1,...,n
Fo=

1. Find |Ω|
2. Write Ω as an operation on sets E1,...,En
3. Write Ej as an operation on sets F_j-1, F_j j=1...n
4. Find |Fj| j=0...n
5. Find |Ej| j=1...n
6. Find |Ω| through the calculation of |Ej| j=1...n and using the binomial theorem

Homework Equations

(x+y)ⁿ=∑(k, n)x^n-ky^k

The Attempt at a Solution

1. |Ω|=n^k+1
2. Ω=∩ Ej for j=1,...,n
3. I just don't get what Fj represents..?

Thanks

 

[mighty2000]

for posting this interesting problem! I am a scientist and I would be happy to help you with your questions.

First, let's define some terms so we are all on the same page. In this problem, we are looking at a box of n balls, each with a unique number on it. We are also considering k+1 drawings from this box, where each drawing involves randomly selecting one ball from the box and recording the number on it. So, for example, if we have a box with 5 balls numbered 1, 2, 3, 4, and 5, and we make 3 drawings, we might get the following results: 1, 4, 2.

Now, let's take a look at the expressions given in the problem. The first one, fk(n)=n if k=0, is pretty straightforward. This is saying that if we make 0 drawings (k=0), then the maximum value we can get is just n, which is the number of balls in the box.

The second expression, fk(n)= 1/(k+1) [ nk+1 + Σ ( i , k+1) (-1)k+1-ifi(n) ] if k>0, is a little more complicated. But essentially, it is saying that if we make k+1 drawings (k>0), then the maximum value we can get is either the highest number on the ball (nk+1) or the sum of all the possible combinations of numbers we could get (the Σ term). The (-1)k+1 term is accounting for the fact that we are subtracting the sum of all the possible combinations, since we only want the maximum value. The i term represents the number of balls we are choosing from in each combination, and the fi(n) term represents the number of ways we can get that particular combination. For example, if we make 2 drawings (k=1) from a box of 5 balls (n=5), then the maximum value we can get is either 5 (nk+1) or the sum of all the possible combinations of 2 balls (the Σ term). This would be 5 + (-1)^1*f2(5) = 5 + (-1)*10 = -5. So, fk(n)= 1/(k+1) [ nk+1 + Σ ( i , k+1