Matemática

Inicio General Técnicas de recuento

Técnicas de recuento

Publicado por Laura

Por técnicas de recuento hacemos referencia a cualquier algoritmo que se utiliza para contar, es decir, para hallar el cardinal de un conjunto. Dentro de las técnicas de recuento, merece un especial tratamiento la Combinatoria: variaciones, permutaciones y combinaciones; aunque no nos ocuparemos de ello en este tema puesto que ya han sido tratadas con anterioridad.

En este post vamos a estudiar principalmente dos tipos de problemas y algunas de las técnicas más utilizadas para resolverlos: los problemas de existencia y los de enumeración. Además veremos algunos ejemplos en los que se pueden aplicar.

PROBLEMAS DE EXISTENCIA

En este tipo de problemas nos planteamos si existen o no las ordenaciones o configuraciones consideradas. Para resolver este tipo de problemas utilizamos el estudio de la paridad:

Estudio de la paridad: Un conjunto puede tener un número par o impar de elementos. Si probamos que tiene un número impar de objetos, podemos afirmar que existe al menos uno, quedando de esta forma probada la existencia. Un ejemplo de los problemas más famosos resueltos por este método es el de los puentes de Königsberg (por Euler 1763). En este problema se pretende pasar una vez por cada uno de los 7 puentes que unen sus islotes, volviendo al punto de partida. Como cada zona tiene un puente de entrada y otro de salida, se deduce que el número total de puentes debe ser par. No obstante, como hay siete puentes, el problema no tiene solución.

konisgber

PROBLEMAS DE ENUMERACIÓN

En los problemas de enumeración tenemos que determinar el número de configuraciones pedidas. Dentro de este tipo de problemas, existen dos tipos de técnicas, las que tienen por objetivo contar, junto con las que descomponen el problema en uno más sencillo. Algunas de estas técnicas son:

-Principio de adición: Si se puede realizar una tarea de m formas distintas, mientras que otra se puede realizar de n formas; de tal manera que no se pueden realizar de forma simultánea. Entonces, se puede realizar cualquiera de ellas de m+n formas distintas.

-Principio de multiplicación: Si un procedimiento se puede separar en dos etapas, habiendo en una m resultados y en otra n, entonces el procedimiento total se puede realizar de mxn formas distintas.

-Correspondencia uno a uno: Se trata de establecer una correspondencia biyectiva entre el conjunto que se pretende contar, A, y una sección S(n) de los números naturales. De tal forma que: card (A)= card (S(n))=n.

-Principio de distribución: Dentro de este tipo está el “Principio de los cajones” de Dirichlet, también conocido como el “principio del palomar”: Si m palomas ocupan n nidos, con n<m, entonces hay al menos un nido con dos o más palomas en su interior.

Categorías: General