[Défi] Formule de Boole-Sylvester (ou principe d'inclusion-e

[Zweig]

Salut,

Un petit défi de combinatoire pour changer.

Cas particulier.

Soit une famille d'ensembles finis. Montrer la formule suivante :

[CENTER][/CENTER]

Généralisation.

Soit un ensemble fini et . Pour tout ensemble , on pose :

avec . Si , montrer la relation suivante :

[CENTER][/CENTER]

Application 1 : Indicatrice d'Euler

On note , l'indicatrice d'Euler.

a) Soit un nombre premier et un entier naturel. Déterminer .

b) A l'aide de la formule de Boole-Sylvester (cas particulier), déterminer une formule close pour

Application 2 : Szego & Polya, 1925

Soient n >1 un entier naturel et les entiers naturels de l'ensemble qui sont premiers avec . Montrer la relation suivante :

[CENTER]
[/CENTER]
où les sont les diviseurs premiers de .

On admettra la formule suivante :

[benekire2]

Salut Zweig,

Pour la deuxième application je connais, mais c'est vraiment pas simple ...

[Zweig]

Je n'ai jamais dit que c'était simple . Encore que là je "donne" la formule à utiliser (la généralisation avec une fonction f bien choisie). A partir de là, c'est plus du calcul que du raisonnement à entreprendre.

[Anonyme]

Dans la generalisation c'est qui ?

[Zweig]

Le même I que le cas particulier : c'est une somme sur l'ensemble des parties de [1, n].

[ft73]

en fait ta formule, c'est la formule de Poincaré pour les probas ?

[Zweig]

Oué voilà, la formule a plusieurs noms ...

[Anonyme]

J'ai demontrer le cas particulier et la generalisation par recurrence (pas tres facile, avec toutes les notations). C'est ce que vous avez fait ?

J'aimerais avoir une petite confirmation le cas particulier se deduit de l'application du cas general a la fonction f(x)=1 ?

[Zweig]

Oui, ça se fait par récurrence et oui le cas particulier se déduit du cas général avec la fonction f(x)=1.

[Anonyme]

Alors pour l'application 1:

a)


Pour la b) je reflechis pour l'instant j'ai aucune idee (edit: c'est plus vrai :zen: ) mais deja c'est quoi une formule "close" ?

[Zweig]

Par formule close, j'entends une formule en fonction de (et éventuellement, de ses diviseurs premiers ...)

a), c'est ok.

[Anonyme]

Pour la b)

Tout entier n s'ecrit sous la forme .
(p_i sont des nombres premiers)

Soit l'ensemble des multiples de inferieurs a .
On a (pas besoin de partie entiere puisque )

De plus il est clair que

On applique la formule:



On peut factoriser (heureusement) cette expression et on obtient:



C'est bon ?

[Zweig]

Le raisonnement est bon, peut-être tu pourrais un peu plus détailler tes calculs ?

[benekire2]

Sinon, on démontre la multiplicité de l'indicatrice d'Euler et on conclu !

[Zweig]

Sauf que cette démonstration (via le dénombrement) a le mérite d'être élémentaire, la tienne fait quand même appel, "pour conclure", a des arguments de théorie algébrique des nombres (groupe produit, générateur etc ...), HP pour un lycéen donc ...

[benekire2]

Oui oui, je le sais, c'est simplement que je pense que ces deux démos n'ont pas du tout les mêmes objectifs "pédagogiques" dans le sens où ce n'est pas du même niveau, :id:

[Zweig]

Quelqu'un pour la dernière question (la plus délicate) ? Je peux donner quelques indices au besoin.

[Anonyme]

En ce qui me concerne j'ai quelques idees mais en ce moment je suis un peu pris par l'exercise de Nightmare.
Voila ce que je pense faire des que j'aurais fini:


Les etant les entiers ayant un diviseur commun avec n.

On peut obtenir une formule de la somme des en applicant la generalisation du theoreme a la fonction et a l'union des intervalles definis precedemment.

J'ai pas essaye mais je ne crois pas que ca soit si direct de ca a moins que les calculs soient assez compliques.

[Zweig]

Exact, c'est le bon raisonnement ! Après, le reste, ce n'est que du calcul (un poil compliqué, en effet !).