Disposició

De la Viquipèdia, l'enciclopèdia lliure.
Saltar a la navegació Saltar a la cerca
Nota de desambiguació.svg Desambiguació : si cerqueu la disposició en un sentit legal, vegeu Disposició (llei) .
Nota de desambiguació.svg Desambiguació : si busqueu la disposició en un sentit filosòfic, vegeu Vestit (filosofia) .

En combinatòria , es donen dos enters no negatius I , es defineix disposició de elements a a (o de elements de classe o de articles presos a la vegada) cada subconjunt ordenat de elements extrets d 'un conjunt de fitxers elements tals que els subconjunts difereixen en almenys un element o, en presència dels mateixos elements, en la forma en què estan ordenats. De vegades es diu nombre de seients i la disposició de elements a llocs es diu -arranjament.

Si no es permeten elements repetits en els subconjunts, parlem de disposicions simples, en cas contrari de disposicions amb repetició : en el primer cas ha de ser

Disposicions senzilles

El nombre d’arranjaments simples, indicats pel símbol des de elements a a ve donat per:

Per donar una explicació d'aquesta fórmula és possible recórrer a l' extracció dels elements d'una bossa o a les funcions d'injecció .

Extracció dels elements

Suposem que volem extreure 3 elements a partir d’un conjunt de 5 elements: en altres paraules, suposem que volem considerar les disposicions de 5 elements a 3 per 3.

En aquest sentit, suposem que poseu les 5 lletres A, B, C, D i E en una bossa i en voleu extreure 3 a l’atzar. La primera carta que anem a extreure serà indiferentment una de les 5 i, per tant, tindrem 5 possibilitats d’extracció. La segona lletra que extreurem serà una de les 4 que queden a la bossa i, per tant, tindrem 4 possibilitats d’extracció. Finalment, la tercera lletra que extraurem serà una de les 3 que queden a la bossa i, per tant, tindrem 3 possibilitats d’extracció. Si multipliquem totes les possibilitats entre elles, tindrem 5x4x3 = 60 grups possibles. Aquests grups són tots aquells que es poden considerar agafant 3 elements del conjunt de 5 elements i també inclouen grups que consisteixen en els mateixos elements però ordenats de manera diferent: evidentment són els 60 arranjaments possibles que es poden obtenir agrupant 5 elements en 3. a 3. Les 60 disposicions es detallen a continuació:

ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED
BAC BAD BAE BCA BCD BCD BDA BDC BDE BEA BEC BED
CAB CAD CAE CBA CBD CBE CDA CDB CDE CEA CEB CEB CED
DAB DAC DAE DBA DBC DBE DCA DCB DCE DEA DEB DEC
EAB EAC EAD EBA EBC EBD ECA ECB ECD EDA EDB EDC

Entre ells també trobem ABC, ACB, BAC, BCA, CAB i CBA: tot i que les provisions constituïdes pels mateixos elements s’han de considerar diferents perquè s’ordenen de manera diferent d’acord amb la mateixa definició de provisió.

Generalitzant, si les lletres en total són i les extraccions a fer són es nota que comencem per possibilitat d’extracció de la primera lletra dibuixada, es redueix a per a la segona lletra extreta i així fins arribar a per al -tima lletra extreta. Repetint el raonament exposat anteriorment tindrem

és a dir, el producte de factors, cadascun igual a va disminuir gradualment Multiplicar i dividir aquest producte per obtenim la fórmula indicada anteriorment:

Finalment, cal assenyalar que quan s’extreu una carta de la bossa, no es torna a posar dins : aquest fet garanteix que la mateixa lletra no es pot extreure diverses vegades i que, per tant, no hi pot haver elements repetits al subconjunt extret d’acord amb la definició de disseny senzill. L'exemple de la bossa també explica per què ha de resultar necessàriament : com a màxim es poden dur a terme extraccions després de les quals no queden altres lletres a la bossa per extreure.

Funcions injectives

A més d'utilitzar l'extracció de cartes d'una bossa, per obtenir el nombre de disposicions de elements a a és possible recórrer a l'ús de funcions injectives i, en particular, determinar el nombre total de totes les funcions injectives que tenen com a domini un conjunt de cardinalitat i per al codomain un conjunt de cardinalitat

Una funció injectiva és una llei que associa cada element del domini amb un element diferent de l’interval. Tenint en compte el cas d’un domini i un codomini format per dos conjunts d’elements, això significa que de cada element del domini només hi ha una línia d’associació (aquest fet sempre és cert per a la definició mateixa d’una funció, ja sigui injectiva, surjectiu o bijectiu) i que només arriba una línia d’associació a cada element del rang. En el cas de les funcions surjectives , entenent-se que només comença una línia de cada element del domini, passa més d'una línia d'associació a un o més elements de l'interval.


Diferència entre la funció injectiva / surjectiva


Per fixar les idees suposem tenir en compte les funcions injectives d’1 element en 4 elements: en total hi haurà 4 funcions d’aquest tipus, totes representades a la figura 1. Denotem per | F 1 | = 4 el nombre total d'aquestes funcions on el subíndex 1 ens recorda que el domini està format per un sol element.


Fig. 1: funcions d'un element en un conjunt de 4 elements


Les funcions injectives de 2 elements en 4 elements són un total de 12: la figura 2 mostra dos exemples diferents de les 12 funcions possibles. Cal assenyalar que en el pas de les funcions injectives d'1 en 4 a les de 2 en 4, hem passat de 4 funcions possibles a 12 funcions possibles: això s'explica pel fet que cadascuna de les funcions d'1 de cada 4 ( per exemple, 1 -A de la figura 1) és com si s'hagués afegit un altre element al domini (per exemple, l'element "2") des del qual és possible iniciar 3 associacions diferents (2-B, 2-C i 2- D, excloent el 2-A ja que ens limitem a les funcions injectives i que l’element A del rang ja està associat a l’element 1 del domini). Això fa que el total sigui 4x3 = 12. Denotem amb | F 2 | = | F 1 | x (4-1) = 4x3 = 12 el nombre total d'aquestes funcions on el subíndex 2 al primer membre i el subíndex 1 al segon membre ens recorden que el domini està format per dos elements i un element respectivament a la nostra exposició.


Fig. 2: exemples de funcions injectives de dos elements en un conjunt de 4 elements


Repetint el raonament, les funcions injectives de 3 en 4 elements són en total 24: a la figura 3 es mostren dos exemples diferents de les 24 funcions possibles. Cal tenir en compte que en el pas de les funcions injectives de 2 en 4 a les de 3 en 4, hem passat de 12 funcions possibles a 24 possibles funcions: això s’explica pel fet que cadascuna de les funcions de 2 en 4 ( per exemple, 1 -A, 2-B de la fig. 2) és com si s'hagués afegit un altre element al domini (per exemple, l'element "3") des del qual és possible iniciar 2 associacions diferents (3-C i 3 -D, excloent el 3-A i el 3-B per respectar la injectivitat). Això fa que el total sigui 12x2 = 24. Denotem amb | F 3 | = | F 2 | x (4-2) = 12x2 = 24 el nombre total d'aquestes funcions on el subíndex 3 al primer membre i el subíndex 2 al segon membre ens recorden que el domini està format respectivament per tres elements i dos elements en conseqüència a la nostra exposició.


Fig. 3: exemples de funcions injectives de tres elements en un conjunt de 4 elements


Generalitzant, ho són un conjunt finit de cardinalitat I un conjunt finit de cardinalitat amb També ser el conjunt de funcions injectives S’aplica la següent fórmula recursiva

estant en general d'acord amb l'exemple anterior de les funcions d'1 en 4 on estant en aquest cas Així, hem arribat a la conclusió esmentada anteriorment que el nombre de funcions injectives d’un conjunt de cardinalitat en un conjunt de cardinalitat s'identifica amb el de les disposicions simples de elements a a

El nombre de funcions injectives d’un conjunt de cardinalitat en una de cardinalitat també s’indica amb el símbol:

Exemples

