Neat proof! WFL On 11/19/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 19/11/2014 23:03, Warren D Smith wrote:
I stumbled across this apparently true fact:
Choose N random i.i.d. real numbers (from some fixed probability density) then sort them; result is (a,b,c,d,...,z).
Do it again independently, result is (A,B,C,D,...,Z).
Then what is the chance that a<A, b<B, c<C, ..., and z<Z simultaneously? ("vector domination")
Put 'em all together and sort them. Now go through them in order and move north 1 unit when you see an a/b/.../z and east one unit when you see an A/B/.../Z. The "vector domination" criterion is the same as saying that you never go below the line x=y (starting, of course, at the origin). The fact that you chose N of each says that you end up at (N,N).
But now we have a familiar problem with a familiar answer. The number of paths with this property is, e.g., the same as the number of properly-nested sequences of parentheses: the N'th Catalan number, which "as every schoolboy knows" is (2N choose N) / (N+1). There are plenty of proofs of this around; choose your favourite.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun