Dénombrement

[Kikoo <3 Bieber]

Hello,

Bon, je vous expose rapidement le contexte.
On considère un ensemble que l'on met en bijection avec un ensemble par une application f définie par pour des i et j de .
Omega est l'ensemble de toutes ces bijections possibles. un ensemble quelconque partie de , et son complémentaire dans .
Pour j fixé de l'intervalle entier , on note et .

Je dis que si f appartient à D, alors il appartient à l'ensemble des bijections qui à chaque renvoient un élément indicé avec . Juste ?

Par contre, avec fixés, je ne sais pas comment faire pour justifier que l'on a :



Ca doit pas être si difficile que ça... une petite piste s'il-vous-plait ?

Merci

[eilimee1229]

Bonjour à tous,
je suis désolée de déranger... J'ai besoin d'aide pour un calcul de factorisation que j'ai à faire pour la rentrée et je n'y arrive pas... Je suis vraiment nulle en maths... Si vous pouviez m'expliquez comment faire je vous serai très reconnaissante .
Merci d'avance

Voilà le calcul:

(5*x-1)*(3*x+2)+25*x²-1

Je me suis dit, qu'il fallait sans doute utiliser des facteurs communs? ou peut-être les identités remarquables? Mais malgré toutes mes tentatives, je suis malheureusement arrivée à des résultats très peu concluants...

[Kikoo <3 Bieber]

Bonjour à tous,
je suis désolée de déranger... J'ai besoin d'aide pour un calcul de factorisation que j'ai à faire pour la rentrée et je n'y arrive pas... Je suis vraiment nulle en maths... Si vous pouviez m'expliquez comment faire je vous serai très reconnaissante .
Merci d'avance

Voilà le calcul:

(5*x-1)*(3*x+2)+25*x²-1

Je me suis dit, qu'il fallait sans doute utiliser des facteurs communs? ou peut-être les identités remarquables? Mais malgré toutes mes tentatives, je suis malheureusement arrivée à des résultats très peu concluants...

Ohééé !!!! Pas de ça sur mon topic quand même !! ^^ (mais je suis content, ça me fait un petit up, merci)

Si tu veux créer ton propre topic, tu vas dans la section adaptée et tu cliques sur "nouveau message" en haut à gauche. Et dire que Sylviel avait créé un sujet à propos de ça...

Bref, tant que j'y suis je vais répondre : tu remarques vite fait que 25x²-1 c'est de la forme a²-b² que tu factorises aisément. Puis tu remarques que dans ce que tu obtiens, ya un facteur commun que tu exposes devant, tu réduis blablabla et c'est fini.

Voili voilou

PS : finalement je ne suis pas content. Tu aurais pu regarder comment poster un message au lieu d'infester les topics d'au moins 3 personnes ! C'est vraiment pas poli !!

[Yann64]

Hello,

Bon, je vous expose rapidement le contexte.
On considère un ensemble que l'on met en bijection avec un ensemble par une application f définie par pour des i et j de .
Omega est l'ensemble de toutes ces bijections possibles. un ensemble quelconque partie de , et son complémentaire dans .
Pour j fixé de l'intervalle entier , on note et .

Je dis que si f appartient à D, alors il appartient à l'ensemble des bijections qui à chaque renvoient un élément indicé avec . Juste ?

Par contre, avec fixés, je ne sais pas comment faire pour justifier que l'on a :



Ca doit pas être si difficile que ça... une petite piste s'il-vous-plait ?

Merci

est l'ensemble des bijections laissant invariable il ne reste de variable donc que n-j éléments, puis comme ce sont des bijections ...

[Kikoo <3 Bieber]

J'ai compris ton explication Yann, merci beaucoup et bonnes fêtes ;)

[Yann64]

Bonnes fêtes à toi aussi ;)

[Kikoo <3 Bieber]

Re,

J'ai du mal à trouver card(D)...

[Kikoo <3 Bieber]

Petit up

Plus précisément, je pense que et trouver le nombre de bijections qui ne laissent pas de points invariants, c'est tout d'abord choisir entre n-1 éléments de F pour un élément de E, ce qui nous laisse théoriquement n-2 choix pour un deuxième élément de E. Ce qui pose problème selon moi c'est que si l'on a d'ores et déjà pioché l'élément de F dont l'indice correspond au deuxième élément de E, alors nous aurions en un second temps non pas n-2 choix mais n-1 pour cet élément. Je pars peut-être dans des élucubrations pas possibles...

Le but est de montrer que

