[Masacroso]

En estas fechas siempre hacemos lo del amigo invisible entre los familiares más cercanos. A raíz de eso me surgió la duda de cómo hallar el número de desarreglos para \(n\) personas. La cuestión es que no me venía a la cabeza la relación recursiva que los define así que intenté otro método, que paso a compartir porque puede resultar interesante.

Lo primero que hice fue darme cuenta de que \(n!=\sum_{k=0}^n \binom{n}k d_k\), siendo \(d_k\) el número de desarreglos de \(k\) elementos. Luego recordé la siguiente relación que había leído hace años en un libro y que jamás había llegado a utilizar: si \(\{a_n\}_n\) es una sucesión definida a partir de otra sucesión \(\{b_n\}_n\) por \(a_n:=\sum_{k=0}^n \binom{n}k b_k\) entonces \(b_n=\sum_{k=0}^n \binom{n}k a_k (-1)^{n-k}\) para todo \(n\), de donde deducimos rápidamente que

\[d_n=\sum_{k=0}^n \binom{n}k k! (-1)^{n-k}=n!\sum_{k=0}^n \frac{(-1)^k}{k!}=\left\lfloor \frac{n!}{e}+\frac12\right\rfloor\]

P.D.: la relación \(a_n=\sum_{k=0}^n \binom{n}k b_k\iff b_n=\sum_{k=0}^n \binom{n}k a_k (-1)^{n-k}\) se sigue de la multiplicación (formal) de las series de potencias \( \sum_{k=0}^\infty b_k \frac{x^k}{k!} \) y la serie de potencias que representa a \(e^x\).

[hahn-banach]

En estas fechas siempre hacemos lo del amigo invisible entre los familiares más cercanos. A raíz de eso me surgió la duda de cómo hallar el número de desarreglos para \(n\) personas. La cuestión es que no me venía a la cabeza la relación recursiva que los define así que intenté otro método, que paso a compartir porque puede resultar interesante.

Lo primero que hice fue darme cuenta de que \(n!=\sum_{k=0}^n \binom{n}k d_k\), siendo \(d_k\) el número de desarreglos de \(k\) elementos. Luego recordé la siguiente relación que había leído hace años en un libro y que jamás había llegado a utilizar: si \(\{a_n\}_n\) es una sucesión definida a partir de otra sucesión \(\{b_n\}_n\) por \(a_n:=\sum_{k=0}^n \binom{n}k b_k\) entonces \(b_n=\sum_{k=0}^n \binom{n}k a_k (-1)^{n-k}\) para todo \(n\), de donde deducimos rápidamente que

\[d_n=\sum_{k=0}^n \binom{n}k k! (-1)^{n-k}=n!\sum_{k=0}^n \frac{(-1)^k}{k!}=\left\lfloor \frac{n!}{e}+\frac12\right\rfloor\]

P.D.: la relación \(a_n=\sum_{k=0}^n \binom{n}k b_k\iff b_n=\sum_{k=0}^n \binom{n}k a_k (-1)^{n-k}\) se sigue de la multiplicación (formal) de las series de potencias \( \sum_{k=0}^\infty b_k \frac{x^k}{k!} \) y la serie de potencias que representa a \(e^x\).

Buenas tardes. He entendido bien todo lo que has hecho, pero hay algo que no consigo ver. Se trata de la relación \(a_n=\sum_{k=0}^n \binom{n}k b_k\iff b_n=\sum_{k=0}^n \binom{n}k a_k (-1)^{n-k}\). No entiendo muy bien a que te refieres con multiplicar formalmente las series de potencias. ¿Te refieres a multiplicar los dos sumatorios (finitos) y luego tomar límite? No consigo verlo, si tienes alguna sugerencia, te lo agradezco.

[Luis Fuentes]

Hola

 Si llamas \( a_n:=\displaystyle\sum_{k=0}^n \binom{n}k b_k \) y  consideras las series \( f(x)=\displaystyle\sum_{k=0}^\infty{}\dfrac{b_k}{k!}x^k  \) y \( e^x=\displaystyle\sum_{k=0}^\infty \dfrac{x^k}{k!} \) y las multiplicas tienes que:

\( f(x)e^x=\displaystyle\sum_{n=0}^\infty\left(\displaystyle\sum_{k=0}^n{}\dfrac{x^n}{k!(n-k)!}\right)=\displaystyle\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n \)

 Por tanto:

