
Notons, pour tout et pour tout ensemble
de cardinal
:
le nombre de parties de
de cardinal congru à 0 modulo 3
le nombre de parties de
de cardinal congru à 1 modulo 3
le nombre de parties de
de cardinal congru à 2 modulo 3
Comme le nombre de parties de de cardinal
est égal à
alors :
sachant que cette somme doit se poursuivre “tant que c’est possible”, ce qui veut dire qu’on ajoute les entiers
où le symbole
On va faire intervenir le nombre complexe :
qui a le bon goût d’être une “racine cubique de l’unité” ce qui signifie simplement que
En effet, d’après la formule de Moivre :
On observe en outre que :
Maintenant, appliquons la formule du binôme :
On a simplement séparé les
Compte tenu de ce qui a été dit au sujet du nombre complexe on dispose de deux égalités supplémentaires :
Si l’on ajoute membre à membre les relations (1), (2) et (3), tout en tenant compte de
Ceci conduit à :
Voilà déjà une formule explicite pour
Pour cela, on va tâcher de faire disparaître toute référence aux nombres complexes et à la trigonométrie…
On observe que, pour tout :
d’où, en passant aux parties réelles :
Finalement :
Passons à l’examen de la parité de Cette question ne semble pas facile d’accès avec la formule explicite obtenue ci-dessus.
Pourtant, en rédigeant un programme de calcul de (voir en annexe pour une version écrite en Python) et en observant la parité de
pour de petites valeurs de
on découvre une apparente régularité :
Pour
On conjecture donc naturellement que, pour tout :
ce qu’on va maintenant établir rigoureusement.
Pour cela, on va faire un petit raisonnement combinatoire.
Considérons un ensemble de cardinal
et nommons
un élément particulier. Les parties de
dont le cardinal est multiple de
sont :
- les parties de
de cardinal multiple de
- les unions du singleton
avec une partie de
de cardinal congru à 2 modulo 3
Par conséquent :
Considérons maintenant un ensemble de cardinal et nommons
deux éléments particuliers. Les parties de
dont le cardinal est multiple de 3 sont :
- les parties de
de cardinal multiple de
- les unions de l’un des deux singletons
ou
avec une partie de
de cardinal congru à 2 modulo 3
- les unions de la paire
avec une partie de
de cardinal congru à 1 modulo 3
Par conséquent :
Considérons enfin un ensemble de cardinal et nommons
trois éléments particuliers. Les parties de
dont le cardinal est multiple de 3 sont :
- les parties de
de cardinal multiple de
- les unions de l’un des trois singletons
ou
avec une partie de
de cardinal congru à 2 modulo 3
- les unions de l’une des trois paires
ou
avec une partie de
de cardinal congru à 1 modulo 3
- l’union de
avec une partie de
de cardinal multiple de 3
Par conséquent :
En combinant
et
on obtient la relation de récurrence linéaire d’ordre 3 suivante :
Annexe : programmation en Python
Calcul des coefficients binomiaux (solution récursive, utilisant la formule du pion)
def binomial(n,k): if k == 0: return 1 elif 2 * k > n: return binomial(n, n-k) else: return (n * binomial(n-1,k-1)) // k
Calcul de la somme
def A(n): s = 0 k = 0 while k <= n: s += binomial(n, k) k += 3 return s
Pour consulter l’énoncé, c’est ici