Enumerateur d'arrangements

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
JPMoulin
Membre Naturel
Messages: 18
Enregistré le: 07 Déc 2014, 11:27

enumerateur d'arrangements

par JPMoulin » 18 Mar 2017, 21:55

Bonjour.je viens d'etudier les fonctions generatrices et leur emploi comme enumerateur et denombreur de combinaisons.
Je prends l'exemple le plus simple possible :



qui nous donne les combinaisons de trois objets e1,e2 et e3 pris trois a trois, deux a deux et un a un.
On reconnait la formule du binome.

Ensuite l'auteur (Arnold Kaufmann dans son livre introduction a la combinatorique) dit que pour obtenir un enumerateur d'arrangements, il conviendrait de construire une algebre non commutative de fonctions generatrices.
J'ai cherche un peu partout et assez longuement un cours ou un ouvrage ou est expliquee la construction de cette algebre sans rien trouver.

Quelqu'on connait il donc un cours ou un ouvrage traitant ce sujet ?

Merci

J-P Moulin



Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 14:31

Re: enumerateur d'arrangements

par zygomatique » 18 Mar 2017, 22:36

salut

la partie {a, b} est la partie {b, a}

l'arrangement (a, b) n'est pas l'arrangement (b, a) ... donc il ne faut pas la commutativité


si G = E U F est l'union de deux ensembles disjoints

pour avoir une partie de G à p éléments il suffit de constituer une partie de E à k éléments et de la compléter par une partie de F à p - k éléments (pour k variant de 0 à p)

on a donc une algègre commutative naturelle pour construire les combinaisons (on le montre avec tes "dénombreurs : des polynomes tout simplement)

car si A est un anneau commutatif alors l'anneau A[x, y, ...] des polynomes en plusieurs indéterminées est une algèbre associative


et donc pour des arrangements il faudrait une algèbre non commutative de polynomes ....

on considère un anneau A non commutatif : pour tout a <> b : ab <> ba et on s'interdit aussi la commutativités des indéterminées sur cet anneau (une indéterminée commute tout de m^me avec les éléments de A je pense)

ainsi par exemple :

(a + bx + cy)(d + ex + fy) = ad + aex + afy + bdx + bex^2 + bfxy + cdy + ceyx + cfy^2 et on en peut rien simplifier ...
(d + ex + fy)(a + bx + cy) = ... et on ne peut rien simplifier et est différent du précédent produit ...


un exemple d'algèbre non commutative : l'anneau des matrices carrées sur un corps ...
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

JPMoulin
Membre Naturel
Messages: 18
Enregistré le: 07 Déc 2014, 11:27

Re: enumerateur d'arrangements

par JPMoulin » 19 Mar 2017, 11:55

Merci zygomatique

Je suis en train d'imprimer ta reponse et je vais la mediter et essayer de trouver une ou meme la solution, je fonctionne comme cela. J'ai eu une formation d'ingénieur il y a très longtemps et je n'ai jamais jusqu'à présent réfléchi aux fondements des mathématiques, aux problèmes d'algèbre générale.

Je m'etais dit qu'on prend ensemble de p elements et qu'a partir de cet ensemble on construit un p-uple (je fais cela "a la main") qui est un arrangement de p objets et une subsitution portant sur ce p-uple de cet ensemble genere un nouveau p-uple.
Je suis en train de considerer les p! substitutions possibles d'un p-uple qui sont des arrangements de p-objets pris p a p.
Une substitution peut etre representee par une matrice c'est donc probablement une demarche identique a celle que tu m'indiques, les produits de substitution étant non commutatifs comme toute composition de fonctions

Par contre je ne vois guere de polynome la dedans. C'est peut être dans l'action de transformer un ensemble comportant p élément en p-uple que se trouve les polynômes dont tu parles.

Je vais essayer de comprendre ce que tu dis vraiment et je vais te tenir au courant.

Merci en tout cas.

J-P Moulin

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: enumerateur d'arrangements

par Ben314 » 19 Mar 2017, 12:33

Salut,
Je t'avoue que, autant dans d'autres cas, la "passerelle" entre la combinatoire et les polynômes me semble pertinente, autant là, j'ai de doutes concernant l'intérêt du bidule.
zygomatique a écrit:(a + bx + cy)(d + ex + fy) = ad + aex + afy + bdx + bex^2 + bfxy + cdy + ceyx + cfy^2
Perso., au lieu d'écrire le bidule çi dessus avec des "plus" et des "multipliés", je pense qu'en l'écrivant sous la forme
{ (a) , (b,x) , (c,y) } x { (d) , (e,x) , (f,y) } = { (a,d) , (a,e,x) , (a,f,y) , (b,x,d) , (b,x,e,x) , (b,x,f,y) , (c,y,d) , (c,y,e,x) , (c,y,f,yd) }
Ca me semble au moins aussi clair et ça contient ni plus, ni moins d'information.
(modulo que j'ai bien compris le contexte vu que je comprend pas pourquoi zygomatique écrit le produit de bx par d sous la forme bdx et pas bxd (idem par exemple pour le produit de cy par fy qui devient du cfy² et pas du cyfy)

Et sinon, ben il te faut des "polynômes" vu que tu as décidé de remplacer les n-uplets par des produits et les réunions par des additions.
Et si tu cherche un "objet mathématique carré-carré" pour modéliser ce type de truc, je pense qu'il faut d'abord regarder la notion de "monoïde libre" (pour modéliser un truc zéro commutatif) puis celle "d'algèbre de monoïde" (pour rajouter là dessus une structure additive).
Mais je le redit : a mon avis, ça a pas grand intérêt dans le sens que tu démontrer rien de bien nouveau avec cette vision là (i.e. on pourra "recopier" les preuves pour qu'elle redescendent à un niveau plus élémentaire)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 14:31

Re: enumerateur d'arrangements

par zygomatique » 19 Mar 2017, 13:46

j'ai écrit bdx au lieu de bxd parce que j'ai supposé que les indéterminées commutaient avec les éléments de l'anneau ...

bien entendu on peut très bien ne pas le supposer ... et ta convention d'écriture est tout aussi raisonnable ...
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: enumerateur d'arrangements

par Ben314 » 19 Mar 2017, 14:23

De toute façon, j'avais tout lu en diagonale et j'avais mal compris le biniou, c'est à dire que j'avais pas vu que sur tes lettres il y avait à la fois des élément de l'anneau (ou du corps) des scalaires et d'autre du monoïde des variables.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Re: enumerateur d'arrangements

par Doraki » 19 Mar 2017, 14:29

Même si on avait construit une algèbre non commutative comme il faut, je vois pas trop comment on pourrait factoriser ou simplifier des trucs comme abc+acb+bac+bca+cab+cba.

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: enumerateur d'arrangements

par pascal16 » 19 Mar 2017, 15:30

l’algèbre non commutative, c'est par rapport à la loi + ou * ou les deux ?

non commutatif ab ne vaut pas forcément ba
mais ab + ac = a(b+c)
(a+b)² = (a+b)(a+b) par définition du carré
= a² + ab +ba +b²

abc+acb+bac+bca+cab+cba non simplifiable :
c'est justement ce que l'on cherche, ne pas simplifier pour simplement compter
abc+acb+bac+bca+cab+cba : il y a 6 arrangements possible dans un ensemble de 3 éléments.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 40 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite