En las matemáticas y teórico de informática, una enumeración de un sistema es un procedimiento para enumerar a todos los miembros del sistema en una cierta secuencia definida, o una cuenta de objetos de una clase especificada. Las dos clases de enumeración a menudo, pero no siempre, traslapo.

Enumeración como listado

Formalmente, una enumeración de un S del sistema (en el sentido de un listado) se puede definir de cualquiera de dos maneras:

como trazado surjective del $\backslash \; del\; mathbb\; \{N\}$ (los números naturales a S (es decir, cada elemento del S es la imagen por lo menos de un número natural). Esta definición es especialmente conveniente a las cuestiones Computability y de la teoría determinada .

como trazado bijective del S a un segmento inicial de los números naturales. Esta definición es especialmente conveniente a las preguntas combinatorias y a los sistemas finitos; entonces el segmento inicial está {1.2,…, n } para un cierto n que sea la cardinalidad S .

En la primera definición varía si el trazado también está requerido ser el inyectivo (es decir, cada elemento del S es la imagen del exactamente un número natural de ), y/o permitido ser el parcial (es decir, el trazado se define solamente para algunos números naturales). En algunos usos (especialmente ésos referidos al computability del S del sistema), estas diferencias son de poca importancia, porque una se refiere solamente a la existencia mera de una cierta enumeración, y una enumeración según una definición liberal implicará generalmente que existen las enumeraciones que satisfacen requisitos más terminantes también.

La enumeración de los sistemas finitos requiere obviamente que el non-injectivity o la parcialidad esté aceptado, y en los contextos en donde los sistemas finitos pueden aparecer uno o ambos éstos estar inevitable presente.

En de informática uno considera a menudo enumeraciones con el requisito agregado que el trazado del $\backslash \; del\; mathbb\; \{N\}$ al sistema enumerado debe ser el computable. El sistema que es enumerado entonces se llama el recurrentemente enumerable, refiriendo al uso de la teoría de la repetición en formalizaciones de lo que significa para que el mapa sea computable. El ser recurrentemente enumerable es una condición más débil que siendo un sistema decidible .

Ejemplos

los números naturales es enumerable por la función f ($f\; de\; x)\; =\; del\; X.\; en\; este\; caso:\; \backslash \; el\; mathbb\; \{\}\; \backslash \; \backslash \; mathbb\; \{N\}$ de N está simplemente la función de identidad .
el $\backslash \; el\; mathbb\; \{Z\}$, el sistema de los números enteros es enumerable cerca $f\; del$

l (x): = \ comenzar {los casos} - (x+1)/2, y \ mbox {si} x \ \ \ x/2 del mbox {es impar}, y \ mbox {si} x \ mbox {es uniforme}. \ extremo {casos}

$f:\; \backslash \; el\; mathbb\; \{\}\; \backslash \; \backslash \; mathbb\; \{Z\}$ de N es un bijection puesto que cada número natural corresponde a exactamente un número entero. La tabla siguiente da los primeros valores de esta enumeración:

Características

allí existe una enumeración para un sistema si y solamente si el sistema es el contable.

si un sistema es enumerable él tendrá un infinito no numerable de diversas enumeraciones, a menos que en las cajas degeneradas del sistema vacío o (dependiendo de la definición exacta) de los sistemas con un elemento. ¡Sin embargo, si uno requiere enumeraciones ser inyectivas el y no prohibe solamente a forma limitada de parcialidad tales que si $f\; (n)$ es entonces definido $f\; (m)$ se debe definir para todo el , después un sistema finito de elementos del N tiene exactamente N ! enumeraciones.

que una enumeración de un sistema da una orden del total de eso fijó. Aunque la orden pueda tener poco hacer con el sistema que es la base es útil cuando una cierta orden del sistema es necesaria.

Enumeración como contando

Hay subáreas flourishing en muchas ramas de las matemáticas referidas a enumerar (en el sentido que cuenta ) los objetos de clases especiales. Por ejemplo, en la enumeración de la permutación y la enumeración del gráfico el objetivo es contar las permutaciones o los gráficos que cumplen ciertas condiciones estructurales.