dénombrement relation d'équivalence

Posté par lyly39 lyly39

bonjour,
J'ai un problème que je n'arrive pas a résoudre.
Je dois trouver que le nombre R_n de relation d'équivalence d'un ensemble fini de cardinal n vérifie la relation de réccurence :
R_n+1= C_n^k R_k
Est ce que quelqu'un pourrait m'aider??
Merci d'avance.

Posté par carpediem carpediem

salut

quand tu ajoutes un élément tu peux:
créer une nouvelle classe d'équivalence où il est seul
ou le relier à une de tes classes déquivalence de la relation r_i parmi tes R_kclasses d'équivalence et tu as C_n^kfaçon de le faire...
voila peut-être une idée
ce me semble-t-il

Posté par dormelles dormelles

Bonjour,
Sans doute je me trompe mais je ne trouve pas cette formule exacte :
R₀=0; R₁=1; R₂=2; R₃=5; or (2,1)R₁+(2,2)R₂=4

Posté par carpediem carpediem

salut

moi aussi je trouve comme toi jusqu'à R3 et j'ai le même problème
peut-être faut-il poser R0=1 par convention (car on peut dire ce qu'on veut des éléments de l'ensemble vide ainsi tout le monde sait que les fourmis de plus de 1000 tonnes sont bleues)ou alors quels sont les indices dans la sommation...

Posté par dormelles dormelles

Sauf erreur , poser R₀=1 ne suffit pour R₄

Posté par stokastik stokastik

Comme l'a remarqué carpediem, le problème revient à dénombrer le nombre de partitions d'un ensemble à  n  éléments, car il y a une correspondance entre relations d'équivalence et partition.

Une recherche sur le forum pourait donner des topics où la question est traitée.

Quant à R0, c'est effectivement 1 formellement. Une relation d'équivalence sur  E  peut être vue comme une application de  ExE  dans l'ensemble à deux éléments  {vrai,faux}, avec certaines conditions. Il y a formellement une application de  ExE  dans  {vrai,faux}, et elle vérifie les conditions de relation d'équivalence, car ces propriétés commencent par "quel que soit x dans E, ...". Le contraire est: "il existe  x  dans  E  tel que ...". Or E est vide, il n'y a pas d'élément  x  dans E.

Posté par stokastik stokastik

_correction



... je voulais dire: Il y a formellement une application de  ExE  dans  {vrai,faux} quand E est vide.

Posté par stokastik stokastik

PS: ce qui est bien cohérent avec la correspondance avec les partitions: il y a une partition de l'ensemble vide

Posté par dormelles dormelles

Pas d'accord : dans une partition aucune des parties n'est vide.

Posté par stokastik stokastik

Ca dépend de comment on définit une partition, mais ici tu n'as pas tort, si on veut identifier une relation d'équivalence à une partition, on aurait tendance à ne pas autoriser la partie vide dans les partitions, car la partie vide n'est la classe d'équivalence d'aucun élément de  E, puisque que la classe d'équivalence de  x  contient au moins  x.

Ceci dit si on définit une classe d'équivalence comme étant une partie de  E  dont les éléments vérifient tous la relation deux-à-deux, alors on ne peut nier que la partie vide est une classe d'&quivalence.

Bref il y a là un petit problème techinque. À part ça je n'ai pas réfléchi à la formule, donc je n'ai rien d'autre à dire. En tous cas, ce que je disais avant mon "PS" est formel: il y a 1 relation d'équivalence sur l'ensemble vide.

Posté par dormelles dormelles

Il n'y a aucune ambiguité sur la définition de classe d'équivalence : aucune ne peut être vide.

Posté par stokastik stokastik


Là n'est pas la question. On se questionne ici à propos de R0=1. Mais bon inutile d'en dire plus, tu n'as pas l'air de vouloir participer à la réflexion.

Posté par lyly39 lyly39

merci pour toutes les aides apportées et dsl de ne pas avoir participé a la réflexion (on ne peu paqs etre partout)... en tout cas je vais creusé le sujet !

Posté par Fractal Fractal

Bonjour
Je m'incruste un petit peu


Justement, dans la partition de l'ensemble vide il n'y a aucune partie, donc a fortiori il ne peut pas y en avoir de vide puisqu'il n'y en a pas.

Fractal

Posté par Mariette Mariette

Bonsoir,

euh j'ai pas compris là...

Fractal : tu dis "il existe une partition de l'ensemble vide, un ensemble vide (ensemble d'ensembles)" ou tu dis "il n'existe pas de l'ensemble vide" ?

Posté par stokastik stokastik

Le nombre de partitions d'un ensemble à n éléments est appelé nombre de Bell . On pose bien . Ce qui est contradictoire dans wiki avec la définition de partition, qui exige qu'aucun élément de la partition ne soit la partie vide.

La définition de partition autorisant la partie vide n'est pas du tout inhabituelle. Le problème si on l'autorise c'est qu'on aurait la partition  {{1},{2}}  de l'ensemble  {1,2}  ainsi que la partition  {{1}, {2}, vide}... si on distingue deux telles partitions, on n'a pas le bon "nombre de Bell".

Il faudrait alors:

- exiger que la partie vide appartienne à une partition
- ou alors identifier 2 partitions qui ne différent que par la partie vide

Le vide serait toujours une classe d'équivalence d'une relation d'équivalence si on prend cette définition de classe d'équivalence: une partie de  E  dont les éléments vérifient tous la relation deux-à-deux.

Mais il faudrait prendre garde à définir l'ensemble quotient comme l'ensemble des classes d'équivalence, sans la partie vide...

Autoriser la partie vide permettrait aussi de dire qu'à une application  f:X -> E  où  X  est un ensemble quelconque, on peut associer une partition de X: l'ensemble des images réciproques par f des singletons de E. Si  f  n'est pas surjective il y a la partie vide dans la partition.

Posté par stokastik stokastik

De wiki:



J'ai dit une bêtise; Je pensais que la partition de l'ensemble vide c'était l'ensemble {vide}, mais c'est l'ensemble vide...

Posté par stokastik stokastik

... et y'a donc pas de contradiction avec si on interdit la partie vide

Posté par stokastik stokastik

Rigolo que B_n est le moment d'ordre n d'une loi de Poisson de paramètre 1. On peut ainsi approcher les B_n par simulation:

# 50000 simulations d'une loi de Poisson de paramètre 1
sims <- rpois(50000,1)
# nombres de Bell
n<-0
while(n < 20){
    n <- n+1
    B <- mean(sims^n)
    print(B)
}
[1] 1.0133
[1] 2.04022
[1] 5.12642
[1] 15.40006
[1] 53.2013
[1] 205.8122
[1] 875.3424
[1] 4035.179
[1] 19921.35
[1] 104227
[1] 572546.9
[1] 3275520
[1] 19380010
[1] 117889630
[1] 733708526
[1] 4653257480
[1] 29974833145
[1] 195599666594
[1] 1.290183e+12
[1] 8.586967e+12

Posté par Fractal Fractal


Voilà, c'est ce que je voulais dire, l'ensemble vide possède bien une partition qui est vide (mais vraiment vide, pas qui contient l'ensemble vide)

Fractal