Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Dénombrement

Posté par
Vendredi
01-01-09 à 20:09

Bonjour, je ne sais pas du tout comment aborder un problème de dénombrement dans E de cardinal n... Comment calculer le nombre de lois de compositions interne, celles qui sont commutatives, celles qui admettent un élément neutre, la somme des  cardinaux de X inter Y ou Y inter X, etc. ?

Posté par
Thibs
re : Dénombrement 01-01-09 à 20:44

Une loi de composition interne ici est une application de (ExE)->E donc on cherche le nombre d'application de (ExE)->E, c'est à dire n[sub][/sub]

Posté par
Vendredi
re : Dénombrement 01-01-09 à 21:04

Pardon, mais la balise [sub] n'a pas été placée au bon endroit ...

Posté par
Thibs
re : Dénombrement 01-01-09 à 21:22

notons x1...xn les éléments de E.
Pour les commutatives, il faut penser que (xi,xj) sont comptés deux fois vu que xi*xj=xj*xi. Pour les compter qu'une fois on va supposer que l'on prend i<=j et donc on trouve n+(n-1)+(n-2)+...+1=n(n+1)/2 couples différents. On a ainsi n^(n(n+1)/2) lois de composition interne commutatives.

Posté par
Thibs
re : Dénombrement 01-01-09 à 21:26

Citation :
Pardon, mais la balise [sub] n'a pas été placée au bon endroit ...

J'ai juste cliqué la balise sans faire exprès (elle est juste au dessus du bouton poster). sinon c'était bien n.

Posté par
Vendredi
re : Dénombrement 01-01-09 à 22:04

Merci, je comprends enfin pour les deux premiers, notamment le deuxième   ... Quant au reste, je m'efforce d'appliquer le même stratagème que pour les lois commutative, mais ne vois pas trop ...

Posté par
Thibs
re : Dénombrement 01-01-09 à 22:31

J'avoue je ne vois pas ce que tu veux dire par:

Citation :
la somme des  cardinaux de X inter Y ou Y inter X, etc.

Pour un élément neutre:
Sans nuire à la généralité, on peut prendre x1 comme l'élément neutre .
Il faut trouver donc les "couples" qui sont répétés. Que trouves tu?

Posté par
Vendredi
re : Dénombrement 01-01-09 à 22:41

Si x1 élément neutre, tous les couples de la forme x1 * y sont répétés, non ? Par "la somme des  cardinaux de X inter Y ou Y inter X", j'entends seulement \sum_{}^{}Card (X U Y)

Posté par
Vendredi
re : Dénombrement 02-01-09 à 18:35

up

Posté par
Vendredi
re : Dénombrement 04-01-09 à 17:06

Deuxième , je ne vois pas comment faire, surtout dans la deuxième partie, avec les \sum_{X et Y appartenant P(E)^2}^{}# (X U Y) et \sum_{X et Y appartenant P(E)^2}^{}# (X inter Y)

Posté par
elhor_abdelali Correcteur
re : Dénombrement 04-01-09 à 19:20

Bonjour ;

Si je comprends bien E est un ensemble fini à n éléments et on demande de calculer en fonction de n :

4$\blue\fbox{U_n=\Bigsum_{X,Y\subset E}Card(X\cup Y)\;\;et\;\;I_n=\Bigsum_{X,Y\subset E}Card(X\cap Y)}

En remarquant que les applications 3$\fbox{\scr P(E)^2\;\to\;\scr P(E)^2\\(X,Y)\to(Y,X)} , 3$\fbox{\scr P(E)^2\;\to\;\scr P(E)^2\\(X,Y)\to(X,Y^c)} et 3$\fbox{\scr P(E)^2\;\to\;\scr P(E)^2\\(X,Y)\to(X^c,Y^c)} sont des bijections

il vient :

4$\fbox{U_n=\Bigsum_{X,Y\subset E}Card(X^c\cup Y^c)=n.2^{2n}-I_n\\U_n-I_n=\Bigsum_{X,Y\subset E}Card(X-Y)+Card(Y-X)=2I_n}

d'où 5$\red\fbox{U_n=3I_n=3n.4^{n-1}} sauf erreur bien entendu

Posté par
Vendredi
re : Dénombrement 04-01-09 à 19:29

Merci, c'est exactement la question, mais je ne vois pas ce que veulent dire les X^{c}ou Y^c.

Posté par
elhor_abdelali Correcteur
re : Dénombrement 04-01-09 à 19:39

C'est une notation du complémentaire 4$\blue\fbox{X^c=E-X}



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !