Combinatoria Teoría    Propuestas    Diccionario    Herramientas

Estás en InicioSin decimales > Combinatoria > Diccionario

Pequeño diccionario de Combinatoria

A B C D E F G H I L M N O P R S T U V W

Selecciona una letra o un tema:

A

Aplicación
Aritmético
Arreglo

B

Binomial

C

Ciclo
Circular
Clase
Combinación
Combinatoria
Combinatorio
Contar ordenadamente
Correspondencia

CH

D

Desarreglo
Descomposición en sumas

E

F

Factorial
Ferrers

G

Generatriz
Grado
Grupo de sustituciones

H

I

Impar
Inversión en una permutación

L

M

Multinomial

N

N-pla
Número

O

Orden

P

Par
Partición
Pascal
Permutación
Principios combinatorios

R

Reducida

S

Selección ordenada
Signatura
Stirling
Subfactorial
Sustitución

T

Transposición

U

V

Variación

W

 


A

Aplicación

Una aplicación es una correspondencia en la que cada elemento del primer conjunto le corresponde un elemento del segundo conjunto y solo uno

Aritmético

Triángulo aritmético

Nombre dado también al triángulo de Pascal o Tartaglia.

Arreglo

Llamaremos arreglo en un conjunto finito a cualquier sucesión también finita formada por elementos de ese conjunto. Al ser el arreglo una sucesión, intervendrá en él el orden, y se podrán repetir elementos.

 

 

B

Binomial

Número binomial

Sinónimo de número combinatorio.

 


 

C

 

Ciclo

Es una parte de una permutación que aplica un subconjunto en sí mismo. Por ejemplo

(3 4 5 6)
(5 3  6 4)  s(3)=5  s(5)=6  s(6)=4  s(4)=3    (regresa al primero, el 3)

Circular

Una permutación es circular o cíclica si es ella misma un ciclo, o que se puede descomponer en un solo ciclo.

 

 

Clase

Clase de una permutación

Es su carácter par o impar.

Combinación

Una de las distintas formas de elegir subconjuntos de n elementos dentro de otro conjunto de m elementos. Es claro que cada elección se distingue de otras por los elementos elegidos, no por el orden en el que son elegidos.

Combinatoria

Parte de las Matemáticas que estudia las formas de ordenar o elegir elementos en los conjuntos. Se considera fundada por Santiago Bernoulli en su tratado Ars Conjectandi en 1713.

Combinatorio

Número combinatorio

Es el número de combinaciones posibles de n elementos en un conjunto de m elementos.

Contar

Contar ordenadamente

En Combinatoria es esencial el saber contar ordenadamente los elementos de un conjunto o un arreglo. Para ello se suele usar

Correspondencia

Una correspondencia entre dos conjuntos es cualquier subconjunto de su producto cartesiano. En la práctica consiste en asignar una pareja o varias a todos o algunos elementos del conjunto.

 


 

CH

 

 


 

D

 

Desarreglo

Llamaremos desarreglo a una permutación de un conjunto en sí mismo en el que no coincide ningún origen con su imagen (no hay puntos fijos). El número de desarreglos posibles en un conjunto de n elementos viene dado por la expresión

 

 

Descomposición

Descomposición de un número en sumas

Ver Partición

 

 


 

E

 

 


 

F

Factorial

Factorial de un número

 

Ferrers

Diagrama de Ferrers

Es un diagrama en el que se adosan símbolos formando tantas filas como sumandos entran en la partición, y columnas, siendo la longitud de cada una el valor del sumando. Así, la partición 8=4+2+1+1 se puede representar así:

* * * *
* *
*
*

 

 

 

 


 

G

Generatriz

Función generatriz

La función generatriz de arreglos, sucesiones o particiones es una función polinómica cuyos coeficientes coinciden con valores numéricos obtenidos en ellas, especialmente el número total de casos posibles.

 

Grado

Grado u orden de un ciclo en una permutación o sustitución

Es el número de veces que hay que aplicarlo sobre un conjunto para que el resultado sea la identidad. Se puede expresar como potencia: Sg = I , donde S es el ciclo, g su grado e I la identidad.

Grado de una sustitución

