2.4: Permutaciones

Última actualización
Guardar como PDF

Page ID: 111045

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Una permutación de$n$ distinct objects is just a listing of the objects in some order. For example, $[c,b,a]$ is a permutation of the set $\{a,b,c\}$ of three objects. Likewise, [triangle, melon, airplane] is a permutation of three objects as well. From our mathematical point of view, the objects we use don't actually matter; all we care about is the order they are arranged in. So usually we'll just talk about permutations of the numbers $1$ through $n$. You can think of each number as just counting the objects involved: first object, second object, $n$th object.

Las permutaciones surgen en el mundo de muchas, muchas maneras. Por ejemplo, supongamos que se le pide que enumere sus preferencias entre un grupo de candidatos presidenciales. La lista que compongas, de favorito a menos favorito, es una permutación de los candidatos. De hecho, puedes usar las matemáticas de las permutaciones para aprender cosas interesantes sobre diferentes tipos de sistemas de votación.

$Hor_ballot_paper.gif$

Figura 2.3: La votación instantánea de la segunda vuelta utiliza una permutación completa de los candidatos para encontrar un ganador. (Fuente)

Otro ejemplo es una baraja de naipes. En una baraja estándar, cada carta aparece exactamente una vez. Cuando barajas el mazo, solo estás creando una permutación aleatoria de las cartas. Se pueden utilizar las matemáticas relacionadas con las permutaciones para responder preguntas interesantes sobre las tarjetas. Como: '¿Cuántas veces necesito barajar la baraja antes de que sea realmente aleatoria?' La respuesta, por cierto, parece ser 7 para un barajado de riffle estándar. ¡Pero probar eso está mucho más allá del alcance de estas notas!

Debido a que las permutaciones son tan comunes, ¡los problemas que involucran permutaciones tienden a ser muy aplicables! Por ejemplo, supongamos que tienes doscientos alumnos en una clase y todos ellos entregan un examen. La pila de exámenes que te dan es una permutación de los alumnos; lo más probable es que la lista de puntajes de los estudiantes que guardes sea alfabética. Esto sugiere un problema: ¿Cuál es la forma más rápida de ordenar los exámenes? (De hecho, la clasificación es un problema fundamental en la informática.)

¿Cuántas permutaciones hay de un conjunto de

Template:ContribDenton