In dit artikel gaan we ervan uit dat je bekend bent met faculteiten en binomiaalcoëfficiënten. Per definitie is $n! = n \cdot (n – 1) \cdot (n – 2) \cdot ... \cdot 3 \cdot 2 \cdot 1$. Voor $n = 1$ tot en met 7 vinden we $1! = 1; 2! = 2; 3! = 6; 4! = 24; 5! = 120; 6! = 720$ en $7! = 5040$. In de OEIS vind je deze getallen onder nummer A000142.

Verder is de binomiaalcoëfficiënt $n\choose k$ als volgt gedefinieerd:

$${n\choose k}= \frac{n!}{k!\cdot (n-k)!}$$

Dit artikel gaat over de volgende speciale binomiaalcoëfficiënten: 

$$B(n) ={2n\choose n} = \frac{(2n)!}{n!^2}$$

voor $n \geq 1$ en $B(0) = 1$. Deze rij – 1, 2, 6, 20, 70, 252, 924, ... – vind je in de OEIS onder nummer A000984. Paul Erdős vermoedde dat op een enkele uitzondering (in het begin van de rij) na al deze binomiaalcoëfficiënten deelbaar zijn door een kwadraat (groter dan 1). Inderdaad zijn 1, 2, 6 en 70 de enige kwadraatvrije getallen (dus niet deelbaar door een kwadraat groter dan 1) in de rij $B(n)$. In 1996 bewezen Andrew Granville en Olivier Ramaré dat er geen andere kwadraatvrije  getallen van de vorm $\binom{2n}{n} zijn. Daarvoor hadden enkele andere wiskundigen al aangetoond dat áls er misschien toch nog kwadraatvrije getallen in de rij zouden zitten, die wel erg groot zouden moeten zijn.

Faculteit en primulteit

Voor $n!$ bestaat een benaderingsformule:

$$n! \approx \sqrt{2\pi n}\cdot \left(\frac{n}{e}\right)^n.$$

Dit is de formule van Stirling. Verder definiëren we $n$# (spreek uit: n primulteit) als volgt:

$$n\# = 2 \cdot 3 \cdot 5 \cdot ... \cdot p_n,$$

waarbij $p_n$ het grootste priemgetal is dat nog kleiner is dan of gelijk is aan n. Achtereenvolgens vinden we 1\# = 1, 2# = 2, 3# = 6, 5# = 30, 7# = 210, 11# = 2310 en 13# = 30030 (zie OEIS A034386). Een stuk ingewikkelder is het om een benadering van $n$# te vinden. Het aardige is dat dit juist met behulp van $2n\choose n​​​​$ weer goed lukt.

Een simpele observatie

We gaan $B(n + 1)$ berekenen uit $B(n)$. Dat lijkt misschien lastig, maar het blijkt mee te vallen, want

\(\begin{align*} \frac{B(n+1)}{B(n)} &= \frac{(2n+2)!}{(n+1)!^2}\frac{n!^2}{(2n)!}\\&=\frac{(2n+2)(2n+1)}{(n+1)^2}\\ &=\frac{2(2n+1)}{n+1}=4-\frac{2}{n+1}. \end{align*}\)

Deze observatie komen we verderop in het verhaal nog een aantal keren tegen.

Aantal factoren $p$

We gaan $n!$ ontbinden in factoren. Bijvoorbeeld $6! = 720 = 24 \cdot 32 \cdot 5$. De vraag is: hoeveel factoren van de priemen 2, 3, 5, ... komen in $n!$ voor? We gaan er op twee manieren naar kijken, zonder in detail te treden.

Uitgaande van bovengenoemde observatie zien we dat het aantal priemfactoren $p$ van $B(n + 1)$ niet zal veranderen ten opzichte van het aantal priemfactoren van $B(n)$ als $p\neq 2$ en $p$ geen deler is van $n+1$ (dus $p ∤ n + 1$) en van $2n + 1$ (dus $p  ∤ 2n + 1$).

Opgave. Kun je zelf afleiden wat het gedrag is van het aantal factoren 2 in $B(n)$ op grond van bovengenoemde observatie?

$B(2n + 1)$ heeft een factor 2 meer dan $B(2n)$, en voor $n = 2m + 1$ geldt: $B(2^k(2m + 1))$ bevat $k - 1$ factoren 2 minder dan $B(2^k(2m + 1) - 1)$. Het aantal factoren 2 van $B(n)$ kun je terugvinden in de OEIS onder nummer A000120. 

Hoeveel factoren $p > 2$ bevat $n!$? Om te beginnen bevatten $p, 2p, 3p, ...$ een factor $p$. Voor $n!$ gaat dat om $\lfloor n/p \rfloor$ factoren $p$. Hierbij is $\lfloor x \rfloor$ de entierfunctie; de afrondfunctie naar het grootste gehele getal kleiner dan of gelijk aan $x$ (bijvoorbeeld $\lfloor 4,7\rfloor = 4$). Maar hiermee zijn we er nog niet, immers 6! bevat 4 factoren 2 en niet 6/2 = 3 factoren 2. We moeten ook kijken hoeveel getallen een veelvoud zijn van $p^2$, vervolgens $p^3$, enzovoort. 

Eenvoudig is te zien dat er $\lfloor n/p^2\rfloor$ getallen zijn tussen 1 en $n$ die een veelvoud zijn van $p^2$. Deze getallen bevatten 2 (of meer) factoren $p$. Maar door $\lfloor n/p\rfloor$ is één factor al geteld. De uiteindelijke formule voor het aantal priemfactoren $p$ in $n!$ wordt 

$$F_p(n)= \sum_{k=1}^T \left\lfloor\frac{n}{p^k}\right\rfloor,$$

waarbij $T$ de grootste macht is die kan voorkomen, dus $T = \log_p(n)$. 

We zijn niet zozeer geïnteresseerd in het aantal priemfactoren van $n!$, maar vooral in dat van $B(n) = {2n\choose n} = \frac{(2n)!}{n!^2}$. Voor het aantal priemfactoren $p$ in $B(n)$ geldt:

$$B_p(n) = F_p(2n) - 2F_p(n) = \sum_{k=1}^T \left\lfloor \frac{2n}{p^k} \right\rfloor- 2\left\lfloor \frac{n}{p^k}\right\rfloor.$$

Merk op dat $\lfloor 2n/p^k\rfloor$ en $2\lfloor n/p^k\rfloor$ niet gelijk hoeven te zijn. De tweede term is altijd even, maar de eerste term kan ook oneven zijn. Bijvoorbeeld $\lfloor 6/5 \rfloor = 1$, terwijl $2\lfloor 3/5\rfloor = 0$. Maar ze kunnen nooit meer dan 1 verschillen. Dat geldt vervolgens voor iedere macht van $p$. Het aantal factoren $p$ kan dus oplopen tot $T$. Dit maximum wordt ook daadwerkelijk bereikt. Op pagina 29 is een tabel weergegeven met $n,\binom{2n}{n}$, het aantal factoren 2, 3, 5, ..., 23. De keren dat het maximum wordt aangenomen zijn vet gedrukt. Maar ook kleinere waarden komen voor. Wanneer $n$ een $p$-voud is, dan zal in bovengenoemde som $\lfloor 2n/p\rfloor – 2\lfloor n/p\rfloor = 0$ gelden. Er geldt zelfs dat het aantal priemfactoren $p$ in $B(n)$ gelijk is aan het aantal priemfactoren in $B(pn)$. (Ga zelf na dat dit klopt in onderstaande tabel.) Ofwel: uitgaande van het aantal priemfactoren in $B(n)$, zal er niets veranderen aan de situatie voor $B(n + 1)$ als $p\neq 2$ en $p ∤n + 1$ en $p∤2n + 1$.

Verder nog een opmerking. Als je de rechterhelft van de tabel bekijkt, dan zie je dat er alleen nullen en enen staan. Dat is geen toeval. Als $n < p < 2n$, dan zal $p ∤n!$, maar wél $p | (2n)!$. En dat betekent dat $B(n)$ precies één factor $p$ heeft. Dus $B(n)$ bevat de factor $(2n)\# / n\#$. Hier komen we nog op terug.

$n$	$B(n)$	$B_2$	$B_3$	$B_5$	$B_7$	$B_{11}$	$B_{13}$	$B_{17}$	$B_{19}$	$B_{23}$
1	2	1	0	0	0	0	0	0	0	0
2	6	1	1	0	0	0	0	0	0	0
3	20	2	0	1	0	0	0	0	0	0
4	70	1	0	1	1	0	0	0	0	0
5	252	2	2	0	1	0	0	0	0	0
6	924	2	1	0	1	1	0	0	0	0
7	3432	3	1	0	0	1	1	0	0	0
8	12870	1	2	1	0	1	1	0	0	0
9	48620	2	0	1	0	1	1	1	0	0
10	184756	2	0	0	0	1	1	1	1	0
11	705432	3	1	0	1	0	1	1	1	0
12	2704156	2	0	0	1	0	1	1	1	1
13	10400600	3	0	2	1	0	0	1	1	1
14	40116600	3	3	2	0	0	0	1	1	1
15	155117520	4	2	1	0	0	0	1	1	1
16	601080390	1	2	1	0	0	0	1	1	1
17	2333606220	2	3	1	0	1	0	0	1	1
18	9075135300	2	1	2	1	1	0	0	1	1
19	35345263800	3	1	2	1	1	0	0	0	1
20	137846528820	2	2	1	1	1	1	0	0	1

Benaderingen

We gaan op zoek naar een benadering van $B(n)$ en van $n\#$. We hadden al gezien dat 

$$\frac{B(n+1)}{B(n)} = 4-\frac{2}{n+1},$$

dus 

$$B(n+1) = \left(4-\frac{2}{n+1}\right)B(n)<4B(n).$$

Ofwel (met behulp van inductie):

$$B(n)<4^n.$$

Met behulp van de formule van Stirling kun je een veel betere benadering krijgen, namelijk:

$$B(n) \approx\frac{4^n}{\sqrt{\pi n}}.$$

We gaan nu kijken naar een benadering voor $n\#$. We kijken hoe ver we komen met de benadering voor $B(n)$, gebruikmakend van $(2n)\# / n\# < B(n)$. Er geldt:

$$(2^k)\# < B(2^{k−1})·B(2^{k−2})·…·B(1)< 4^{2^k} .$$

Eenvoudig valt te extrapoleren dat $n\# < 4^n$. Het blijkt dat $n\# \approx e^n$.

Erdös' vermoeden

Paul Erdős vermoedde dat alleen $B(1) = 2, B(2) = 6$ en $B(4) = 70$ kwadraatvrij zouden zijn. Omdat $B(n) \approx 4n$ en $(2n)\# / n\# \approx e^n$, is er voor het product van de priemfactoren (met multipliciteit) tot $n$ in $B(n)$ bij benadering een factor $(4/e)^n$ over. Als alle priemfactoren kleiner dan $n$ in $B(n)$ zouden voorkomen, dan zou dit de veel grotere waarde en opleveren. Het is dus zeker niet vanzelfsprekend dat er een priemgetal vaker dan eenmaal voorkomt in $B(n)$.

Als je echter de kolom van $B_2$ in de tabel bekijkt, het aantal factoren 2 in $B(n)$, dan zie je dat dit aantal factoren meestal groter is dan 1, en alleen 1 is als $n = 1, 2, 4, 8$ en 16. Er geldt dat het aantal factoren 2 in $B(n)$ altijd groter is dan 1 als $n$ niet een macht van 2 is.

Dit is weliswaar een stap in de richting van een bewijs, maar we zijn er nog lang niet. Voor dit tijdschrift is dit een mooi moment om te stoppen. Want het volledige bewijs dat Andrew Granville en Olivier Ramaré in 1996 gaven, zal de gemiddelde amateurwiskundige boven de pet gaan.

Meer weten?

Weetjes over de rij $B(n)$ vind je onder meer op http://archive.lib.msu.edu/crcmath/math/math/c/c178.htm