Una relación entre el error relativo de un número aproximado y el número de dígitos significativos exactos

Leyendo el clásico libro de Demidovich y Maron sobre introducción al cálculo numérico, he recordado este interesante teorema —una demostración del cual se puede leer en la página 32 de dicho libro— que relaciona el número de dígitos significativos exactos de una número aproximado con una cota de error relativo, y que resumo a continuación.

  El error relativo en una aproximación $\bar{x}$ de un número $x$, con $n$ dígitos signifativos exactos ($\bar{x}=.d_{1}d_{2}\ldots d_{n}\times 10^{e}$) es menor o igual que $\dfrac{1}{d_n}\cdot 10^{1-n}$, donde $d_n$ es el dígito más significativo de la aproximación.

Ejemplo: Podemos aproximar $\sqrt{2}$ por $1,41=0.141\times 10^1$, con $3$ dígitos significativos exactos. Entonces, como el dígito más signicativo es $1$ y $n=3$, tenemos que el error relativo en la aproximación de $\sqrt{2}$ cumple que $e_{r}(\sqrt{2})\le \dfrac{1}{1}\cdot 10^{1-3}=10^{-2}=0.01=1\,\%$

COMENTARIO. Recordemos que una aproximación $\bar{x}=.d_{1}d_{2}\ldots d_{n}\times 10^{e} \approx x$ tiene todos sus dígitos exactos si el error absoluto es menor o igual que media unidad del orden del dígito menos significativo, esto es, $|x-\bar{x}|\le \dfrac{1}{2}\cdot 10^{-n}$
$\square$
-oOo-
Referencias:
  Demidovich, B.P,; Maron, I.A., Cálculo Numérico Fundamental, Paraninfo, Madrid, 1988

Acerca de algunas funciones discretas básicas

Entenderemos por funciones discretas las definidas en $\mathbb{R}$ sobre $\mathbb{Z}$, esto es, las funciones que envían números reales a números enteros. Como su nombre sugiere, son importantes en cálculo numérico, programación y matemática discreta. Básicamente, se construyen mediante las funciones suelo y techo. Así, siendo $x \in \mathbb{R}$, se definen de la siguiente manera:

$\text{suelo}(x) \equiv \lfloor x \rfloor \overset{\text{def}}{=}\text{máximo}\{k\in \mathbb{Z}: k\le x\}$, o lo que es lo mismo, $y=\lfloor x \rfloor : y=\{y\in \mathbb{Z} \wedge x\in \mathbb{R} \wedge y \le x \prec y+1\}$
Ejemplos: a) $\lfloor 4,7 \rfloor = 4$, b) $\lfloor -2.6 \rfloor = -3$
y
$\text{techo}(x) \equiv \lceil x \rceil \overset{\text{def}}{=}\text{máximo}\{k\in \mathbb{Z}: k\ge x\}$ , o lo que es lo mismo, $y=\lceil x \rceil : y=\{y\in \mathbb{Z} \wedge x\in \mathbb{R} \wedge y-1 \prec x \le y\}$
Ejemplos: c) $\lceil 4,7 \rceil = 5$, b) $\lceil -2.6 \rceil = -2$


Mediante estas dos funciones podemos hablar de la parte entera de un número real, entendiéndola como la función suelo. En muchos libros de texto suele notarse de la forma $E(x)\equiv\lfloor x \rfloor$ - y se suele notar de la forma $[x]$, esto es, definiéndola de la forma $[x]=E(x):=n \Leftrightarrow n \le x \lt n+1$ -, esto es, endiendo ésta como la función suelo. Así, en muchos lenguajes de programación (como, por ejemplo, Python), $E(x)$ se invoca mediante la instrucción $\text{int}(x)\equiv\lfloor x \rfloor$

Ejemplos: e) $[ 4,7 ] = 4$, f) $[ -2.6 ] = -3$


Observación. No obstante, en el lenguaje de programación C, se sigue otra definición que es la siguiente $\text{int}_{C}(x)=\left\{\begin{matrix}\lceil x \rceil & \text{si} & x \prec 0 \\ \lfloor x \rfloor & \text{si} & x \ge 0 \end{matrix}\right.$
Ejemplos: g) $\text{int}_{C}( 4,7) = 4$, b) $\text{int}_{C}( -2.6) = -2$


-oOo-

Funciones de redondeo y truncamiento Para enviar un número real, $x$, a un número entero por truncamiento utilizamos la siguiente función: $$\mathcal{T}(x)=\left\{\begin{matrix}\lceil x\rceil & \text{si} & x \prec 0 \\ \lfloor x\rfloor & \text{si} & x \ge 0\end{matrix}\right.$$ y para hacerlo por redondeo empleamos $$\mathcal{R}(x)=\left\{\begin{matrix}\lceil x-0.5\rceil & \text{si} & x \prec 0 \\ \lfloor x+0.5\rfloor & \text{si} & x \ge 0\end{matrix}\right.$$
Ejemplos:
i) $\mathcal{T}(1,9)=1$, h) $\mathcal{T}(-1.2)=-2$
j) $\mathcal{R}(1,9)=2$, k) $\mathcal{R}(-1.2)=-2$

Por otra parte, para truncar y redondear ( respectivamente ) un número real a otro número real con un cierto número de dígitos, $n$, en la parte decimal lo hacemos de la siguiente manera: $$\mathcal{T}(x;n)=\left\{\begin{matrix}\dfrac{\lceil 10^{n}\cdot x \rceil}{10^n} & \text{si} & x \prec 0 \\ \\ \dfrac{\lfloor 10^{n}\cdot x \rfloor}{10^n} & \text{si} & x \ge 0 \end{matrix}\right.$$ y para redondear $$\mathcal{R}(x;n)=\left\{\begin{matrix}\dfrac{\lceil 10^{n}\cdot x -0.5 \rceil}{10^n} & \text{si} & x \prec 0 \\ \\ \dfrac{\lfloor 10^{n}\cdot x +0.5 \rfloor}{10^n} & \text{si} & x \ge 0 \end{matrix}\right.$$ Ejemplos:
l) $\mathcal{T}(\pi,3)=3.141$, m) $\mathcal{T}(-2.6785,3)=-2.678$
n) $\mathcal{R}(\pi,3)=3.142$, p) $\mathcal{R}(-2.6785,3)=-2.679$
$\square$
-oOo-
Referencias:
  [1] Funciones discretas, https://es.wikipedia.org/wiki/Funci%C3%B3n_discreta, Wikipedia
  [2] Moreno, C., Introducción al Cálculo Numérico, UNED, Madrid, 2011

Representación en punto flotante en base 10 y en base 2

  En el siguiente ejemplo se muestra la manera de representar en el formato de punto flotante varios números reales (expresados en base 10) en la misma base o en base 2, y con un cierto número de dígitos significativos

NOTA PRELIMINAR. En la representación de un númro real $x$ en el formato de coma flotante, se considera el conjunto de dígitos $\mathcal{M}$, de tal manera que $$\text{float}(x):=\pm\,0.d_{1}\,d_{2}\,\ldots\times b^e\approx \pm\,0.d_{1}\,d_{2}\,\overset{\underbrace{n}}{\ldots},d_{n}\times b^e$$ que es la representación finita de dicha cantidad, donde $0\le d_i \prec b$ para $i=1,2,\ldots ,n$, siendo $b$ un número entero positivo que corresponde a la base de la representación, y el número entero $e$ es el exponente, que puede variar en un determinado rango; y, finalmente, el número entero positivo $n$ da cuenta de la precisión de la representación. La parte fraccionaria se denomina mantisa ( $0.d_{1}d_{2}\ldots d_{n}$ ). Para pasar a la represntación finita, utilizaremos la siguiente notación para notar las necesarias operaciones de truncamiento o bien de redondeo — recordemos que lo usual será hacerlas por redondeo &madash;: $$\mathbb{R}\ni \text{float}(x)=\pm\,0.d_{1}d_{1}\ldots \times b^e \approx \left\{\begin{matrix}\mathcal{T}(x;n)=\text{Ent}(b^n \times 0.m)\times b^{e-n} \\ \mathcal{R}(x;n)=\text{Ent}(b^n \times 0.m+\mu)\times b^{e-n}\end{matrix}\right.$$ donde $\mu$ denota media unidad en el sistema de numeracíon de base $b$ que se emplee; así, si $b=10$ es claro que $\mu=0.5$, y, si, por ejemplo, $b=2$, entonces $\mu=0.1_{2}$ ya que $0.1_{2}=2^{-1}=0.5_{10}$


***
ENUNCIADO. Hállese la representación en punto flotante ( sin dígito principal implícito ) de: a) $2/7$ en un sistema con $b=10$ y $n=6$
b) $327$ en un sistema con $b=2$ y $n=6$
c) $-4/3$ en un sistema con $b=2$ y $n=6$

SOLUCIÓN.
a)
$2/4=0.\overline{285714}_{10}\times 10^0$, luego $e=0$. Así, $4/7 \approx \mathcal{R}(4/7;6) =\text{Ent}(10^6 \times 0.\overline{285714}_{10} +0.5 )\times 10^{0-6}=$
  $=\text{Ent}(10^6 \times 0.285714285714\ldots_{10} +0.5 )\times 10^{-6}$
    $=\text{Ent}(285714.5) \times 10^{-6}$
      $=285714 \times 10^{-6}$
        $=0.285714 \times 10^{0}$

b)
$327_{10}=101000111_{2}=0.101000111_{2}\times 2^9$, luego $e=9$
Entonces, $0.101000111_{2}\times 2^9 \approx \mathcal{R}(0.101000111_{2}\times 2^9;6)=$
  $=\text{Ent}(2^6\times 0.101000111_{2}+\mu)\times 2^{9-6}$
    $=\text{Ent}(101000.111_{2}+\mu)\times 2^{3}$, donde $\mu$ ( media unidad en el sistema binario ) es $0.1_{2}$ ya que esto a su vez es igual a $0.5_{10}$
    $=\text{Ent}(101000.111_{2}+.1_{2})\times 2^{3}$
    $=\text{Ent}(101001.011_{2})\times 2^{3}$
      $=101001_{2}\times 2^{3}$
        $=0.101001_{2}\times 2^6 \times 2^{3}$
          $=0.101001_{2}\times 2^{9}$
Observación. Veamos esa cantidad en base $10$:
            $=(1\times 2^{-1}+1\times 2^{-3}+1\times 2^{-6})\times 2^{9}$
              $=1\times 2^{8}+1\times 2^{6}+1\times 2^{3}$
                $=256+64+8$
                  $=328$

c)
$4/3=1.\overline{3}_{10}=1.01010101\ldots_{2}=0.10101010\ldots_{2}\times 2^1$, luego $e=1$
Entonces $0.10101010\ldots_{2}\times 2^1 \approx$
  $\approx \mathcal{R}(0.10101010\ldots_{2};6)=$
    $=\text{Ent}(2^6\times 0.10101010\ldots_{2}+\mu)\times 2^{1-6}$, donde $\mu$ ( media unidad en el sistema $b=2$) es $\mu=.1_{2}=2^{-1}=0.5_{10}$; y, siendo $e=1$ y $n=6$, el exponente $e-n=1-6=-5$
      $=\text{Ent}(101010.1010\ldots_{2}+.1_{2})\times 2^{-5}$
        $=\text{Ent}(101011.0010\ldots_{2})\times 2^{-5}$
          $=101011\ldots_{2}\times 2^{-5}$
            $=1.01011_{2}$
              $=0.101011_{2}\times 2^1$
Finalmente, tendremos en cuenta que $\mathcal{R}(-x)=-\mathcal{R}(x)$, con lo cual podemos escribir que
                $-4/3 \approx \mathcal{R}(-4/3;6)=-\mathcal{R}(4/3;6)=-0.101011_{2}\times 2^1$
$\square$
-oOo- Referencias:
  [1] Moreno, C., Introducción al Cálculo Numérico, UNED, Madrid, 2011
  [2] Aubanell, A. et al., Útiles básicos de Cálculo Numérico, Labor, Barcelona, 1993
  [3] Demindovich, B.O.;Maron, I.A., C., Cálculo Numérico Fundamental, Paraninfo, Madrid, 1988

¿Qué es un grupo simple finito?¿Cómo se clasifican?

Un grupo algebraico es un conjunto de elementos en el que se define una operación interna que cumple las siguiens propiedades: i) asociativa, ii) existencia de elemento neutro, iii) cada elemento del grupo tiene asociado un elemento opuesto con respecto de la operación definida (en el sentido de que dicho elemento operado con su opuesto es igual al elemento neutro); además, si se cumple la propiada conmutativa, diremos que el grupo en cuestión es abeliano (o conmutativo). Cuando el número de elementos de que consta el grupo es finito decimos que el número de elementos de que consta es finito. Pero, ¿a qué nos referimos cuando hablamos de grupos simples (además de finitos)?¿Cómo se clasifican?.

    Sabido es que todo número natural puede descomponerse de manera única en un conjunto de números naturales, más pequeños, llamados primos por no poder a su vez descomponerse en otros más sencillos; así que podemos ver a los números primos como los materiales primigenios de construcción de los números naturales. Tomando esta idea (véase [4]), ¿podrían ciertos grupos finitos, con determinadas características (véase [1]), llamados simples, descomponerse también en un conjunto de grupos más « sencillos »? Pues bien, la respuesta es sí. Los grupos simples, por tanto, son suceptibles de una clasificación (teorema de clasificación, véase [2]): ¿cuántos tipos de grupos simples finitos hay?.

Desde 1955 los algebristas se lanzaron a estudiar las posibles estructuras de dichos grupos finitos simples, y esa tarea monumental fue completada, arduamente, en 2004. Gracias a este gran esfuerzo colectivo se sabe que todo grupo finito simple es: o bien cíclico, o bien alternante, o de una cierta clase de grupos de Lie (los grupos de Lie son de gran importancia en Física) — hay $18$ familias de infinitos de tales grupos (véase [1]) —; o bien es considerado « anómalo », por tratarse de alguno de los $27$ grupos que no encajan en dichas familias, razón por la cual reciben el nombre de grupos (simples finitos) esporádicos. Por cierto, se sabe que el grupo finito simple esporádico más grande tiene casi $10^{54}$ elementos, y por ello, se le llama el Monstruo (véase [3]).

-oOo- Referencias:
  [1] Wikipedia, https://es.wikipedia.org/wiki/Grupo_simple
  [2] Wikipedia, https://es.wikipedia.org/wiki/Teorema_de_clasificación_de_grupos_simples
  [3] Wikipedia, https://es.wikipedia.org/wiki/Grupo_monstruo
  [4] Freiberger, M.; Thomas, R., Matemáticas. Cien conceptos, Librero, Madrid, 2020

$\square$

La técnica de marcaje y recaptura para estimar el número total de individuos de una población

    La técnica de marcaje y recaptura se suele emplear en ecología para estimar el número total de individuos, $N$, de una cierta especie que habitan en un área delimitada, y consiste en extraer una primera muestra de tamañó $n$, marcando con algún tipo de señal todos los individuos de la misma, liberando después a dichos individuos. Pasado un tiempo razonable, al objeto de que la población se redistribuya de manera homogénea, se extrae una segunda muestra de $m$ individuos, de los cuales, se espera que encontaremos entre ellos $m'$ individuos marcados (que ya formaban parte de la primera muestra). Entonces, teniendo en cuenta que la razón aritmética entre el número de individuos marcados y el número total de individuos en cada muestra debería ser aproximadamente constante, tandrá que cumplirse de manera aproximada la siguiente proporción:
$\dfrac{m'}{m} \sim \dfrac{n}{N}$, y por tanto, el número total de individuos de dicha especie que se estima que hay en el área en la que realizamos el estudio es $N \sim \dfrac{n\,m}{m'}$

Ejemplo del tipo que puede encontrarse en (Yates, 2020):   Queremos estimar el número de caracoles que hay en un jardín. Para ello, capturamos ( en una primera muestra ) 23 individuos ( $n=:23$ ) y los marcamos pegándoles una discreta etiqueta adhesiva en la concha antes de soltarlos. Unos días después, realizamos capturamos otro grupo de caracoles, esta vez fueron ($m=:18$), de los cuales $m'=:3$ tenían la marca que pusimos a los individuos de la primera muestra. Estimemos el número de caracoles, $N$, que hay en el jardín: como
$\dfrac{3}{18} \sim \dfrac{23}{N}$, de donde se obtiene que el número estimado de caracoles que hay en el jardín es $N \sim \dfrac{23\cdot 18}{3} = 138$ individuos en total.
-oOo-
Referencias:
  [1] Yates, K., Los números de la vida, Blackie Books, 2020
  [2] Piñol, J.; Martínez-Vilalta, J., Ecología con números, Lynx, Barcelona, 2006

$\square$

Distribución de bolas (iguales) en urnas sabiendo que algunas de las urnas tienen que quedar vacías

Continuando con los problemas de « bolas y urnas », ligados al patrón de combinaciones con repetición. El caso que se presenta ahora es similar al anterior, sin embargo, ahora fijaremos el número de urnas que deben quedar vacías al distribuir entre ellas un cierto número de bolas.

ENUNCIADO.
  a) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que $s$ cualesquiera de las urnas queden vacías ($s\le k$)?
  b) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que $s$ determinadas urnas queden vacías ?


SOLUCIÓN. En un artículo anterior se ha resuelto el problema básico de repartir $n$ bolas iguales en $k$ urnas, en el que se había justificado que la solución consiste en calcular el número de combinaciones con repetición de $n$ bolas elegidas en una gama de $k$ clases: $$\displaystyle \left(\binom{k}{n}\right):=\dfrac{(n+(k-1))!}{n!\,(n-k)!}=\binom{n+(k-1)}{n}=\binom{n+(k-1)}{k-1}$$
a) Como $s$ urnas tienen que quedar vacías, ahora $k:=k-s$ en la solución del problema genérico, con lo cual tendremos $$\displaystyle \left(\binom{k-s}{n}\right)=\binom{n+((k-s)-1)}{(k-s)-1}=\binom{n+k-s-1}{k-s-1}\,\text{posibilidades}$$

b) Si $s$ determinadas urnas del total de $k$ urnas ($s\ge k$) tienen que quedar vacías, el problema difiere el algo del del apartado anterior. Debemos contabilizar primero de cuántas manera podemos elegir esas $s$ urnas que deberán quedar vacías, y ello se puede hacer de $\displaystyle \binom{k}{s}=k$ maneras distintas. A continuación, razonaremos de la siguiente manera: como de las $k-s$ urnas restantes no deberá quedar ninguna vacía, procedamos a ubicar exactamente $1$ bola en cada una de ellas para poder garantizar tal cosa, y, a continuación, veamos de cuántas manera podemos distribuir las $n-(k-s)$ bolas que nos quedan entre las $k-s$ urnas que deberán contener al menos una bola: estableciendo pues $n:=n-(k-s)$ y $k:=k-s$ en la solución genérica de distribución de bolas iguales en urnas distintas, la solución a este problema de reparto entre las urnas no vacías es $$\displaystyle \left(\binom{k-s}{n-(k-s)}\right)=\binom{(n-(k-s))+(k-s)-1}{(k-s)-1}=\binom{n-1}{k-s}$$
Por consiguiente, teniendo en cuenta además (como ya hemos dicho) las posibilidades que tenemos de elegir las $s$ urnas que han de quedar vacías, tendremos un total de $$\displaystyle \binom{k}{s}\cdot\binom{n-1}{k-s}\,\text{posibilidades}$$

-oOo-
Veamos un caso concreto: EJEMPLO. Supongamos que tenemos $n:=8$ bolas a distribuir en $k:=4$ urnas, de entre las cuales:
  (1) $s:=3$ urnas cualesquiera han de quedar vacías
  (2) $s:=3$ urnas prefijadas han de quedar vacías
¿De cuántas maneras se podrá hacer eso?


SOLUCIÓN.
Recordemos ahora que $n:=8$, $k:=4$ y $s:=3$, luego de las soluciones genéricas deducidas arriba, obtenemos los siguientes resultados:

  (1)             $\displaystyle \binom{8+4-3-1}{4-3-1}=\binom{8}{0}=1$ posibilidad

  (2)             $\displaystyle \binom{4}{3}\cdot \binom{8}{0}=4 \cdot 1=4$ posibilidades
$\square$

-oOo-

Referencias:
  [1] Hernández, V.; Vélez, R.: Dados, monedas y urnas, UNED, Madrid, 1995

Otro problema de distribución de bolas (iguales) en urnas

Seguimos con los problemas de « bolas y urnas », ligados al patrón de combinaciones con repetición. Y, por supuesto, aprovecharemos lo que se ha estudiado ya con anterioridad.

ENUNCIADO.
  a) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que una de las urnas contenga exactamente $r$ bolas ($r\le n$)?
  b) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que, elegida una determinada urna, ésta contenga exactamente $r$ bolas ($r\le n$)?


SOLUCIÓN. En un artículo anterior se ha resuelto el problema básico de repartir $n$ bolas iguales en $k$ urnas, en el que se había justificado que la solución consiste en calcular el número de combinaciones con repetición de $n$ bolas elegidas en una gama de $k$ clases: $$\displaystyle \left(\binom{k}{n}\right):=\dfrac{(n+(k-1))!}{n!\,(n-k)!}=\binom{n+(k-1)}{n}=\binom{n+(k-1)}{k-1}$$
a) Si una de las $k$ urnas (cualquiera de ellas) tiene que contener exactamente $r\le n$ bolas, debemos resolver el problema de repartir $n-r$ urnas en $k-1$ urnas, así que, en la solución básica tendremos que $n:=n-r$ y $k:=k-1$, con lo cual el número de posibilidades es $$\displaystyle \left(\binom{k-1}{n-r}\right)=\binom{(n-r)+((k-1)-1)}{(k-1)-1}=\binom{n-r+k-2}{k-2}$$

b) Si una urna determinada de las $k$ urnas tiene que contener exactamente $r\le n$ bolas, el problema difiere el algo del del apartado anterior. Debemos contabilizar primero de cuántas manera podemos elegir la urna que contiene exactamente $r$ bolas, y ello se puede hacer de $\displaystyle \binom{k}{1}=k$ maneras. A continuación, razonaremos de la siguiente manera: por cada una de esas $k$ posibilidades, sabemos que existen (por la solución encontrada en el apartado anterior) otras tantas $\displaystyle \binom{n-r+k-2}{k-2}$ maneras de distribuir las $n-r$ bolas en las restantes $k-1$ urnas. Finalmente, por tanto, tendremos un total de $$\displaystyle \binom{k}{1}\displaystyle \binom{n-r+k-2}{k-2}=k\,\binom{n-r+k-2}{k-2}\,\text{posibilidades}$$

