Sous-ensembles pairs-impairs

[Tchoumsky]

Bonjour à tous,

Alors voilà, montrer que le nombre de sous-ensembles paires d'un ensemble de n éléments est égal au nombre de sous-ensemble impaires d'un ensemble de n éléments.

Je tente la récurrence sur n. pour n=1, on a l'ensemble vide qui comporte 0 éléments (donc pair) et l'ensemble composé de {1}. Donc c'est bon.
Supposons que la propriété est vraie pour n.
Pour n+1: si on ajoute notre nouvel élément x à tous les S-E de cardinalité impaire ça nous donne des S-E de cardinalité paire. Et vice-versa. Sauf que avec ça le S-E vide est transformé en {x}.
Du coup, je doit oublier quelque chose parce que ça me donne un sous ensemble pair en plus.

Ou est mon erreur?

Merci d'avance pour votre aide

Tchoumsky

[L.A.]

Bonjour.

Je pense que ton erreur vient du fait que tu ne compte que les sous-ensembles qui contiennent x, alors qu'il y a aussi certains sous-ensembles qui ne le contiennent pas.

Sinon, il existe une démonstration en une ligne, si ça t'intéresse.
Petites indications :
Quel est le nombre de sous-ensembles à k éléments dans un ensemble à n éléments ?
Quelle est l'égalité à prouver alors ?

[Tchoumsky]

Ah oui, et donc si je prend mes S-E impairs et pairs de mon ensemble à n éléments et que j'ajoute respectivement mes S-E impairs et pairs contenant x, ça marche.

Nombre de sous-ensembles à k éléments parmi n: n!/(k!(n-k)!)
Du coup il faudrait prouver que la somme pour k allant de 0 à n de 2k parmi n est égale à la somme pour k allant de 0 à n de 2k+1 parmi n. Isn't it?

[L.A.]

OK pour ta récurrence.

Pour la méthode rapide, attention k ne varie pas de 0 à n mais à la partie entière de n/2.
Mais le mieux pour l'écrire serait

Somme{k pair de 0 à n} (k parmi n) = Somme{k impair de 0 à n} (k parmi n)

Maintenant qu'est-ce que t'évoquent ces sommes ?

[Tchoumsky]

Bonjour,

Alors si on fait l'un plus l'autre ça nous donne tous les sous-ensembles d'un ensemble de n éléments.
Et si on fait la différence ça nous donne un binôme de newton avec des coef (-1) pour les k impairs et +1 pour k pairs. J'ai compris le truc.

Merci,

[Doraki]

En version combinatoire, prend un élément au hasard dans ton ensemble et appelle-le x.

Ensuite, regarde l'application qui à un sous-ensemble X associe Xu{x} si x est dans X ; X-{x} si x n'est pas dans X.
Cette application est une bijection entre les ensembles de taille paire et les ensembles de taille impaire.