Fonction caractéristique

[xixxxxx]

Bonjour,

Lorsque est un ensemble et une partie de , on note la fonction caractéristique de A qui est définie par : pour tout , si et sinon.

Je cherche à établir la formule :


Évidemment, j'entreprends une récurrence.

1) J'ai vérifié que la formule fonctionne pour les cas .

2) Supposons la formule établie pour un certain entier . Maintenant, et c'est là que mon malheur commence, il faut l'établir au rang .

Voilà où j'en suis :

d'après le cas

J'utilise maintenant l'hypothèse de récurrence :


Maintenant, je coupe la première somme en deux en isolant le cas , ce qui permet d'obtenir :


Ensuite, je développe les , ce qui permet d'obtenir :


Est-ce correct ? Si oui, est-ce que quelqu'un peut m'aider à conclure, cela fait un très long moment que je suis sur cet exercice. J'ai essayé de donner les détails dans ma démarche.

Cordialement.

[Doraki]

"en isolant le cas k=1" : mauvaise idée.

Tu pourrais utiliser que "1(A inter B) = 1A * 1B", ce qui clarifie et facilite un peu les calculs (on a plus l'habitude de manipuler * que des intersections)

Ensuite j'crois que tout le calcul finalement revient à dire que

1_(réunion des Ai) = 1 - 1_(intersection des complémentaires des Ai) = 1 - produit des 1_(complémentaire de Ai) = 1 - produit des (1 - 1_Ai), et de développer ce produit.

[xixxxxx]

Et le il faut le développer ?

[xixxxxx]

Bon j'essaye de remplacer les intersections alors. J'obtiens :


Que faire ensuite ? :triste:

[barbu23]

Ton exo ressemble beaucoup à ce qui est écrit ici : http://fr.wikipedia.org/wiki/Principe_d%27inclusion-exclusion#Version_probabiliste
:hum:
Y'a-t-il un lien entre entre les deux ?

[Polytop]

soit x un élément de X.
Appliquons à x les deux membres de l'équation.
1° Elle est vérifiée si x n'appartient à aucun des Ai (des 0 partout) ;
2° Elle est vérifiée si x appartient à tous les Ai, car le 1er membre vaut 1 et le second sont les termes du développement de 1-[(1-1) puissance n], les images de toutes les fonctions caractéristiques valant 1.
3° On remarque que la formule est invariante par permutation des Ai.
Si l'un des Ai au mois contient x, on permute les indices de telle manière que x appartienne aux premiers jusqu'à l'indice p inférieur à n, n'appartienne pas aux suivants,
On remarque qu'on peut alors supprimer tous les Ai d'indice strictement supérieur à p, et l'on retrouve le cas 2°.

[xixxxxx]

Je relance, quelqu'un peut m'aider à terminer ma récurrence ?

On en est là :


Comment aboutir au résultat ?

[Polytop]

Vous êtes-vous aperçu que par mon message précédent je vous ai proposé une solution complète ?

[xixxxxx]

Oui, désolé mais je ne comprends pas non plus.

1) Ok

2) je ne vois pas que le second terme vaut 1.

3) formule invariante par permutation des Ai : OK.
Je ne comprends pas la suite.

[Polytop]

Pour le 2° :
Si les fonctions caractéristiques prennent toutes la valeur 1, la seconde somme du second membre est un coefficient du binôme : c'est le nombre de parties à k éléments d'un ensemble à n éléments, pour k non nul. Si on ajoute -1 au second membre, on remarque que tous les termes du second membre sont les opposés de ceux du développement de (1 - 1)^n par la formule du binôme. Donc le second membre - 1 vaut 0, donc le second membre vaut 1.

[Polytop]

Pour le 3°
Si x appartient à l'un au mois des Ai (sinon on serait dans le cas 1°)
On met en premier les Ai qui contiennent x. Soit p leur nombre. Leurs indices vont de 1 à p après ré-indiciation. Au premier membre comme au second, on remarque qu'on peut ne mener la sommation que jusqu'à p, au lieu de la mener jusqu'à n