-oOo-
Veamos un caso concreto: EJEMPLO. Supongamos que tenemos $n:=8$ bolas a distribuir en $k:=4$ urnas, de entre las cuales:
  (1) en una de ellas (una cualquiera) deberá haber $r:=3$ bolas
  (2) en una determinada urna (prefijada) deberá haber $r$ bolas
¿De cuántas maneras se podrá hacer eso?


SOLUCIÓN.
Recordemos ahora que $n:=8$, $k:=4$ y $r:=3$, luego de las soluciones genéricas deducidas arriba, obtenemos los siguientes resultados:

  (1)             $\displaystyle \binom{8-3+4-2}{4-2}=\binom{7}{2}=6$ posibilidades

  (2)             $\displaystyle \binom{4}{1}\cdot \binom{8-3+4-2}{4-2}=4 \cdot 6=24$ posibilidades
$\square$

-oOo-

Referencias:
  [1] Hernández, V.; Vélez, R.: Dados, monedas y urnas, UNED, Madrid, 1995

Del problema de contar el número de maneras de distribuir n bolas iguales entre k urnas identificables (n mayor o igual que k) — de forma que no quede ninguna urna vacía — al problema de contar « rachas »

Nos vamos a plantear ahora un problema que encaja en el patrón de las combinaciones con repetición: el de distribuir un cierto número de bolas iguales en un conjunto de urnas, de tal modo que cada urna vaya a contener por lo menos una bola. Para ello, aprovecharemos lo que se ha estudiado ya con anterioridad. A su vez, este problema constituye, como veremos, un patrón para resolver el de las rachas que se obitienen al extraer bolas de manera sucesiva de una urna que contiene un cierto número de bolas blancas y un cierto números de bolas negras, hasta que ésta quede vacía.

ENUNCIADO. ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), siendo $n\ge k$, de forma que no quede vacía ninguna urna?.

SOLUCIÓN. En el artículo anterior se ha resuelto el problema de repartir $n$ bolas iguales en $k$ urnas, en el que se había justificado que la solución consiste en calcular el número de combinaciones con repetición de $n$ bolas elegidas en una gama de $k$ clases: $$\displaystyle \left(\binom{k}{n}\right):=\dfrac{(n+(k-1))!}{n!\,(n-k)!}=\binom{n+(k-1)}{n}=\binom{n+(k-1)}{k-1}$$ Sin embargo, ahora debemos garantizar que ninguna urna va a quedar vacía, por lo que empezaremos ubicando exactamente una bola en cada urna; y, a continuación, procederemos a distribuir las $n-k$ bolas restantes entre las $k$ urnas. Así, el problema es análogo al que ya tenemos resuelto, pero con $k$ bolas menos. Entonces, la solución al mismo es: $$\displaystyle \left(\binom{k}{n-k}\right)\overset{def}{=}\dfrac{(n-k+(k-1))!}{(n-k)!\,(n-k)!}=\dfrac{(n-1)!}{(n-k)!(n-1-(n-k)!}=\dfrac{(n-1)!}{(n-k)!(k-1)!}=\binom{n-1}{k-1}=\binom{n-1}{n-k}\quad \quad [1]$$
-oOo-
Veamos un caso concreto sobre esto: EJEMPLO 1. ¿De cuántas maneras podemos distribuir $5$ bolas iguales entre $3$ urnas, de manera que no quede ningua urna vacía?.

SOLUCIÓN. Ahora, $n:=5$ y $k:=3$, luego podremos hacerlo de $$\displaystyle \left(\binom{3}{5-3}\right)=\left(\binom{3}{2}\right)=\binom{5-1}{3-1}=\binom{4}{2}=6\,\text{maneras}$$

***

OBSERVACIÓN (El problema de las « rachas »):
  Una bonita aplicación —de la que se habla en (Hernández, 1995)— es el de contar las rachas al extraer de manera sucesiva de una urna que contiene, en un principio, $b$ bolas blacas y $n$ bolas negras, hasta que la que la urna queda vacía, obteniendo secuencias del tipo $BBNNNBBBNBNNNN\,\ldots$. ¿Cuántas rachas formadas de $k$ bolas blancas y $k+1$ bolas negras &mdsh; donde, lógicamente, $k$ deberá cumplir que $k\le a$ y $k+1\le b$ — es posible obtener?.

SOLUCIÓN: Para resolver este problema podemos pensar en el problema patrón de distribuir un cierto número de bolas iguales en un conjunto de urnas, de manera que ninguna de las urnas quede vacía, esto es, de modo que, tras acabar la operación de ubicación de las bolas en las urnas, cada urna acabe conteniendo al menos una bola. Cada racha una de las $k$ rachas de bolas blancas puede asociarse a la distribución de $a$ bolas blancas en $k$ urnas (sin que ninguna de ellas quede vacía); sabemos, de [1] (haciendo $n:=a$) que esto puede hacerse de $\displaystyle \binom{a-1}{k-1}$ maneras, y contabilizando también las $k+1$ rachas de bolas negras intercaladas entre dos rachas de bolas blancas, vemos que, por cada una de esas posibilidades ($k$ rachas de bolas blancas), hay $\displaystyle \binom{b-1}{k+1)-1}=\binom{b-1}{k}$ (haciendo en [1] $n:=b$ y $k:=k+1$). Así pues, tendremos un total de $$\displaystyle \binom{a-1}{k-1}\cdot \binom{b-1}{k}\,\text{maneras de obtener}\,k\,\text{rachas de bolas blancas, y}\,k+1\,\text{rachas de bolas negras}$$ EJEMPLO 2. Consideremos una urna que contiene $8$ bolas, $3$ de las cuales son blancas y $5$ son negras. Nos dedicamos a extraer bolas, de manera sucesiva, hasta que la urna quede vacía. ¿De cuántas maneras pueden darse $2$ rachas de bolas blancas ($k:=2$), estando intercaladas por tanto (dichas rachas), entre $3$ rachas de bolas negras ($k+1=2+1=3$)?.

