Pensaba en la demostración por inducción de la fórmula cerrada para calcular
\[
\sum_{k=1}^{n}k.
\]
Supongamos que se nos presenta la sospecha de que debe ser un polinomio cuadrático $a_{2}n^{2}+a_{1}n+a_{0}$.
¿Qué tal si lo tomamos por cierto para $n-1$, y vemos cómo deben acomodarse las cosas para que sea cierto para $n$? Vale: debe satisfacerse
\begin{align*}
\sum_{k=1}^{n}k &= \sum_{k=1}^{n-1}k+n \\
&= a_{2}(n-1)^{2}+a_{1}(n-1)+a_{0}+n\\
&= a_{2}n^{2}+a_{1}n+a_{0},
\end{align*}
de donde se infiere que
\begin{align*}
-2a_{2}+a_{1}+1&=a_{1},\\
a_{2}-a_{1}+a_{0}&=a_{0},
\end{align*}
y por ello que $a_{2}=\frac{1}{2}$ y que $a_{1}=\frac{1}{2}$. ¿Qué pasa con la $a_{0}$? No queda determinada, excepto porque tiene que cumplirse el caso base, lo que obliga a que $a_{0}=0$.
Listo, la fórmula y la demostración de un solo golpe. Creo que algo así es lo que propone Zeilberger como el "polynomische Ansätze", y que es un poco mejor que solamente ajustar algunos resultados de la suma con un polinomio.
miércoles, 28 de noviembre de 2012
martes, 20 de noviembre de 2012
Va el segundo...
Veo con deleite que en el volumen 7, número 2 del 2012 de la revista "Contributions to Discrete Mathematics", aparece por fin mi artículo "Antichains and counterpoint dichotomies". Ya tenía un rato en arXiv, de cualquier manera, y pueden comprobar con las versiones de preimpreso mi genialidad para cometer errores y desatinos.
Como bien agregaron los editores, recibieron mi artículo en el 8 de junio de 2010 y lo terminaron de procesar básicamente para el 26 de septiembre de este año. Un intervalo de tiempo muy normal para un autor de mi calibre, según tengo entendido.
¡Vamos ahora por el tercero!
Como bien agregaron los editores, recibieron mi artículo en el 8 de junio de 2010 y lo terminaron de procesar básicamente para el 26 de septiembre de este año. Un intervalo de tiempo muy normal para un autor de mi calibre, según tengo entendido.
¡Vamos ahora por el tercero!
jueves, 15 de noviembre de 2012
Una pregunta tonta
Pensando en un viejo problema, me pregunté: "¿Cuál es la probabilidad de que una permutación aleatoria de $2k$ objetos mande por lo menos a uno de un subconjunto $A$ de ellos a $\complement A$, donde $|A|=k$?".
Digamos que $U_{i}$ es el evento "el $i$-ésimo elemento de $A$ es enviado a $\complement A$". Lo que deseaba calcular es $P(\cup_{i=1}^{k} U_{i})$. Se puede aplicar el principio de inclusión y exclusión sumando las probabilidades de $U_{i}$, luego restando las de todos los pares $U_{i}\cap U_{j}$ (que es la probabilidad de que un par de elementos de $A$ caiga afuera de $A$ bajo la permutación), después sumando las de todas las triplas, y así sucesivamente.
Para este fin, primero observamos que la suma de las probabilidades de que "se salgan" las $j$-tuplas es \[ \sum_{a\in\binom{A}{j}}\frac{\binom{k}{j}}{\binom{2k}{j}}=\frac{\binom{k}{j}^{2}}{\binom{2k}{j}}, \] pues la probabilidad de que una $j$-tupla $a$ vaya a $\complement A$ es el cociente de las $j$-tuplas de $\complement A$ sobre el total de $j$-tuplas disponibles.
Ahora sí: \[ P\left(\bigcup_{i=1}^{k} U_{i}\right) = \sum_{j=1}^{k}(-1)^{j-1}\frac{\binom{k}{j}^{2}}{\binom{2k}{j}}, \] lo cual se ve un poco intimidante. Pero, vaya, se supone que ya existen métodos automáticos para calcular estas cosas. Le pregunté a Wolfram Alpha primero, sin obtener un resultado del todo satisfactorio (¿es así de "complicado"?). Después decidí ir con el buen Maxima, para que me calculara algunos de los términos de la sucesión de probabilidades, y obtuve:
Satisfactoriamente regular, ¿cierto? Los hay que ya habrán visto que es esto (y desde hace rato, quizá), pero aguántenme un segundito. De aquí fuí con la OEIS y encontré que los denominadores de estas fracciones son los coeficientes binomiales centrales.
¡Claro! (y va la palmada en la frente): la probabilidad de que una elección de $k$ elementos entre $2k$ no vaya a sí misma bajo la permutación es obviamente la de que su imagen sea cualquiera de los otros $k$-subconjuntos disponibles: \[ P\left(\bigcup_{i=1}^{k} U_{i}\right) = \sum_{j=1}^{k}(-1)^{j-1}\frac{\binom{k}{j}^{2}}{\binom{2k}{j}} = \frac{\binom{2k}{k}-1}{\binom{2k}{k}}. \] Y eso es lo que significa el resultado de Wolfram Alpha. Es por cosas como ésta que me gusta tanto la Matemática.
Digamos que $U_{i}$ es el evento "el $i$-ésimo elemento de $A$ es enviado a $\complement A$". Lo que deseaba calcular es $P(\cup_{i=1}^{k} U_{i})$. Se puede aplicar el principio de inclusión y exclusión sumando las probabilidades de $U_{i}$, luego restando las de todos los pares $U_{i}\cap U_{j}$ (que es la probabilidad de que un par de elementos de $A$ caiga afuera de $A$ bajo la permutación), después sumando las de todas las triplas, y así sucesivamente.
Para este fin, primero observamos que la suma de las probabilidades de que "se salgan" las $j$-tuplas es \[ \sum_{a\in\binom{A}{j}}\frac{\binom{k}{j}}{\binom{2k}{j}}=\frac{\binom{k}{j}^{2}}{\binom{2k}{j}}, \] pues la probabilidad de que una $j$-tupla $a$ vaya a $\complement A$ es el cociente de las $j$-tuplas de $\complement A$ sobre el total de $j$-tuplas disponibles.
Ahora sí: \[ P\left(\bigcup_{i=1}^{k} U_{i}\right) = \sum_{j=1}^{k}(-1)^{j-1}\frac{\binom{k}{j}^{2}}{\binom{2k}{j}}, \] lo cual se ve un poco intimidante. Pero, vaya, se supone que ya existen métodos automáticos para calcular estas cosas. Le pregunté a Wolfram Alpha primero, sin obtener un resultado del todo satisfactorio (¿es así de "complicado"?). Después decidí ir con el buen Maxima, para que me calculara algunos de los términos de la sucesión de probabilidades, y obtuve:
| $k$ | $P$ |
|---|---|
| $3$ | $\frac{19}{20}$ |
| $4$ | $\frac{69}{70}$ |
| $5$ | $\frac{251}{252}$ |
| $6$ | $\frac{923}{924}$ |
| $7$ | $\frac{3431}{3432}$ |
Satisfactoriamente regular, ¿cierto? Los hay que ya habrán visto que es esto (y desde hace rato, quizá), pero aguántenme un segundito. De aquí fuí con la OEIS y encontré que los denominadores de estas fracciones son los coeficientes binomiales centrales.
¡Claro! (y va la palmada en la frente): la probabilidad de que una elección de $k$ elementos entre $2k$ no vaya a sí misma bajo la permutación es obviamente la de que su imagen sea cualquiera de los otros $k$-subconjuntos disponibles: \[ P\left(\bigcup_{i=1}^{k} U_{i}\right) = \sum_{j=1}^{k}(-1)^{j-1}\frac{\binom{k}{j}^{2}}{\binom{2k}{j}} = \frac{\binom{2k}{k}-1}{\binom{2k}{k}}. \] Y eso es lo que significa el resultado de Wolfram Alpha. Es por cosas como ésta que me gusta tanto la Matemática.
miércoles, 14 de noviembre de 2012
¿Cómo dicen los pollitos?
Es tristemente común tomar los dígitos que integran una constante o sucesión matemática famosa para producir "música" (la Online Encyclopedia of Integer Sequences inclusive lo hace de manera automática). De este modo se exhibe, supuestamente, la conexión que existe entre ambas áreas, siendo que la relación es mucho más profunda de lo que se pudiera imaginar de manera simplista.
Más específicamente, mi opinión al respecto es que lo que se haga de música usando a $\pi$, por nombrar un ejemplo concreto, debe expresar de algún modo la naturaleza del número en cuestion. En este sentido, simplemente escribirla en binario y tocar si el dígito es 1 y no tocar si es 0 no es realmente interesante, y menos si se eligen las armonías para disfrazar el hecho de que la configuración rítmica de lo que resulta es bastante caprichosa. Así es bastante fácil obtener algo bonito, pero que pudo venir de las codificaciones binarias de la poesía de Sor Juana Inés de la Cruz o el número de flatulencias diarias de una persona a lo largo de un mes sin que se distinga una gran diferencia. Una canción sobre las ideas de Arquímedes, Ramanujan u otros me gustaría infinitamente más.
Tomando cartas en el asunto, decidí componer algo a dos voces con un cierto patrón rítmico de fondo usando a $\pi$. La primera voz emitiría un tono fijo, mientras que la otra distaría de ésta los sucesivos intervalos \[ 3, \frac{13}{4}, \frac{16}{5}, \frac{19}{6} \quad\text{y}\quad \frac{22}{7} \] de ida y de regreso. Éstas son sucesivas aproximaciones cada vez mejores de $\pi$.
Usando Audacity, es fácil generar una onda sinusoidal (quise usar una cuadrada o triangular, pero eso hubiera vuelto redundantemente desagradable (¡o agradable!) el resultado). Un pequeño problema que encontré es que, si no se elige apropiadamente la frecuencia del "cantus firmus", entonces al multiplicarla por estos racionales no da siempre un número con una expansión decimal finita, y entonces al concatenar los tonos del "discanto" se oían pequeños chasquidos que no me gustaron.
Una solución, por supuesto, es tomar el mínimo común múltiplo de los denominadores de las fracciones como frecuencia base, que es simplemente el producto $4\times 5\times 6\times 7 = 840$, pero en hercios es demasiado agudo. De todos modos construí el "contrapunto" simple con estas frecuencias y luego lo transporté a un tono menos agrio para el oído humano.
Haciendo más experimentos con aproximaciones racionales, noté que después de $\frac{22}{7}$ ya era muy difícil distinguir la diferencia entre los intervalos, y por eso hasta ahí llegue. Sin embargo, quería plasmar la notable aproximación $\frac{355}{113}$, que no se puede mejorar con un denominador de menos de cinco dígitos decimales. Si no se podía en el dominio de la frecuencia, se podía en el del tiempo. Por ello, introduje dos pulsos "rítmicos" de modo que los cocientes entre sus frecuencias fueran justamente $\frac{355}{113}$. En lo particular, me gusta mucho lo que se obtiene, pues al ser números coprimos tardan mucho en coincidir y generan muchas síncopas interesantes en el proceso. Esta idea no es original, desde luego, y pueden revisar una página titulada Euclidean Rythms para ensayar interesantes combinaciones rítmicas de coprimos.
Respecto a la obra que salió de todo esto, vale apuntar que introduje varios crescendi y decrescendi para hacer tolerable la adición de los ingredientes de la mezcla, y que la proporción inicial de tonos $3:1$ es una quinta sobre una octava en la afinación pitágorica, que es muy placentera y que genera un excelente contraste con lo inquieto que se oye el $22:7$ de en medio.
Para finalizar, en una entrada previa dije que una composición fea debe ser aburrida o incomprensible. Creo que mi opus 33 no es fea en este sentido, pues el ritmo y los intervalos extraños la hacen de todo menos sosa. Por otro lado, podría resultar difícil de interpretar (de hecho, no creo que pueda ser tocada por seres humanos, si alguien lo intenta le suplico me comunique cómo le fue), pero la explicación que acabo de dar elimina este obstáculo al menos un poco. Como quiera que fuese, mi objetivo no era conseguir una belleza fácil, sino expresar algo un poco más profundo, y que curiosamente se acomodó todo bien al final. En lo personal, el resultado me fascinó, y las pocas impresiones que he recogido hasta el momento me han convencido de que no quedé muy lejos de conseguir mi cometido.
¿Qué opinan ustedes?
P. D.: Hay otra versión con tonos más agudos, por si las quieren comparar.
P. D. 2: No son flatulencias, pero me refería algo como lo que hicieron con electroencefalografía ciertos investigadores cuando digo que se puede utilizar cualquier cosa.
P. D. 3: Intenté torturar a alumnos míos con estas obras, y lejos de resultar aturdidos o asqueados, me indicaron que esta música tiene un aire trance, y que recuerda a la obra de Armin van Buuren. ¡Vaya!
Más específicamente, mi opinión al respecto es que lo que se haga de música usando a $\pi$, por nombrar un ejemplo concreto, debe expresar de algún modo la naturaleza del número en cuestion. En este sentido, simplemente escribirla en binario y tocar si el dígito es 1 y no tocar si es 0 no es realmente interesante, y menos si se eligen las armonías para disfrazar el hecho de que la configuración rítmica de lo que resulta es bastante caprichosa. Así es bastante fácil obtener algo bonito, pero que pudo venir de las codificaciones binarias de la poesía de Sor Juana Inés de la Cruz o el número de flatulencias diarias de una persona a lo largo de un mes sin que se distinga una gran diferencia. Una canción sobre las ideas de Arquímedes, Ramanujan u otros me gustaría infinitamente más.
Tomando cartas en el asunto, decidí componer algo a dos voces con un cierto patrón rítmico de fondo usando a $\pi$. La primera voz emitiría un tono fijo, mientras que la otra distaría de ésta los sucesivos intervalos \[ 3, \frac{13}{4}, \frac{16}{5}, \frac{19}{6} \quad\text{y}\quad \frac{22}{7} \] de ida y de regreso. Éstas son sucesivas aproximaciones cada vez mejores de $\pi$.
Usando Audacity, es fácil generar una onda sinusoidal (quise usar una cuadrada o triangular, pero eso hubiera vuelto redundantemente desagradable (¡o agradable!) el resultado). Un pequeño problema que encontré es que, si no se elige apropiadamente la frecuencia del "cantus firmus", entonces al multiplicarla por estos racionales no da siempre un número con una expansión decimal finita, y entonces al concatenar los tonos del "discanto" se oían pequeños chasquidos que no me gustaron.
Una solución, por supuesto, es tomar el mínimo común múltiplo de los denominadores de las fracciones como frecuencia base, que es simplemente el producto $4\times 5\times 6\times 7 = 840$, pero en hercios es demasiado agudo. De todos modos construí el "contrapunto" simple con estas frecuencias y luego lo transporté a un tono menos agrio para el oído humano.
Haciendo más experimentos con aproximaciones racionales, noté que después de $\frac{22}{7}$ ya era muy difícil distinguir la diferencia entre los intervalos, y por eso hasta ahí llegue. Sin embargo, quería plasmar la notable aproximación $\frac{355}{113}$, que no se puede mejorar con un denominador de menos de cinco dígitos decimales. Si no se podía en el dominio de la frecuencia, se podía en el del tiempo. Por ello, introduje dos pulsos "rítmicos" de modo que los cocientes entre sus frecuencias fueran justamente $\frac{355}{113}$. En lo particular, me gusta mucho lo que se obtiene, pues al ser números coprimos tardan mucho en coincidir y generan muchas síncopas interesantes en el proceso. Esta idea no es original, desde luego, y pueden revisar una página titulada Euclidean Rythms para ensayar interesantes combinaciones rítmicas de coprimos.
Respecto a la obra que salió de todo esto, vale apuntar que introduje varios crescendi y decrescendi para hacer tolerable la adición de los ingredientes de la mezcla, y que la proporción inicial de tonos $3:1$ es una quinta sobre una octava en la afinación pitágorica, que es muy placentera y que genera un excelente contraste con lo inquieto que se oye el $22:7$ de en medio.
Para finalizar, en una entrada previa dije que una composición fea debe ser aburrida o incomprensible. Creo que mi opus 33 no es fea en este sentido, pues el ritmo y los intervalos extraños la hacen de todo menos sosa. Por otro lado, podría resultar difícil de interpretar (de hecho, no creo que pueda ser tocada por seres humanos, si alguien lo intenta le suplico me comunique cómo le fue), pero la explicación que acabo de dar elimina este obstáculo al menos un poco. Como quiera que fuese, mi objetivo no era conseguir una belleza fácil, sino expresar algo un poco más profundo, y que curiosamente se acomodó todo bien al final. En lo personal, el resultado me fascinó, y las pocas impresiones que he recogido hasta el momento me han convencido de que no quedé muy lejos de conseguir mi cometido.
¿Qué opinan ustedes?
P. D.: Hay otra versión con tonos más agudos, por si las quieren comparar.
P. D. 2: No son flatulencias, pero me refería algo como lo que hicieron con electroencefalografía ciertos investigadores cuando digo que se puede utilizar cualquier cosa.
P. D. 3: Intenté torturar a alumnos míos con estas obras, y lejos de resultar aturdidos o asqueados, me indicaron que esta música tiene un aire trance, y que recuerda a la obra de Armin van Buuren. ¡Vaya!
lunes, 12 de noviembre de 2012
Necrologías de sorpresa (1)
Impactado me entero, por medio del discurso del actual presidente de la Sociedad Matemática Mexicana durante la inauguración de la más reciente edición del Congreso Nacional de dicha asociación, que han fallecido este año:
Del Dr. Lacomba hay poco que agregar después de comprobar que fue alumno de Stephen Smale. Un artículo de 1973 publicado por él en "Transactions of the American Mathematical Society", según parece, resume los resultados de su disertación doctoral. Grosso modo, y hasta donde llega mi entendimiento, estudió las geodésicas (o caminos más cortos) en ciertos espacios usando ideas de su director de tesis.
Del Dr. Ize resalto que aparentemente está listado como "George Ize" en el Mathematics Genealogy Project, y que algo de su calibre se manifiesta al ver que su director de tesis fue Louis Nirenberg (éste último fue el primer premiado con la Medalla Chern). Su área de estudio fueron los sistemas dinámicos, y adivino que su disertación doctoral clasificaba algunos de los entresijos de los operadores de Fredholm, que aparecen en las ecuaciones integrales.
Resulta muy curioso también que, salvo que me equivoque con el Dr. Humberto Cárdenas, todos los directores de tesis de estos tres matemáticos mexicanos viven todavía. QEPD, grandes pioneros de la Matemática en México.
- Francisco Raggi Cárdenas (12 de junio),
- Ernesto Alejandro Lacomba Zamora (26 de junio),
- Jorge Ize Lamache (16 de agosto).
Del Dr. Lacomba hay poco que agregar después de comprobar que fue alumno de Stephen Smale. Un artículo de 1973 publicado por él en "Transactions of the American Mathematical Society", según parece, resume los resultados de su disertación doctoral. Grosso modo, y hasta donde llega mi entendimiento, estudió las geodésicas (o caminos más cortos) en ciertos espacios usando ideas de su director de tesis.
Del Dr. Ize resalto que aparentemente está listado como "George Ize" en el Mathematics Genealogy Project, y que algo de su calibre se manifiesta al ver que su director de tesis fue Louis Nirenberg (éste último fue el primer premiado con la Medalla Chern). Su área de estudio fueron los sistemas dinámicos, y adivino que su disertación doctoral clasificaba algunos de los entresijos de los operadores de Fredholm, que aparecen en las ecuaciones integrales.
Resulta muy curioso también que, salvo que me equivoque con el Dr. Humberto Cárdenas, todos los directores de tesis de estos tres matemáticos mexicanos viven todavía. QEPD, grandes pioneros de la Matemática en México.
Suscribirse a:
Entradas (Atom)