Vale la misma definición anterior: Sg = I , donde S es el ciclo, g su grado e I la identidad.
Si S está descompuesta en ciclos, su grado será el m.c.m. de los grados de esos ciclos.

 

Grupo

Grupo de permutaciones (o sustituciones)

Todas las sustituciones que operan sobre un conjunto forman un grupo para la operación S*T, que consiste en aplicar sobre ese conjunto, de forma sucesiva, las dos sustituciones S y T. Su elemento neutro es la Identidad I. Se le llama grupo simétrico y se representa por Sn, siendo n el cardinal del conjunto.

 


H

 

 

 

 


 

 

I

Impar

Permutación impar

Una permutación es impar cuando posee un número impar de inversiones (o transposiciones). El número total de permutaciones impares de orden n es n!/2

Inversión

Inversión de una permutación

Diremos que dos elementos a y b de una permutación presentan una inversión si están ordenados de forma inversa al orden principal prefijado. Por ejemplo, los números 5 y 2 presentan una inversión en 15342 respecto al orden natural de los números.

Si el número de inversiones de una permutación es par, dicha permutación también se llama par, e igualmente si es impar.

Así la permutación del ejemplo 15342 presenta las inversiones 53, 54, 52, 32 y 42, luego es impar.

 


L

 

 

 

 

 


 

M

 

Multinomial

Coeficiente  n1, n2,... nk, multinomial de índice superior n e inferiores a, b,... h, con k>2 es una forma de expresar el número de permutaciones de n elementos con elementos repetidos en grupos de a, b,... h elementos. Su valor equivale a

 


N

 

N-pla

Sinónimo de Arreglo o de Selección ordenada

Número

Número combinatorio: Ver Combinatorio

Número de Bell: Se llama número de Bell de un conjunto finito de n elementos, y se representa por Bn al número de particiones distintas que se pueden definir en ese conjunto.

Número de Stirling:

Existen dos sucesiones distintas de números de Stirling, que son

Números de Stirling de primera clase.

Dado el grupo de permutaciones Sn sobre un conjunto de n elementos, llamaremos Número de Stirling de primera clase, S1(n,k), al número de permutaciones de  Sn que se pueden descomponer exactamente en k ciclos.

Números de Stirling de segunda clase.

Dado un conjunto de n elementos, llamaremos número de Stirling de segunda clase S2(n,k) al número de particiones distintas de k conjuntos que se pueden definir en ese conjunto de n elementos.

 


 

O

Orden

El orden en Combinatoria: El orden es un elemento de definición en las combinaciones y permutaciones.

Orden de un ciclo o de una permutación: Sinónimo de grado


 

P

Par

Permutación par

Una permutación es par cuando posee un número par de inversiones. El número total de permutaciones pares de orden n es n!/2

Paridad

Paridad de una permutación o una sustitución

Es el carácter par o impar de esa permutación.

Partición

Partición de un número natural

Es cada una de las representaciones de ese número como suma de otros naturales no nulos, sin tener en cuenta el orden. Se representa con el símbolo p(n) y se calcula mediante la identidad de Euler

(1-x)-1.(1-x2)-1.(1-x3)-1… = 1+p(1)x+p(2)x2+p(3)x3+…

Pascal

Triángulo de Pascal

Disposición en triángulo de los números combinatorios o binomiales.

 
 
 
 
 
1
 
 
 
 
 
 
 
 
 
1
 
1
 
 
 
 
 
 
 
1
 
2
 
1
 
 
 
 
 
1
 
3
 
3
 
1
 
 
 
1
 
4
 
6
 
4
 
1
 
1
 
5
 
10
 
10
 
5
 
1

 

Permutación

Se llama permutación sin repetición a cualquiera de las distintas formas posibles de ordenar un conjunto. El número de permutaciones de un conjunto de n elementos es el factorial de n, n!.

También se define como una aplicación biyectiva del conjunto en sí mismo.

En los distintos órdenes posibles quizás se desee admitir la repetición de algunos elementos un número determinado de veces. Por ejemplo, en la palabra CATAPULTA, si quisiéramos ordenar sus letras, deberíamos admitir que la A se repitiera tres veces y la T dos. Llamaremos permutaciones con repetición a estas ordenaciones.

