Problem:
We have N pies[1,2,3,...,N-1,N] and we have to pick a pie in each step but the constraint is that we can only choose pie from left end or right end. We have to find the expected value of the number of steps required to eat ith pie for every i from 1 to n
Approach 1 :
Assuming that some pth pie was choosen by p operations of type L(choosen from left end) and k operations of type R(choosen from right end) and the last operation was L obviously.
So before choosing the pth pie we had p-1+k steps out of which k where R type.
So number of ways to choose pth pie is (p-1+kCk)
Since choosing from left and right is equally likely the probability of choosing pth pie after p+k operations is (p-1+kCk).(1/2)p+k
So the expected value will become:
$$\sum_{k=0}^{n-p} C^{p-1+k}_k.(1/2)^{p+k}.(p+k)$$
I got this approach .
But i don't get how the second approach works.
Approach 2:
Here's how the second approach goes
I don't quite get this thing?
How is Sp being constructed like this here?
How did Sp get simplified?
Also why we did not consider pth pie being chosen from right in Approach 1 as we are considering in Approach 2?
Also there is simplification of the 1st Approach which i can't figure out either
Simplifying approach 1 using method 1:
enter image description here
What i did not get here:
-> What is [x^p]?
-> How is did the summation term get converted to [x^p] in 3rd step?
-> How did [x^p] term get converted to summation term again while simplifying the second term in last line?
Simplifying approach 1 using method 2:
enter image description here
Things i did not get here :
Did not get anything ;((
Can someone help me to understand these in a easier way?