SOLUCIÓN. Ahora, $a:=3$ y $b:=5$, y $k:=2$, luego tal cosa podrá suceder de $$\displaystyle \binom{3-1}{2-1}\cdot \binom{5-1}{2}=\binom{2}{1}\cdot \binom{4}{2}=2\cdot 6=12\,\text{maneras}$$
$\square$

-oOo-

Referencias:
  [1] Hernández, V.; Vélez, R.: Dados, monedas y urnas, UNED, Madrid, 1995

Combinaciones con repetición: un patrón para llegar a la solución del problema genérico

En otros artículos hemos analizado problemas de variaciones, icluidos los que, en particular, se ajustan a esquemas de permutaciones con repetición. Ahora vamos a ver un problema de combinaciones, cuya solución, en particular, se ajusta a un problema de combinaciones con repetición, solución a la que llegaremos empleando el recurso consistente en realizar una representación equivalente en la que podamos utilizar la idea del cálculo de permutaciones con repetición.

ENUNCIADO. Tres personas se reúnen en la terraza de un bar. En dicho bar solamente sirven dos tipos de bebidas: infusiones y cafés. Cada una de los tres personas pide una única bebida, una infusión o bien un café. ¿Cuántos pedidos pueden realizar?.

SOLUCIÓN. Podemos recurrir a representar las configuraciones o repartos utizando únicamente dos símbolos: el símbolo 'x' para designar la elección efectiva de una de las dos bebida por parte de cada una de las tres personas, y el símbolo '|' para separar los dos compartimentos separadores en la representación de las tres celdas dispuestas en hilera necesarias asociadas a cada tipo de bebida. Así, el problema se reduce a permutar $2-1$ símbolos '|' y $3$ símbolos 'x'. Por tanto, la solución (el número de repartos posibles) es $\displaystyle \dfrac{3+(2-1))!}{3!\cdot (2-1)!}=\dfrac{4!}{6\cdot 1}=4$.

Nota: Denominamos combinaciones con repetición (de $n$ objetos en $k$ clases) al número de $k$-combinaciones con repetición tomadas de un conjunto con $n$ elementos (o número de formas en que se puede extraer un multiconjunto con $k$ elementos de un conjunto con $n$ elementos), y escribimos $\displaystyle CR_{k,n}:=\dfrac{n+(k-1))!}{n!\cdot (k-1)!}=\binom{n+k-1}{k-1}=\binom{n+k-1}{n}$, lo cual también puede designarse de la forma $\displaystyle \left(\binom{k}{n}\right)$. En este problema en concreto, $n:=3$ y $k:=2$.

***
Como problema genérico/patrón, análogo al que acabamos de tratar, puede servirnos el siguiente: el de distribuir/ubicar $n$ bolas idénticas en $k$ urnas perfectamente identificables: la solución es $\displaystyle \left(\binom{k}{n}\right)$.
$\square$

-oOo-

Referencias:
  [1] Hernández, V.; Vélez, R., Dados, monedas y urnas, UNED, Madrid, 1995
  [2] Grimaldi, R.P., Matemáticas. Discreta y combinatoria, Addison-Wesley Iberoamericana, 1989

Matrices y submatrices

Consideremos una matriz $m \times n$ ( $m$ filas y $n$ columnas ). Sin pérdida de generalidad, pongamos que $m:=3$ y $n:=4$ $$A=\begin{pmatrix}a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34}\end{pmatrix}$$ a la cual le corresponde los siguientes conjuntos de índices de filas y columnas, respectivamente: $I=\{1,2,3,4\}$ y $J=\{1,2,3,4\}$. Pues bien, podemos referirnos a una cierta submatriz $B$ de $A$ seleccionando su subconjunto de índices de fila $I_B$ y un subconjunto de índices de columna $J_B$; pongamos que $I_B=\{2,3\}$ y $J_B=\{3,4,\}$, entendiendo dicha submatriz como una matriz de tamaño $(3-2) \times (4-2)$, que, concretamente es $$B\overset{.}{=}A[I_B;J_B]=A[\{2,3\};\{3,4\}]=\begin{pmatrix}a_{23} & a_{24} \\ a_{33} & a_{34} \end{pmatrix}$$ Diremos que una submatriz $B$ de una matriz $A$ es principal si eliminamos las filas y columnas de igual índice, esto es $I_B=J_B$, y lo abreviaremos con la notación $A[I_B]$. Así, por ejemplo, si eliminamos la primera fila y la primera columna, obtenemos la matriz principal $A[\{1\}]=\begin{pmatrix}a_{22} & a_{23} & a_{24} \\ a_{32} & a_{33} & a_{34} \end{pmatrix}$

Por menores complementarios de una matriz $A_{m \times n}$ nos referimos a los determinantes de las submatrices cuadradas, que obtengamos al eliminar una o más de las filas o columnas de la matriz dada.

-oOo- Matrices cuadradas de orden $m$

Si en una matriz cuadrada de orden $m$ seleccionamos las filas y columnas $I=J=\{1,\ldots,k\}$ ( con $k\le m$ ), obtenemos una matriz principal superior; y si seleccionamos las filas y columnas con $I=J=\{k,\ldots,m\}$ obtenemos una matriz principal inferior.
Así, para una matriz $B=\begin{pmatrix}b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ b_{31} & b_{32} & b_{33} \end{pmatrix}$, hay tres submatrices principales superiores: $B[\{1\}]=(b_{11})$, $B[\{1,2\}]=\begin{pmatrix}b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix}$ y $B[\{1,2,3\}]=B$.

Y también tres matrices principales inferiores: $B[\{3\}]=(b_{33})$, $B[\{2,3\}]=\begin{pmatrix}b_{22} & b_{23} \\ b_{32} & b_{33} \end{pmatrix}$ y $B[\{1,2,3\}]=B$

Si se elimina una sola fila y una sola columna, los menores complementarios que así se obtienen se denominan primeros menores de dicha matriz cuadrada, y se necesitan para encontrar la matriz de cofactores, la cual es útil para calcular el determinante y la inversa de matrices cuadradas. Además, en el caso de que la submatriz cuadrada formada sea una submatriz principal, los correspondientes primeros menores se denominan menores principales.


-oOo- Nota. Los determinantes de las matrices principales superiores/inferiores se denominan menores principales superiores/inferiores.

Al eleminar la fila $i$ y la columna $j$ de una matriz cuadrada $A_{m \times m}$ obtenemos el menor complementario que suele notarse de la forma $M_{ij}$; o, como también suele decirse, el $(i,j)$-ésimo menor complementario de $A$ ) y que, lógicamente, es de orden $m-1$. Dicho menor puede entenderse como el que resulta de eliminar la fila y la columna a las que pertenece el elemento $a_{ij}$ de la matriz $A$. Recordemos que en el caso de obtener un cierto menor eliminando una única fila y una única columna, hablamos de primeros menores, por lo que si se obtienen eliminando dos filas y dos columnas, los llamaremos segundos menores, etcétera.$\square$

Factorial de un número entero no negativo con Python3

En este sencillo ejercicio os muestro el código fuente del algoritmo iterativo para calcular el factorial de un número no negativo.

''' Cálculo del factorial de un número entero no negativo  '''
def factorial(n):
    f = 1
    i = 2
    while i <= n:
        f *= i
        i+=1
    return f 


n=int(input('Introduce un número no negativo\n'))
print(n)
print(factorial(n))

-oOo-
Archivo de texto con el código fuente en el lenguaje de programación Python3: [factorial2.txt]

Referencias:
  [1] Vacas, J.A.: Curso de Python, YouTube

$\square$

Ejemplo sencillo de uso de un servidor web con Python (Flask v. 2.0)

Aquí os muestro un ejercicio sencillo --que realicé como alumno en un curso de formación-- de uso de un servidor web mediante Flask v. 2.0 para publicar el resultado del cálculo del factorial de un número entero no negativo, a modo de ejemplos de prueba. Aprovecho también para mostrar un ejemplo básico de cálculo lambda.

-oOo-
Archivo de texto con el código fuente en el lenguaje de programación Python3: [servidorwebmedianteflaskv2.txt]

Referencias:
  [1] Vacas, J.A.: Curso de Python, YouTube

$\square$

Choques de una bola en las bandas de un billar. Un ejercicio con Python3 empleando la librería Pygame

Os muestro en este artículo un ejercicio sencillo de aplicación de la librería Pygame para simular los choques elásticos de una bola en un billar rectangular que elaboré en un curso de formación como alumno.

-oOo-
Archivo de texto con el código fuente en el lenguaje de programación Python3: [choquesboladebillar.txt]

Referencias:
  [1] Vacas, J.A.: Curso de Python, YouTube

$\square$

Ejemplo sencillo de uso de los métodos Math y Statistics (dos de los módulos de la librería estándar de Python

En este sencillo ejercicio os muestro el uso de algunos de los métodos de los módulos Math y Statistics de la librería estándar de Python. Este programa calcula el valor de algunos parámetros estadísticos para un conjunto de datos ( de ejemplo ) de una variable estadística
  Observación: Este programa se ha editado y ejectuado en el entorno Thonny

-oOo-
Archivo de texto con el código fuente en el lenguaje de programación Python3: [ejemplodeusodelosmetodosmathystatistics.txt]

Referencias:
  [1] Vacas, J.A.: Curso de Python, YouTube

$\square$

Un ejemplo de programación orientada a objetos con Python3

En este artículo os muestro una aplicación de la Programación Orientada a Objetos para la realización de unas cuantas operaciones aritméticas básicas que ensayé hace unos meses. El programa consta de una clase padre ( Operaciones ) y una clase hija para cada una de las operaciones ( suma, multiplicación, y división entera )

-oOo-
Archivo de texto con el código fuente en el lenguaje de programación Python3: [ejemplodeorientacionaobjetos.txt]

Referencias:
  [1] Vacas, J.A.: Curso de Python, YouTube

$\square$

Programa en Python3 para realizar recuentos en un fichero de texto

En el enlace al código fuente podéis ver el algoritmo que he escrito para realizar recuentos en un fichero de texto ( número de líneas, número de palabras, y número de caracteres ) en un nuevo fichero ( fichero de resultados ).
  El fichero que hay que analizar, y que he preparado previamente ( con el nombre texto.txt ), está en la carpeta del ejercicio. El nombre del fichero a analizar ( texto.txt ) y el nombre del fichero de los resultados que el programa generará ( resultados.txt ) se solicitan al usuario al inicio del programa. Para analizar otro fichero de texto distinto, habrá que especificar convenientemente los nombres de los mismos.

-oOo-
Archivo de texto con el código fuente en el lenguaje de programación Python3: [recuentosenunficherodetexto.txt]

Referencias:
  [1] Vacas, J.A.: Curso de Python, YouTube

$\square$

Fracciones continuas

Las fracciones continuas tienen muchas aplicaciones; por poner unos cuantos ejemplos, cabe citar: la resolución de ecuaciones diofánticas (restringiéndonos a los números enteros), las pruebas de primalidad (ver si un número es primo o no lo es), la aproximación de números reales (Demidovich, 1988), el desarrollo de funciones en fracciones continuas, o su utilidad en los métodos de factorización (descomposición de un número entero no primo en producto de factores primos). Recordamos aquí algo muy básico (si bien muy importante) sobre las fracciones continuas, si bien voy a omitir la demostración, la cual, si tenéis curiosidad, podéis encontrarla en las referencias indicadas:

    Todo número puede escribirse como una fracción continua. A todo número racional le corresponde una fracción continua finita, mientras que a todo número irracional le corresponde una fracción continua infinita.

EJEMPLO (fracción continua asociada a número decimal exacto):
$\displaystyle 2,56=2+0,56=2+\dfrac{46}{100}=2+\dfrac{14}{25}=2+\dfrac{1}{\dfrac{25}{14}}=2+\dfrac{1}{1+\dfrac{11}{14}}=2+\dfrac{1}{1+\dfrac{1}{\dfrac{14}{11}}}=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{3}{11}}}=$

  $=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{\dfrac{11}{3}}}}=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{2}{3}}}}=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{\dfrac{3}{2}}}}}=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{1+\dfrac{1}{2}}}}}$

Es usual expresar una fracción continua finita $\alpha$ de la forma $[a_0;a_1,a_2,a_3,\ldots,a_n]$; donde el número $a_0$ representa la parte entera de $\alpha$ (el grupo de dígitos que constituyen el número entero a la izquierda de la coma decimal) y los números $a_1,a_2,\ldots,a_n$ son los llamados cocientes incompletos — que van apareciendo en la descomposición iterativa de la cantidad remanente que está en los denominadores (como suma de un entero, que es el cociente incompleto, y una fracción impropia) y que ilustra el ejemplo —. En nuestro caso, podemos escribir $2,56=[2;1,1,3,1,2]$


***
OBSERVACIÓN:
Notemos que un número racional con infinitos dígitos en la parte decimal (periódico puro o mixto), tal como, por ejemplo, $0,\hat{6}:=0,666\ldots$ tiene un número finito de cocientes incompletos, a pesar de tener infinitos dígitos en la parte decimal. En efecto, $\displaystyle 0,\hat{6}:==0+\dfrac{2}{3}=0+\dfrac{1}{\dfrac{3}{2}}=0+\dfrac{1}{1+\dfrac{1}{2}}$, luego podemos escribir $0,\hat{6}:==\dfrac{2}{3}=[0;1,2]$. Otro ejemplo: $0,\hat{3}:=0,333\ldots=0+0,\hat{3}:==0+\dfrac{1}{3}$, luego la fracción propia asociada a $0,\hat{3}:=$ es $[0;3]$
-oOo-
COMENTARIO:
L. Euler, entre otros, utilizó las fracciones continuas para desarrollar funciones. Así, por ejemplo, uno de sus resultados es el desarrollo en funciones continuas de la función $e^x$ obteniendo la misma exactitud que en el desarrollo de McLaurin par $x=1$, $e=2+\dfrac{1}{2!}+\dfrac{1}{3!}+\ldots$, tal como puede verse en lad páginas 82 y 83 de (Demidovich, 1988).$\square$

-oOo-
Referencias:
  [1] Freiberger, M.; Thomas, R.: Math Squared. 100 Concepts You Should Know, Quantum Books United, 2016
      Nota: Puede encontrarse una entrada concisa sobre este concepto en la edición del libro en español (Matemáticas. Cien conceptos), Librero, 2020

  [2] Wikipedia: https://es.wikipedia.org/wiki/Fracción_continua
  [3] Demindovich, B.O.;Maron, I.A., C., Cálculo Numérico Fundamental, Paraninfo, Madrid, 1988

Simulación del lanzamiento simultáneo de dos dados de parchís

Mediante el lenguaje de programación Python3, vamos a tratar la simulación del lanzamiento simultáneo de dos dados de parchís no trucados y el cálculo de la probabilidad de que la suma de las puntuaciones en un lanzamiento sea igual a un determinado valor.

  Las caras de sendos dados están numeradas del '1' al '6', dichos valores son los elementos de las respectivas LISTAS asociadas a cada dado, las cuales se recorren iterativamente de forma anidada para formar ( utilizando la instrucción 'add' ) el CONJUNTO de las 2-tuplas del espacio muestral así como el CONJUNTO de las 2-tuplas de los resultados favorables a que el valor de la suma de las puntuaciones del lanzamiento simultáneo de los dos dados sea igual a un valor requerido por el usuario.

  Así pues, en el programa se hace uso de dos LISTAS y de dos CONJUNTOS.

  Finalmente, se calcula la probabilidad de que el resultado de la suma de las puntuaciones de los dos dados que se lanzan sea igual a un determinado valor ( comprendido entre 2 y 12 ), el cual se solicita al usuario al inicio del programa.

  Como se parte de un espacio muestral equiprobable, la probabilidad se calcula aplicando directamente la regla/principio de Laplace.

  Para contabilizar el número de casos posibles así como el número de casos favorables ( número de elementos de los CONJUNTOS ) se utiliza la instrucción 'len'

-oOo-
Archivo de texto con el código fuente en el lenguaje de programación Python3: [simulaciondosdados.txt]

Referencias:
  [1] Vacas, J.A.: Curso de Python, YouTube

$\square$