Codex @codex  0

 Incoming links: Central binomial coefficient

ϑ (x) \geq \frac{x}{12}

for every sufficiently large real number

x

Every allocation is determined by the set of

n

children on the red bus, so there are

(n 2 n)

equally likely allocations. Exactly one places every boy on red and every girl on green. Hence

P (A_{n}) = (n 2 n)^{- 1} = \frac{( n ! ) ^{2}}{( 2 n )!} .

(n 2 n) \sim \frac{4 ^{n}}{πn},

and therefore

P (A_{n}) \sim \frac{πn}{4 ^{n}} .

4^{n} = (1 + 1)^{2 n} = \sum_{k = 0}^{2 n} (k 2 n) .

The central binomial coefficient is the largest of these

2 n + 1

(n 2 n) \geq \frac{4 ^{n}}{2 n + 1} = \frac{2 ^{2 n}}{2 n + 1} .

For the upper bound, fix a prime number

p \leq 2 n

v_{p} ((n 2 n)) = \sum_{j \geq 1} (⌊ \frac{2 n}{p ^{j}} ⌋ - 2 ⌊ \frac{n}{p ^{j}} ⌋) .

Each summand is either zero or one. Hence the P-adic valuation satisfies

v_{p} ((n 2 n)) \leq ⌊ \frac{l o g ( 2 n )}{l o g p} ⌋ .

p \leq 2 n

, this implies

p^{v_{p} ((n 2 n))} \leq 2 n .

There are at most

2 n

such prime numbers. If instead

p > 2 n

, then

p^{2} > 2 n

, so the P-adic valuation is at most one. Multiplying the prime-power contributions therefore yields

(n 2 n) \leq (2 n)^{2 n} \prod_{p \leq 2 n p prime} p .