\( f(x)=e^{-x}\left(\displaystyle\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n\right)=\left(\displaystyle\sum_{k=0}^\infty \dfrac{(-1)^kx^k}{k!}\right)\left(\displaystyle\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n\right)=\displaystyle\sum_{k=0}^\infty\left(\displaystyle\sum_{s=0}^k{}\dfrac{a_s(-1)^s}{s!(k-s)!}\right)x^k \)

 Comparando con \( f(x)=\displaystyle\sum_{k=0}^\infty{}\dfrac{b_k}{k!}x^k  \) llegas a:

\( \dfrac{b_k}{k!}=\displaystyle\sum_{s=0}^k{}\dfrac{a_s(-1)^{k-s}}{s!(k-s)!} \)

\( b_k=\displaystyle\sum_{s=0}^k{}\binom{k}{s}a_s(-1)^{k-s} \)

Saludos.

P.D. Estoy usando que el producto de dos series formales:

\( \displaystyle\sum_{n=0}^\infty{}p_nx^n \) y \( \displaystyle\sum_{n=0}^\infty{}q_nx^n \)

es:

\( \displaystyle\sum_{n=0}^\infty{}\left(\sum_{k=0}^np_kq_{n-k}\right)x^n \)

[Tachikomaia]

En cuanto a la duda inicial, si son 2 personas, sólo hay 1 resultado posible.

Si son 3, creo que 2:
A -> B -> C -> A
A -> C -> B -> A

Si son 4:
A, B, C, D
A, B, D, C
A, C, B, D
A, C, D, B
A, D, B, C
A, D, C, B
B, A, C, D REPETIDO
B, A, D, C REPETIDO
B, C, A, D REPETIDO
Oh, well ¿todos repetidos a partir de ahora? Parece.

Si son 5:
A, B, C, D, E
A, B, C, E, D
A, B, D, C, E
A, B, D, E, C
A, B, E, C, D
A, B, E, D, C
Donde está B podemos poner C, D y E, y creo que no hay repetición, así que son 6*4.

Tenemos 1 -> 1
2 -> 2
3 -> 6
4 -> 24
La relación que veo, que podría ser la que buscamos o no, es el resultado anterior * el N actual. Los números que se conectan así / se multiplican, o sea el de la derecha*el izquierdo de abajo. Pero queremos saberlo desde un N, no calculando todos los anteriores. Pero bueno...

Código: [Seleccionar]

N = 2
Resultado = 2
Repetir:
  N++
  Resultado = Resultado*N
mientras N<9También creo que puede verse como: 1*2*3*4*5*6*7*8*9
Pero no le veo mucho sentido ¿es la misma fórmula de permutaciones típicas? Pensé que había algún 2 por ahí, ya que hay parejas.

[hahn-banach]

Hola

 Si llamas \( a_n:=\displaystyle\sum_{k=0}^n \binom{n}k b_k \) y  consideras las series \( f(x)=\displaystyle\sum_{k=0}^\infty{}\dfrac{b_k}{k!}x^k  \) y \( e^x=\displaystyle\sum_{k=0}^\infty \dfrac{x^k}{k!} \) y las multiplicas tienes que:

\( f(x)e^x=\displaystyle\sum_{n=0}^\infty\left(\displaystyle\sum_{k=0}^n{}\dfrac{x^n}{k!(n-k)!}\right)=\displaystyle\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n \)

 Por tanto:

\( f(x)=e^{-x}\left(\displaystyle\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n\right)=\left(\displaystyle\sum_{k=0}^\infty \dfrac{(-1)^kx^k}{k!}\right)\left(\displaystyle\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n\right)=\displaystyle\sum_{k=0}^\infty\left(\displaystyle\sum_{s=0}^k{}\dfrac{a_s(-1)^s}{s!(k-s)!}\right)x^k \)

 Comparando con \( f(x)=\displaystyle\sum_{k=0}^\infty{}\dfrac{b_k}{k!}x^k  \) llegas a:

\( \dfrac{b_k}{k!}=\displaystyle\sum_{s=0}^k{}\dfrac{a_s(-1)^{k-s}}{s!(k-s)!} \)

\( b_k=\displaystyle\sum_{s=0}^k{}\binom{k}{s}a_s(-1)^{k-s} \)

Saludos.

P.D. Estoy usando que el producto de dos series formales:

\( \displaystyle\sum_{n=0}^\infty{}p_nx^n \) y \( \displaystyle\sum_{n=0}^\infty{}q_nx^n \)

es:

