Forum de mathématiques - Bibm@th.net

NadjaV

Membre

Inscription : 17-11-2021

Messages : 2

Cardinal d'un ensemble

Bonjour, Pouvez vous m'aider avec cette exo?

Soit E un ensemble fini de n éléments et soit [tex](A_1,…,A_k )∈P〖(E)〗^k[/tex] une famille de parties de E sans relation d’inclusion, c’est-à-dire telle que
[tex]∀(i,j)∈[[1;k]]^2,(i≠j⟹A_i⊄A_j)[/tex]
Montrer que si l’on pose
[tex]p_i=card(A_i)[/tex],
alors on a
[tex](∑ p_i !(n-p_i )!)≤n! [/tex] (Somme de i=1 à k)
Indication : on pourra considérer toutes les familles [tex](C_0,…,C_n )[/tex] de E vérifiant [tex]card(C_i )=i[/tex] pour 0≤i≤n et [tex]C_i⊂C_(i+1[/tex]) pour 0≤i≤n-1

Merci beacoup

Dernière modification par NadjaV (17-11-2021 19:05:00)

NadjaV

Membre

Inscription : 17-11-2021

Messages : 2

Re : Cardinal d'un ensemble

Moi aussi, mais algébriquement, ce n'est pas correct.
On ne peut pas inverser une fraction et changer l'inégalité s'il y a une sommatoire.

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 230

Re : Cardinal d'un ensemble

re,
tu as raison et c'est la raison pour laquelle que je viens de ... la supprimer..
Dans l'indication on dirait qu'on te propose un raisonnement par l'absurde..

Dernière modification par Zebulor (17-11-2021 22:03:54)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 912

Re : Cardinal d'un ensemble

Bonjour,

Apparemment, le terme de gauche de l' inégalité ( avec les sommes ) est exactement le nombre de [tex](C_0, C_1,..., C_n) [/tex] tels qu'ils on été définis, mais avec la restriction  qu' 1  des [tex]C_i [/tex] ( exactement 1 selon la propriété des [tex]A_i[/tex] de non-inclusion supposée) est l'un des [tex]A_i[/tex], ces ensembles d'uplets étant donc disjoints, on en a donc  le total exactement en les ajoutant...
Comme au total ( sauf erreur de ma part) on a n!  uplets du type [tex](C_0, C_1,..., C_n) [/tex] ( les [tex]C_i [/tex] étant ou non égaux à un [tex]A_i[/tex] ),
on en donc forcément pas plus dans le premier calcul qu'en prenant la factorielle de n.

Graphiquement, ce qui se passe... :

https://www.cjoint.com/c/KKsjwnYaGpg

C'est amusant.

Alain

Dernière modification par bridgslam (18-11-2021 10:25:36)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 912

Re : Cardinal d'un ensemble

Bonjour,

ou si l'on préfère une notation symbolique ( le " | " mettant en évidence l'emboitement ensembliste:

Les uplets avec [tex]A_1[/tex] qui s'emboitent par pas progressif de 1 élément :

<---------------[tex]A_1[/tex]-------------->
. | . | ....................................| . | ................................................ | . |
<---------------- [tex]p_1 ![/tex] -------------><--------------[tex](n-p_1)![/tex] -------------->
                         possibilités                                    possibilités

Même principe avec [tex]A_2[/tex] , dont les uplets sont  forcément distincts des précédents, [tex]A_3[/tex] etc.

Mais le nombre total d'uplets possibles quelconques est n!.
D'où l'inégalité indiquée.

Alain

Dernière modification par bridgslam (19-11-2021 15:12:29)

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 912

Re : Cardinal d'un ensemble

Bonjour,

Pour voir mieux les choses tu peux prendre par exemple E avec 3 éléments, et pour parties A par exemple des parties distinctes de même cardinaux égal à 2 (pourquoi pas), donc vérifiant automatiquement les hypothèses de non-inclusion.

exemple 1 : [tex]A_1 = \{1,2\} , A_2 = \{2,3\}[/tex] et E ={1,2,3}

On a 6 = 3! possibilités globales, dont 2!1! pour celles avec [tex]A_1[/tex], 2!1! pour celles avec [tex]A_2[/tex], à expliciter... c'est rapide.
On a ici une inégalité stricte.

exemple 2: [tex]A_1 = \{1,2\} , A_2 = \{2,3\}, A_3 = \{1,3\}[/tex] et E ={1,2,3}

Cette fois on a l'égalité puisque on a pris en compte toutes les parties à 2 éléments.
Une suite [tex](C_i)[/tex] sera  forcément  une suite passant par l'une ou l'autre des [tex]A_i[/tex]...

Tu peux essayer aussi avec E = {1,2,3,4} [tex]A_1 = \{1,2\} , A_2 = \{2,3 ,4 \}, A_3 = \{1,3, 4\}[/tex] c'est-à-dire une partie de E à 2 éléments et  deux à 3 éléments.
Lister les chaînes est assez rapide par effet de rotations sur les éléments.
Ici 4!= 24 >  2!2! + 3!1! + 3!1! (= 16)

Dans tout cela on peut voir aussi une petite application arithmétique en creusant un peu:
Si n est un entier, une suite d'entiers [tex](n_i)[/tex]inférieurs à n est dite n-exclusive  ssi il existe une famille de parties [tex]P_i[/tex] de {1,..,n} telle que :
- [tex]\forall i \; Card( P_i) = n_i[/tex]
- aucunes de ces parties ne se contiennent  2 à 2.

Alors le résultat précédent montre que : [tex]\forall \;s , \;n-exclusive, \; \sum_{k \in s} \frac {1}{\binom{n}{k}} \le 1[/tex]
En cas particulier on a évidemment l'égalité triviale pour la suite s = ( k,k,k,...k) à [tex]\binom{n}{k}[/tex] termes clairement n-exclusive,
car dans la somme précédente on ajoute [tex]\binom{n}{k}[/tex] égaux  à [tex] \frac {1}{\binom{n}{k}} [/tex]...

Pour les fans de programmation, et de Python ou Java en particulier, il doit être faisable de déterminer pour un entier naturel n donné l'ensemble de ses suites n-exclusives (terme que j'ai sorti de ma besace, aucune nomenclature officielle, ou alors ce serait une coïncidence :-)  ),et par voie de conséquence de vérifier l'inégalité dans chaque cas.
De mémoire certains langages permettent de gérer les opérations ensemblistes, je l'avais fait sur un jeu de jetons en Java il y a quelques années, que j'avais proposé à deux stagiaires.

Alain

Dernière modification par bridgslam (19-11-2021 09:42:28)