También se pueden definir estas permutaciones como las formas de distribuir n objetos en k cajas, de forma que cada caja contenga siempre un mismo número determinado de objetos.

Igualmente, coincide con el número de aplicaciones (o funciones) existente entre un conjunto de n elementos y otro de k elementos, en el que el número de antiimágenes de cada elemento está prefijado.

Para calcular el número de permutaciones de este tipo bastará dividir el factorial del número total de símbolos, contando sus repeticiones, entre el número de veces que se repite cada uno.

Este número recibe el nombre de coeficiente multinomial.

 

Principios combinatorios

Principio de la Adición

Dados los conjuntos A1, A2,...Ak, disjuntos dos a dos, se cumple que

Card(A1È A2È...ÈAk) =Card(A1) + Card(A2) + ... +  Card(Ak)

Es decir, que para contar los elementos de la unión de varios conjuntos disjuntos, deberemos sumar.

Principio de la Multiplicación

Si los conjuntos A1, A2,...Ak, son no vacíos, se cumple que

Card(A1´ A2´...´Ak) =Card(A1) ´ Card(A2) ´ ... ´  Card(Ak)

Podemos traducir este principio a la idea de que al combinar mediante pares, ternas, etc. varios conjuntos, el número total de elementos resultantes equivale al producto de los cardinales de los conjuntos que se combinaron.

Principio de Distribución

Este principio se conoce también como Principio de las cajas, del palomar  o de Dirichlet

Lo desarrollaremos en dos versiones equivalentes:

(a)  Si repartimos m objetos en n cajas, y m>n, entonces, al menos una caja deberá contener 2 objetos o más.

(b) Si se reparten np+m objetos en n cajas, entonces alguna caja deberá contener al menos p+1 objetos.

Principio de Inclusión y exclusión

Se llama así a la fórmula obtenida anteriormente

Card(AÈB) =Card(A) + Card(B) - Card(AÇB)

y a su generalización para más de dos conjuntos. Por ejemplo, para tres sería

Card(AÈBÈC) =Card(A) + Card(B) + Card(C) - Card(AÇB) - Card(AÇC) - Card(BÇC) +  Card(AÇBÇC)

En el caso de varios conjuntos aparecerían signos - en las intersecciones de un número par de conjuntos y signo + en las de número impar:

Card(ÈSi) = ∑Card(Si) - ∑Card(SiÇSj) + ∑Card(SiÇSjÇSk) + ... + (-1)n ∑Card(SiÇ...ÇSn)

 

 


 

R

Reducida

Permutación reducida

Una permutación es reducida si no deja fijo ningún elemento. En su descomposición en ciclos ninguno de ellos tiene orden 1.


 

S

Selección ordenada

Sinónimo de Arreglo y de n-pla

 

Signatura

Signatura de una permutación

Llamaremos signatura de una permutación al número +1 si es de tipo par o al número –1 si es de tipo impar.

 

Stirling

Números de Stirling de primera clase (o primera especie)

Número de Stirling de primera clase S1(n,k)  indica, dado el grupo de permutaciones Sn sobre un conjunto de n elementos, cuántas permutaciones se pueden descomponer exactamente en k ciclos.

Números de Stirling de segunda clase (o segunda especie)

Número de Stirling de segunda clase S2(n,k) representa cuántas particiones distintas de k conjuntos se pueden definir en
un conjunto de n elementos.

 

Subfactorial

Subfactorial de un número natural

Llamaremos subfactorial de n al número de desarreglos de un conjunto de n elementos.

 

 

Sustitución

Una sustitución aplicada a un conjunto es cualquier correspondencia biyectiva definida entre los elementos de dicho conjunto. Su número total es el factorial del cardinal de ese conjunto. Es sinónimo de permutación.

 


 

T

Transposición

Se llama transposición en el grupo de permutaciones de un conjunto, a todo ciclo de orden 2. Todas las permutaciones se pueden descomponer en transposiciones, pero no de forma única, aunque se conserva la paridad.

 


U

 


 

V

 

Variación

Una de las distintas formas de elegir subconjuntos de otro conjunto, de forma que cada elección se distinga de otras por los elementos o bien por el orden en el que son elegidos.

 

 

 


 

W