Re: recursive formula.

[BrowserUk]

What should the result be for P( 1, 1, 1 )?

My interpretation is that each term will be: P( 1 - 1 )P( ... )

Which as 1 - 1 will always be zero, the results of the multiplication is zero, so the overall results will be zero?

If this is the case, then herveus' solution is incorrect as given input of ( 1, 1, 1 ), he returns 1.

If I'm correct, of which there is no guarentee, then I think that the problem lies with his simple expedient of prefixing the list with a 0 to get around the "indices starting from 1" problem, which is causing the function to iterate and recurse once too often.

[rsteinke]

You forget that r_0 is always zero, so

P(1, 1, 1) = (1 - 1) P(1, 1) + (1 - 1) P(1, 1) + (1 - 0) P(1, 1)
           = P(1, 1) = P(1) = 1

[BrowserUk]

Thanks. That's the source of my misunderstanding. I saw the r₀ = 0 reference, but I also saw r running 1 .. n and i running 1 to n.

I missed that n-i = 0 whenever n=i. Stupid.