1) Suposem que volem conèixer el nombre total de podis possibles d’una cursa en què participen 10 corredors. Atès que l’ordre d’arribada és important, caldrà tenir en compte les disposicions (senzilles ja que no hi pot haver repetició, ja que és impossible que el mateix corredor sigui el primer i el segon classificats al mateix temps) en lloc de les combinacions . En particular, caldrà tenir en compte les disposicions de 10 elements a 3 a 3. Per tant, tindrem:

Per tant, el podi pot estar format per 720 grups diferents de corredors.

2) Tenint en compte que el campionat de la Sèrie A consta de 20 equips, suposem que volem conèixer el nombre total de partits que es jugaran en una temporada. Com que dos equips genèrics A i B s’enfrontaran tant a la primera ronda (AB amb A jugant a casa) com a la segona ronda (BA amb A jugant fora de casa), això vol dir que l’ordre és important i, per tant, ens ocupem amb disposicions (senzilles ja que no pot haver-hi repetició, ja que és impossible que un equip s’enfronti a si mateix) en lloc de combinacions. En particular tindrem:

Així, en total, es jugaran 380 partits de la Sèrie A en una temporada.

Disposicions amb repetició

El nombre d’arranjaments amb repetició, que es denota amb el símbol des de elements a a ve donat per:

També aquí, per donar una explicació d’aquesta fórmula, es pot recórrer a l’ extracció dels elements d’una bossa o a les funcions injectives i surjectives .

Extracció dels elements

Suposem que volem extreure 3 elements a partir d’un conjunt de 4 elements, però a diferència d’abans ens assegurem que els elements es puguin repetir: és a dir, volem trobar els arranjaments amb la repetició de 4 elements per 3 per 3.

En aquest sentit, suposem que posem les 4 lletres A, B, C i D en una bossa i en volem extreure 3 a l’atzar. La primera lletra que anem a extreure serà indiferentment una de les 4 i, per tant, tindrem 4 possibilitats d’extracció. Ara, però, abans de procedir a l'extracció de la segona lletra, torneu a posar la lletra que acabem d'extreure a la bossa . Fins i tot la segona lletra que anem a extreure serà indiferentment una de les 4 i, per tant, tornarem a tenir 4 possibilitats d’extracció: entre altres coses, pot passar que la segona lletra extreta sigui la mateixa que la primera, que per tant hi hagi és repetitivitat , compartint-se amb totes les lletres de la bossa. Una vegada més tornem a posar la lletra que acabem d’extreure a la bossa. Finalment, també la tercera lletra que anem a extreure serà indiferentment una de les 4 i, per tant, tornarem a tenir 4 possibilitats d’extracció. Si multipliquem totes les possibilitats, tindrem 4x4x4 = 4 3 = 64 grups possibles, és a dir, els 64 arranjaments possibles amb repetició de 4 elements presos en 3 per 3.

Aquestes disposicions es detallen a continuació:

AAA AAB AAC AAD ABA ABB ABC ABD
ACA ACB ACC ACD ADA ADB ADC ADD
BAA BAB BAC BAD BBA BBB BBC BBD
BCA BCB BCC BCD BDA BDB BDC BDD
CAA CAB CAC CAD CBA CBB CBC CBD
CCA CCB CCC CCD CDA CDB CDC CDD
DAA DAB DAC DAD DBA DBB DBC DBD
DCA DCB DCC DCD DDA DDB DDC DDD

Com podeu veure, diferents grups tenen elements repetits: per exemple, les disposicions AAB i BAA es consideren diferents, ja que, tot i que tenen els mateixos elements (la lletra A es repeteix dues vegades i la lletra B), s’ordenen de manera diferent.

Generalitzant, si les lletres són i les extraccions a fer són s'observa que, cada vegada que es torna a posar la lletra extreta a la bossa, torna a començar amb totes les lletres disponibles independentment de si es tracta de la primera, segona, tercera extracció, etc. El nombre de disposicions amb repetició ve donat, com hem volgut demostrar, pel producte de per a ell mateix vegades a partir de la qual la fórmula:

A diferència de les disposicions simples, la restricció no s'aplica a les disposicions amb repetició : atès que cada vegada que es torna a posar la lletra extreta a la bossa, no hi ha risc que s’esgotin tal com passa en les disposicions simples en què, després de extraccions, no queden més lletres a la bossa per extreure.

Funcions injectives i surjectives

A més d’utilitzar l’extracció de lletres d’una bossa, s’obté el nombre de disposicions amb repetició de elements a a és possible recórrer a l'ús de funcions i, en particular, a la determinació del nombre total de totes les funcions, ja siguin injectives o surjectives, tenint com a domini un conjunt de cardinalitat i per al codomain un conjunt de cardinalitat

Per fixar les idees suposem que considerem les funcions d’1 element en 4 elements: ja que només hi ha una línia d’associació que comença a partir de l’únic element present al domini i que aquesta línia només pot acabar en un sol element dels 4 presents a per a aquesta condició de tenir a veure amb funcions surjectives que, com s'ha esmentat anteriorment, requereixen que almenys un element del rang estigui afectat per almenys dues línies d'associació. Per tant, també en el cas d’arranjaments amb repetició, s’aplicarà la figura 1, ja que les funcions d’1 de cada 4 són sempre del tipus injectiu. Per tant, els arranjaments simples de 4 elements a 1 a 1 i els que tenen repetició de 4 elements a 1 a 1 s’identifiquen entre ells, també perquè és impossible tenir repeticions si només hi ha un element.

Considerem ara les funcions de 2 elements en 4 elements: la figura 4 il·lustra les 16 funcions d’aquest tipus, ja siguin injectives o surjectives. En particular, es pot observar com la condició de la surjectivitat dóna vida a la repetitivitat dels elements del rang que al seu torn distingeix les disposicions amb la repetició: per exemple (1) de la figura 4 determina la disposició AA mentre que (8) determina la disposició BB.

En el pas de les funcions d’1 element en 4 elements a les de 2 elements en 4 elements és com si haguéssim afegit un altre element al domini: a diferència del cas de les disposicions simples, ara, en disposicions amb repetició, ho permetem segon element que s’ha d’associar a qualsevol dels 4 elements de l’interval, fins i tot amb l’element de l’interval ja associat al primer element del domini , considerant ara possibles associacions del tipus surjectiu. Per tant, les 4 associacions relacionades amb el primer element del domini s’han de multiplicar per les 4 associacions relatives al segon element del domini obtenint 4x4 = 16 que són el total de les funcions injectives i surjectives de 2 elements en 4 elements.


Fig. 4: funcions de 2 elements en 4 elements


Generalitzant, si és així denotem un conjunt finit de cardinalitat i amb un conjunt finit de cardinalitat el nombre total de funcions injectives o surjectives que siguin, seran iguals a d'acord amb la fórmula de les disposicions amb repetició que ens proposem demostrar:

Exemples

Els enters no negatius amb menys de tres dígits són els que s’obtenen a partir de les disposicions de repetició de 10 elements (els números del 0 al 9) presos del 2 al 2 (considerant els números d’un sol dígit que consisteixen en dos dígits dels quals el primer res) : per tant, en total hi ha 10 2 = 100.

El nombre de columnes possibles de les piscines de futbol formades per tretze prediccions escollides entre tres elements (1, X o 2) és igual a 3 13 = 1.594.323. En aquest cas resulta estar i

Permutació: cas particular d'una disposició simple

Es pot veure que hi ha una estreta correlació entre disposicions simples i permutacions. De fet, per si de cas és igual a sí que ho tens

que coincideix amb el nombre de permutacions de elements.

D'altra banda, això és obvi si utilitzem l'exemple de l'extracció de cartes d'una bossa: les permutacions es poden veure com l'extracció de les cartes amb la condició que es facin tantes extraccions com lletres fins a la bossa. es buida.

Bibliografia

  • Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elements of matemàtiques discretes , Bolonya, Zanichelli, 1988.
  • Sheldon M. Ross, Càlcul de probabilitats , Milà, Apogee, 2004.

Articles relacionats

Altres projectes

Matemàtiques Portal de matemàtiques : accediu a les entrades de Wikipedia relacionades amb les matemàtiques