\( \displaystyle\sum_{n=0}^\infty{}\left(\sum_{k=0}^np_kq_{n-k}\right)x^n \)

De acuerdo, no sabía de la existencia de los productos de series formales. Muchas gracias!!

[Luis Fuentes]

Hola

En cuanto a la duda inicial, si son 2 personas, sólo hay 1 resultado posible.

Si son 3, creo que 2:
A -> B -> C -> A
A -> C -> B -> A

Esto está bien.

Si son 4:
A, B, C, D
A, B, D, C
A, C, B, D
A, C, D, B
A, D, B, C
A, D, C, B
B, A, C, D REPETIDO
B, A, D, C REPETIDO
B, C, A, D REPETIDO
Oh, well ¿todos repetidos a partir de ahora? Parece.

Aquí no estoy seguro de que notación estás usando. Parece que con A,B,C,D te refieres a que A le regala a B; B a C; C a D; y D a A. Supongo. Pero con esa notación excluyes la posibilidad de que A le regale a B y B a A; y C le regale a D y D a C.

Es mejor denotarlas con cuatro letras ordenadas pero entendiendo que se indica por orden a quien regala A,B,C,D. Es decir si escribo cuatro letras X,Y,Z,T significa que A le regala a X; B a Y; C a Z; y D a T.

Por ejemplo si escribo B,A,D,C. Significa que A regala B; B le regala a A; C le regala a D; y D le regala a C.

Entonces se trata de buscar las formas de ordenar las cuatro letras A,B,C,D, de manera que ninguna esté en su posición original (porque nadie puede regalarse así mismo). Serían nueve posibilidades:

B,A,D,C
B,C,D,A
B,D,A,C
C,A,D,B
C,D,A,B
C,D,B,A
D,A,B,C
D,C,A,B
D,C,B,A

Mira por aquí:

https://es.wikipedia.org/wiki/Subfactorial

Saludos.

[Tachikomaia]

Parece que con A,B,C,D te refieres a que A le regala a B; B a C; C a D; y D a A. Supongo.

Claro, era más rápido poner una , que -> .

Pero con esa notación excluyes la posibilidad de que A le regale a B y B a A; y C le regale a D y D a C.

Cierto ^^u

En lo demás: 

Me surgió una duda, quizá algo tonta. Supongo que al hacer el sorteo, se ponen los 9 nombres, si son 9 personas. Supongamos que:
A saca el nombre de B
B el de C
C el de D
D el de E
E el de F
F el de G
H el de I
I el de A
y entonces... J el de J ¿se hace el sorteo de nuevo o es que inicialmente se hace de modo que se evita eso?

[Luis Fuentes]

Hola

Me surgió una duda, quizá algo tonta. Supongo que al hacer el sorteo, se ponen los 9 nombres, si son 9 personas. Supongamos que:
A saca el nombre de B
B el de C
C el de D
D el de E
E el de F
F el de G
H el de I
I el de A
y entonces... J el de J ¿se hace el sorteo de nuevo o es que inicialmente se hace de modo que se evita eso?

Pues eso ya depende de como se organice. Pero lo más cómodo es ir sacando uno a uno; si a uno le sale su propia papeleta sacar otra (dejando la suya fuera de la urna) y después volver a meterla. Cuando sólo queden dos por sacar papeleta (pongamos X,Y) y por tanto dos papeletas, si la papeleta de alguno de ellos (pongamos X) no ha salido la asignación es automática: Y le regala a X y X al que faltaba por regalar. SI sus propias papeletas ya han salido simplemente se completa el sorteo.

Saludos.

[hahn-banach]

En estas fechas siempre hacemos lo del amigo invisible entre los familiares más cercanos. A raíz de eso me surgió la duda de cómo hallar el número de desarreglos para \(n\) personas. La cuestión es que no me venía a la cabeza la relación recursiva que los define así que intenté otro método, que paso a compartir porque puede resultar interesante.

Lo primero que hice fue darme cuenta de que \(n!=\sum_{k=0}^n \binom{n}k d_k\), siendo \(d_k\) el número de desarreglos de \(k\) elementos. Luego recordé la siguiente relación que había leído hace años en un libro y que jamás había llegado a utilizar: si \(\{a_n\}_n\) es una sucesión definida a partir de otra sucesión \(\{b_n\}_n\) por \(a_n:=\sum_{k=0}^n \binom{n}k b_k\) entonces \(b_n=\sum_{k=0}^n \binom{n}k a_k (-1)^{n-k}\) para todo \(n\), de donde deducimos rápidamente que

\[d_n=\sum_{k=0}^n \binom{n}k k! (-1)^{n-k}=n!\sum_{k=0}^n \frac{(-1)^k}{k!}=\left\lfloor \frac{n!}{e}+\frac12\right\rfloor\]

P.D.: la relación \(a_n=\sum_{k=0}^n \binom{n}k b_k\iff b_n=\sum_{k=0}^n \binom{n}k a_k (-1)^{n-k}\) se sigue de la multiplicación (formal) de las series de potencias \( \sum_{k=0}^\infty b_k \frac{x^k}{k!} \) y la serie de potencias que representa a \(e^x\).

Buenas tardes, luego de casi un año he vuelto a mirar este hilo, y ya entiendo todo lo que haces. Solo una pequeña duda: ¿la serie $$ \sum_{k\geq0} b_k \frac{x^k}{k!} $$ debería ser convergente, verdad? Lo digo porque todo lo que hacemos en este razonamiento es gracias al Teorema de Mertens, y para ello dicha serie debe ser convergente.

Saludos.

[Masacroso]

Buenas tardes, luego de casi un año he vuelto a mirar este hilo, y ya entiendo todo lo que haces. Solo una pequeña duda: ¿la serie $$ \sum_{k\geq0} b_k \frac{x^k}{k!} $$ debería ser convergente, verdad? Lo digo porque todo lo que hacemos en este razonamiento es gracias al Teorema de Mertens, y para ello dicha serie debe ser convergente.

Hola, acabo de ver de casualidad esto. Si ves que no contesto a algo en un par de días es o bien porque no he visto la pregunta (lo más probable) o bien porque la he visto y me he liado con alguna cosa y he olvidado luego contestarlo (menos probable, pero ya ha ocurrido), entonces en esos casos puedes escribirme un mensaje privado diciendo algo como "¿puedes echar un vistazo a este tema?" y así cuando vea el foro veré el mensaje y contesto seguro.

No, en lo anterior no es necesario que ninguna de las series converja, por eso hago referencia a que son series formales. Las series formales sobre un cuerpo \( \mathbb{K} \) cualquiera definen un anillo, que es una estructura algebraica. Es decir, que el producto de dos series formales siempre está bien definido en este contexto, y tal producto es único. La razón es que el producto de dos series formales es una operación algebraica, esto es, una operación sobre \( \mathbb{K} \) con un número finito de elementos, es por eso que aquí no es necesaria ninguna noción de límite o de topología, es álgebra pura y dura.

Por aclararlo más: sean \( s,t\in \mathbb{C}[\![X]\!] \), donde \( \mathbb{K}[\![X]\!] \) representa el anillo de series formales sobre un cuerpo \( \mathbb{K} \), entonces \( s=\sum_{k=0}^{\infty }s_k X^k \) y \( t=\sum_{k=0}^{\infty }t_k X^k \) para coeficientes cualesquiera \( s_k,t_k\in \mathbb{C} \), y el producto de \( s \) y \( t \) se define como

\[
s\cdot t:=\sum_{k=0}^{\infty }c_k X^k,\quad \text{ donde }\,c_k:=\sum_{j=0}^k s_j t_{k-j}\,\text{ para cada }\, k\in \mathbb N\cup\{0\}
\]

Observa que tal operación es algebraica, porque para definir cada \( c_k \) sólo necesitamos realizar un número finito de operaciones en \( \mathbb{C} \). Como en todo anillo si uno de los elementos es invertible tal inverso es único, por tanto de lo anterior podemos deducir la relación que dejé en mi anterior respuesta observando que \( \left(\sum_{k=0}^{\infty }\frac{a_k}{k!} X^k\right)\cdot \left(\sum_{k=0}^{\infty }\frac1{k!}X^k\right)=\sum_{k=0}^{\infty }\frac{b_k}{k!} X^k \) para \( b_k=\sum_{j=0}^k a_j \binom{k}{j} \), y que \( \left(\sum_{k=0}^{\infty }\frac1{k!}X^k\right)^{-1}=\sum_{k=0}^{\infty }\frac{(-1)^k}{k!}X^k \). Intenta comprobarlo por ti mismo, y si hay algo que no ves o te produzca dudas comenta de nuevo.

P.D.: en lo anterior la \( X \) es un símbolo, no tiene que representar alguna cosa conocida, simplemente es un símbolo que sigue la regla de suma y multiplicación definidas en el anillo.