PS : je viens de trouver que l'intersection des complémentaires de n ensembles est le complémentaire de la réunion de ces ensembles... Je vais voir si ça donne quelque chose.

PPS : quoique... peut-être seulement pour deux ensembles, je ne sais pas... A l'aide !!! ^^'

[Yann64]

Petit up

Plus précisément, je pense que et trouver le nombre de bijections qui ne laissent pas de points invariants, c'est tout d'abord choisir entre n-1 éléments de F pour un élément de E, ce qui nous laisse théoriquement n-2 choix pour un deuxième élément de E. Ce qui pose problème selon moi c'est que si l'on a d'ores et déjà pioché l'élément de F dont l'indice correspond au deuxième élément de E, alors nous aurions en un second temps non pas n-2 choix mais n-1 pour cet élément. Je pars peut-être dans des élucubrations pas possibles...

Le but est de montrer que

PS : je viens de trouver que l'intersection des complémentaires de n ensembles est le complémentaire de la réunion de ces ensembles... Je vais voir si ça donne quelque chose.

PPS : quoique... peut-être seulement pour deux ensembles, je ne sais pas... A l'aide !!! ^^'

Je crois que
Comme
On connait le cardinal de oméga, reste à trouver le cardinal de l'union des [tex]A_i[tex]et à le retrancher au cardinal de oméga.
Je ne suis pas plus avancé que toi.

[Kikoo <3 Bieber]

Merci beaucoup pour ton aide ! Je commençais à perdre espoir.

J'ai dû commencer l'exo par la démonstration (par récurrence) de la formule du crible de Poincaré.
Donc cela me permet de donner :

.
Sachant que , j'ai
(je doute un peu pour cette dernière ligne).
Mais après ça bloque...

J'y réfléchis !

[Kikoo <3 Bieber]

Une petite idée ? Je sèche pas mal...

[Doraki]

Merci beaucoup pour ton aide ! Je commençais à perdre espoir.

J'ai dû commencer l'exo par la démonstration (par récurrence) de la formule du crible de Poincaré.
Donc cela me permet de donner :

.
Sachant que , j'ai
(je doute un peu pour cette dernière ligne).
J'y réfléchis !

Moi, à n et j fixés, quand je remplace par dans ,
j'obtiens ,
qui est d'ailleurs égal à
Tu peux calculer cette somme de 1s lorsque j=1 ou 2 (ou 3) en fonction de n, pour voir ?


Je comprends pas trop d'où tu sors ta somme de (n-k)! pour 1<=k<=j.

[Kikoo <3 Bieber]

Salut Doraki,

C'est moi qui n'ai pas parfaitement compris la formule sommatoire quand on indice pour les i1<...Mais au moins cela me permettra d'avancer !
Du coup la somme devient j(n-j)! ?

Hmmm en fonction de n ? Je vois pas trop...

[Doraki]

ben par exemple pour j=1 et n=4, que veut dire "somme pour 1<=i1<=4 de 1" ?
et pour j=2 et n=4, que veut dire "somme pour 1<=i1

[Kikoo <3 Bieber]

ben par exemple pour j=1 et n=4, que veut dire "somme pour 1<=i1<=4 de 1" ?
et pour j=2 et n=4, que veut dire "somme pour 1<=i1<i2<=4 de 1" ?

Ah oui ! Je dois vraiment me mettre à réviser ça :marteau:

Alors la somme des 1 pour 1<=i1<=4 vaut 4.
La somme des 1 pour 1<=i1<i2<=4 vaut la somme de i2 à 4 de la somme de 1 à i1 des 1 et cela vaut : i1*(4-i2+1)

[Doraki]

La somme des 1 pour 1<=i1<i2<=4 vaut la somme de i2 à 4 de la somme de 1 à i1 des 1 et cela vaut : i1*(4-i2+1)

Non, ça veut dire 1 (pour i1=1 et i2=2) + 1 (pour i1=1 et i2=3) + 1 (pour i1=1 et i2=4) + 1 (pour i1=2 et i2=3) + 1 (pour i1=2 et i2=4) + 1 (pour i1=3 et i2=4).

Des manières alternatives de l'écrire qui vont moins te confondre que "somme pour 1<=i1<i2<=4 de ... ", c'est "somme pour (i1,i2) dans {(i1,i2) de N*N / 1<=i1<i2<=4} de ...", ou bien "somme pour 1<=i1 de somme pour i1<i2<=4 de ..."

Dans la formule du principe inclusion-exclusion,
"somme pour 1<=i1<i2<...<ij<=n de |Ai1 inter Ai2 inter ... Aij|"
est une manière un peu moche de dire
"somme pour toutes les parties I de {1..n} de cardinal j, de |intersection pour i dans I des Ai|",
et la formule entière est aussi une manière un peu moche de dire
"0 = |réunion pour i dans {1..n} des Ai| + somme pour I une partie non vide de {1..n} de (-1)^|I| * |intersection des Ai pour i dans I|"

(et on peut considérer que l'intersection vide devrait correspondre à la réunion des Ai, et juste dire 0 = somme pour I une partie de {1..n} de (-1)^|I| * |intersection des Ai pour i dans I|)

[Kikoo <3 Bieber]

Ok ! Je pense que je vois mieux.

Nous avons pour allant de 1 à n-1 et allant de 2 à n.
Donc nous sommons 1 tout d'abord n-2+1=n-1 fois 1, puis n-2, puis n-3 puis, ..., puis 1 fois.
Ce qui nous donne la somme

Maintenant il faut que j'étende ce raisonnement à un nombre fixé de j éléments... :hum:

[Kikoo <3 Bieber]

Je me suis fait un petit arbre pour essayer de dénombrer le nombre de sommations pour j éléments fixés.

Sachant que pour , j'ai n-j+1 branches ce qui donne (n-j+1)+(n-j)+...+1 (rien que pour ).
Pour , j'ai n-j branches avec une sommation de (n-j)+...+1
Etc.
Pour , il me reste deux branches, qui me donnent 1+2

J'ai donc écrit que
(merci calculatrice)

Mais vu la lourdeur du résultat, je doute que cela soit juste...

PS : Autrement j'ai qui semble fonctionner pour n=5 et en considérant 3 éléments , et (et ça a l'air d'autant plus juste que je vais jusqu'à 2 branches au lieu d'une seule).
Par contre, elle est fausse pour n=4 et deux éléments et

PPS : finalement je ne sais pas...

[Doraki]

ouh là ouh là.
Déjà, ton résultat contredit tes résultats précédents (qui sont justes), n (pour j=1) et n(n-1)/2 (pour j=2) .

i1 a n-j+1 valeurs possibles, mais c'est pas tellement le nombre de valeurs possibles qu'ont veut c'est surtout combien il y a de feuilles dans chaque branche.
Quand tu regardes la branche i1=1, tu dois alors compter le nombre de moyen de choisir i2...ij tels que 2 <= i2 < i3 ... < ij <= n. Je suis pas sûr que les machins que tu sommes correspondent à ça.

Pour la branche i1 = n-j, il y a alors deux branches pour i2, certes, mais dans une de ces branches il y a deux branches pour i3, etc.

Et pour i1=n-j+1, t'as pas le choix pour tout le reste, il faut prendre ik = n-j+k, donc LA, tu as une seule feuille dans cette branche, ok.

Appelle N(j,n) le nombre de moyens de choisir i1..ij tels que 1 <= i1 < ... < ij <= n.
Selon la valeur de i1 tu as bien différentes branches.
Mais est-ce que tu pourrais pas relier dans chaque cas, le nombre de moyens de choisir i2...ij tels que i1 < i2 < ... < ij <= n à un certain N(j',n') pour j' et n' bien choisis ?


Et puis si tu lis bien mon dernier post y'a quasiment marqué explicitement la réponse à la question "que vaut N(j,n) ?"

[Kikoo <3 Bieber]

Je vais le faire à la bourrin car j'arrive pas à faire le lien entre le nombre N(j,n) et le nombre N(j',n'). J'y réfléchirai sans doute après si j'y arrive.

Il me semble vraiment plausible de faire ainsi, au vu des arbres que j'ai déjà tracé :
Pour i1=1, j'ai n-j choix pour i2, puis n-j-1 choix pour i3 etc. Lorsque j'arrive à ij, j'ai n-j+1 choix, puis n-j choix lorsque i_(j-1) n'a que n-j choix, ainsi de suite. J'ai donc (n-j+1)+(n-j)+...+1 feuilles pour cette ramification (i1=1) non ?
Pour i1=2, je fais pareil en enlevant cette fois-ci (n-j+1) donc j'ai (n-j)+...+1 feuilles pour cette ramification.
Je vais jusqu'à i1=n-j+1, ce qui me laisse une seule feuille pour cette branche.

Donc je somme :

_1+...+(n-j-1)+(n-j)+(n-j+1)
+1+...+(n-j-1)+(n-j)
+...
+1+2+3
+1+2
+1
_________________________
blah-blah (deuxième somme de mon avant-dernier message)

N'est-ce pas juste ? C'est ce que tu viens de dire il me semble :/