Hice esta pregunta contando crudamente. Como$|S|$ era solo$4$, el conteo no tomó mucho tiempo, pero debería haber una manera de hacerlo para conjuntos más grandes.
Deje$S = \{a, b, c, d\}$ y$X = \{f : S \to S \mid f\text{ is bijective and }f(x)\ne x\text{ for each }x \in S\}$
Entonces $|X| =\text{ ?}$
Bijections a partir de un conjunto que no tienen puntos fijos se llaman alteraciones. La pregunta es ¿cuántos de alteraciones de un conjunto. Un recuento de estos es una aplicación estándar de la inclusión-exclusión principio.
Ver este artículo.
La línea inferior es quizás sorprendente: Es el entero más cercano a $\dfrac{n!}{e}$.
Por ejemplo, si $n=5$ entonces es el entero más cercano a $\dfrac{5!}e = \dfrac{120}e=44.14553\ldots\ {}$.
El argumento es el siguiente: El número de bijections es $n!$. Restar de que el número total de bijections con al menos un punto fijo y que esa es la respuesta. El número de bijections con al menos un punto fijo se encuentra de la siguiente manera.
El número de bijections en que $k$th es el elemento fijo es $(n-1)!$. Agregar los largo de todos los $n$ miembros y ha $(n-1)!n=n!$.
Pero que es un sobre cuenta porque cuando se contaba con el primer elemento fijo y, a continuación, añadió que los del segundo elemento fijo, todo el uno con el primer y segundo elementos fijos consiguió contado dos veces. Para restar el número de aquellos fijo, que es $(n-2)!$. Hacer lo mismo sobre tales desordenada de los pares, de los cuales hay $\dbinom n 2=\dfrac{n(n-1)}{2}$. Así que usted está restando un total de $\dfrac{n(n-1)}2\cdot(n-2)! = \dfrac{n!}2$.
Hasta ahora, nuestros recuento de aquellos con al menos un punto fijo es $n!-\dfrac{n!}2$.
Pero ahora te has restado demasiados ya que resta aquellos con el primer y segundo elementos fijos, y aquellos con el primer y tercer elementos fijos, y los del segundo y tercer elementos fijos. Aquellos con los tres elementos fijos se añadió en tres veces, luego se resta tres veces, por lo que necesita para obtener añadió de nuevo. Hay $(n-3)!$ de las personas. Hacer lo mismo con todos los conjuntos de tres, de los cuales hay $\dfrac{n(n-1)(n-2)}{6}$. Así, obtenemos $(n-3!)\dfrac{n(n-1)(n-2)}{6}=\dfrac{n!}6$.
Hasta ahora, nuestros recuento de aquellos con al menos un punto fijo es $n!-\dfrac{n!}2+\dfrac{n!}6$.
Pero ahora con cuatro puntos fijos han contado demasiadas veces, por lo que se tienen que restar de ellos, consiguiendo $n!-\dfrac{n!}2+\dfrac{n!}6-\dfrac{n!}{24}$.
Y así sucesivamente, hasta el $n$: $$ n!-\frac{n!}2+\frac{n!}6-\frac{n!}{24} + \frac{n!}{120} - \cdots \pm \dfrac{n!}{n!}. $$ Esto es lo que tenemos que restar de la $n!$, el número total de bijections, llegar $$ n! - n!+\frac{n!}2-\frac{n!}6+\frac{n!}{24} - \frac{n!}{120} + \cdots \pm \dfrac{n!}{n!}. $$ Este es $$ n!\a la izquierda( \frac1{0!} - \frac1{1!} + \frac1{2!} - \frac1{3!} + \frac1{4!} - \cdots \pm \frac1{n!} \right). $$ En otras palabras, es $n!$ veces el valor en $x=-1$ de la energía estándar de la serie $$ e^x = \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} +\cdots $$ excepto que la serie termina después de la $n$th-grado plazo.
Voy a derivar de la inclusión-exclusión en el argumento como una alternativa. Hay $n!$ permutaciones. Restamos el número de permutaciones en las que $f(x) = x$ para un punto de $x$. Fijamos un punto y permutar el resto de $n-1$ $(n-1)!$ maneras. Como hay $n$ tales maneras de solucionar un punto, se restar $n!$.
Sin embargo, tenemos más de contado y tengo que agregar de nuevo en los puntos en que dos puntos son fijos. Recogemos nuestros dos puntos en $\binom{n}{2}$ maneras. Hay, a continuación, $(n-2)!$ formas de organizar el resto de $n-2$ puntos. Así, por la regla del producto, que se multiplican para obtener $\binom{n}{2} \cdot (n-2)! = \frac{n}{2!} = P(n, 2)$ donde $P$ es la permutación función count.
Continuamos este argumento para obtener la fórmula:
$$D_{n} = n! \cdot \sum_{i=0}^{\infty} \frac{(-1)^{i}}{i!}$$
también hay una derivación utilizando exponencial funciones de generación. una permutación arbitraria de un conjunto se compone de un trivial mapa sobre el subconjunto de sus puntos fijos, y una alteración en el complemento del conjunto fijo.
el trivial mapa tiene un solo representante por cada uno de cardinalidad, por lo que su correo.g.f. es $e^z$
el número de permutaciones de un conjunto tiene el correo.g.f. $\sum \frac{n!}{n!}z^n=(1-z)^{-1}$
si $D(z)$ es el correo.g.f. para el número de alteraciones a continuación: $$ (1-z)^{-1}=D(z)e^z $$ es decir, $$ D(z)=\frac{e^{-z}}{1-z} $$ a medida que la serie nos tiene $$ D(z)=\sum_{j=0}^{\infty}\frac{d_n}{n!} =\sum_{j=0}^{\infty}\frac{(-1)^j}{j!}z^j\sum_{k=0}^{\infty}z^k \\ =\sum_{n=0}^{\infty}\sum_{j+k=n}\frac{(-1)^j}{j!}z^n $$ lo que da el número de alteraciones de $n$ objetos como: $$ d_n = n!\sum_{j=0}^n \frac{(-1)^j}{j!} $$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
