A maior rede de estudos do Brasil

Grátis
179 pág.
Análise combinatória matemática

Pré-visualização | Página 11 de 30

diferentes: f−1({a1}), f−1({a2}),
. . . , f−1({ak}). Por el contrario, a cada partición de X en
k clases están asociadas k! diferentes funciones sobreyectivas
de X en A.
Por ejemplo, el número de funciones sobreyectivas que
pueden definirse del conjunto {1, 2, 3, 4} en el conjunto {a, b}
50 Caṕıtulo 4. Particiones de un conjunto
es igual a 2!S 24 = 14. Para enumerarlas, empleamos por
ejemplo la notación (a, b, b, a) para referirse a la función f
tal que
f(1) = a , f(2) = b , f(3) = b , f(4) = a.
Luego, las 14 funciones sobreyectivas son:
(a, a, a, b), (a, a, b, a), (a, b, a, a), (b, a, a, a), (a, a, b, b),
(a, b, a, b), (b, a, a, b), (a, b, b, a), (a, b, b, a), (b, b, a, a),
(a, b, b, b), (b, a, b, b), (b, b, a, b), (b, b, b, a).
Proposición 31 Sean n y m enteros positivos. Entonces,
mn =
m∑
k=1
(
m
k
)
(k!S kn ). (4.1)
Demostración: En efecto, considérese los conjuntos X y A
de n y m elementos respectivamente. La cantidad mn de la
parte izquierda de la fórmula coincide con el número total
de funciones que pueden definirse de X en A. Este número
total de funciones puede desglosarse de la siguiente manera:
(i) Las funciones cuya imagen consiste en exactamente 1
elemento de A: hay exactamente m = (m1 )(1!S
1
n ) fun-
ciones con esta caracteŕıstica.
(ii) Las funciones cuya imagen consiste en exactamente 2
elementos de A: hay en total (m2 ) subconjuntos de A
con 2 elementos y para cada uno de ellos existen 2!S 2n
distintas funciones (sobreyectivas) de X en tal subcon-
junto. Luego, en total habrá exactamente (m2 )(2!S
2
n )
funciones con esta caracteŕıstica.
(iii) En general, las funciones cuya imagen consiste en ex-
actamente k elementos de A (con 1 ≤ k ≤ m): hay en
total (mk ) subconjuntos de A con k elementos y para
4.1. Números de Stirling de segunda especie 51
cada uno de ellos existen k!S kn distintas funciones (so-
breyectivas) de X en tal subconjunto. Luego, en total
habrá (mk )(k!S
k
n ) funciones con esta caracteŕıstica.
Sumando las cantidades anteriores, desde k = 1 hasta k = m
obtenemos la fórmula de la proposición.
Recuérdese que los números de Stirling de primera es-
pecie, s kn , se caracterizan precisamente por ser los coeficientes
de los polinomios de Stirling de primera especie: [x]n =
x(x − 1) · · · (x − n + 1) =
∑n
k=1 s
k
n x
k. Veamos la relación
inversa, que involucra a los números de Stirling de segunda
especie.
Proposición 32 Sea x un número real. Entonces,
xn =
n∑
k=1
S kn [x]k. (4.2)
Demostración: En efecto, obsérvese primero que el térmi-
no k-ésimo de la sumatoria de la parte derecha de (4.2),
S kn [x]k, simplifica de la siguiente forma:
S kn [x]k = k!S
k
n
[x]k
k!
=
(
x
k
)
(k!S kn ).
La fórmula (4.2) es una identidad de polinomios de grado n
en la variable x. En virtud de la proposición 31, la fórmula
(4.2) se cumple para los n + 1 distintos valores 0, 1, . . . , n
de la variable x. Se concluye que ambos polinomios de la
fórmula (4.2) son iguales, para todo x ∈ R.
A continuación se estudia otra relación por recurrencia
para el cálculo de los números de Stirling de segunda especie.
Proposición 33 Para m ≥ 1, n ≥ 0, m ≤ n+ 1 se cumple:
S mn+1 =
n∑
k=m−1
(
n
k
)
S m−1k .
52 Caṕıtulo 4. Particiones de un conjunto
Demostración: En efecto, considérese la tabla de todas las
particiones del conjunto X = {1, 2, . . . , n, n + 1} de n + 1
objetos en m clases. En cada una de las particiones de esta
tabla, elimı́nese la clase que contiene al objeto n + 1. De
esta manera, obtenemos todas las particiones de un conjunto
K ⊆ {1, 2, . . . , n} en m − 1 clases, para cada selección de
K. Cada uno de estos conjuntos K tendrá m− 1 elementos
como mı́nimo. Debido a que existen (nk ) subconjuntos K ⊆
{1, 2, . . . , n} con k elementos, y para uno de ellos habrá en
total S m−1k particiones en m−1 clases, se obtiene la fórmula
propuesta.
4.2 Los números de Bell
Los números de Stirling de segunda especie, S kn , coinciden
con el número de particiones de un conjunto X de n ele-
mentos en k clases no vaćıas. Consideremos ahora el número
total de particiones de X en cualquier número de clases no
vaćıas. Denotemos por Bn este número total de particiones
de X de n elementos. Estos números también son llamados
números exponenciales o números de Bell2.
2Eric Temple Bell (1883–1960) Matemático escocés, nacido en Ab-
erdeen. Vivió y creció en Escocia hasta 1903, año en que se trasladó a
vivir a Estados Unidos. Recibió su doctorado de la Universidad de
Columbia en 1912 por la disertación The Cyclotomic Quinary Quintic,
siendo Cole su tutor. Enseñó matemáticas en la Universidad de Wash-
ington desde 1912 hasta 1926, cuando obtuvo una plaza permanente en
el Instituto de Tecnoloǵıa de California.
Escribió algunos libros muy populares sobre la historia de las
matemáticas. También hizo contribuciones a la teoŕıa anaĺıtica de los
números, el análisis diofantino y las funciones numéricas. La Sociedad
Matemática Americana le concedió el premio Bôcher en 1924 por su
memoria Paráfrasis Aritméticas, que apareció en la revista Transaction
of the American Mathematical Society en 1921. A pesar que escribió
cerca de 250 art́ıculos —incluyendo aquel por el que recibiera el premio
Bôcher— Bell es mejor recordado por sus libros y por consiguiente como
un historiador de las matemáticas.
4.2. Los números de Bell 53
Por ejemplo, si X = {a, b, c, d}, el número total de parti-
ciones de X es igual a 15 = B4. Estas 15 particiones son:
{a, b, c, d} {a}|{b, c, d} {b}|{a, c, d} {c}|{a, b, d}
{d}|{a, b, c} {a, b}|{c, d} {a, c}|{b, d} {a, d}|{b, c}
{a}|{b}|{c, d} {a}|{c}|{b, d} {a}|{d}|{b, c} {b}|{c}|{a, d}
{b}|{d}|{a, c} {c}|{d}|{a, b} {a}|{b}|{c}|{d}
Del significado de los números de Stirling de segunda
especie, claramente obtenemos la siguiente fórmula para el
cálculo de Bn:
Bn = S 1n + S
2
n + · · ·+ S nn . (4.3)
Por otra parte, Bn coincide también el número de rela-
ciones de equivalencia que pueden definirse en un conjunto X
de n elementos, en virtud de la asociación biuńıvoca existente
entre una relación de equivalencia sobre X y una partición
de X.
A continuación se estudia una relación por recurrencia
para el cálculo de los números de Bell.
Proposición 34 Escribiendo B0 = 1 obtenemos, para todo
n ∈ N,
Bn+1 =
n∑
k=0
(
n
k
)
Bk.
Sus libros Aritmética Algebraica (1927) y El Desarrollo de las
Matemáticas (1940) se convirtieron en clásicos. Otros de sus libros son El
Hombre de las Matemáticas (1937) y Matemáticas, Reinas y Sirvientes
de la Ciencias (1951). Su estilo era claro y exuberante y sus opiniones las
expresaba con vehemencia, acompañadas frecuentemente con algún hu-
mor y un poco de suave malicia. De sus obras obtenemos una visión muy
interesante de las matemáticas, como sublimes actividades perseguidas
por intelecto humano, a menudo falibles, aunque siempre comprometidas
ante la búsqueda perpetua de la verdad matemática. Cultivó también
el genero de la ciencia ficción, escribiendo bajo el seudónimo de John
Taine.
54 Caṕıtulo 4. Particiones de un conjunto
Demostración: En efecto, escribiendo Smn = 0 param > n,
la fórmula 4.3 queda entonces como Bn+1 =
∑∞
m=1 S
m
n+1.
Aplicamos la relación por recurrencia de la proposición 33
para el cálculo de Smn+1 y obtenemos el resultado:
Bn+1 =
∞∑
m=1
Smn+1 =
∞∑
m=1
n∑
k=0
(
n
k
)
Sm−1k
=
n∑
k=0
(
n
k
)( ∞∑
m=1
Sm−1k
)
=
n∑
k=0
(
n
k
)
Bk.
Dos belĺısimos desarrollos asintóticos que involucran a los
números de Bell se presentan a continuación.
Proposición 35 (Bell) Para todo t ∈ R se cumple la relación
∞∑
n=0
Bn
n!
tn = e(e
t−1).
Demostración: La siguiente prueba, elemental y elegante,
es debida a Rota3. Considere el espacio vectorial de las fun-
3Gian-Carlo Rota (1932–1999) Matemático y filósofo italiano,
nacido en Vigevano, hijo de una prominente familia antifascista que tuvo
que huir precipitadamente de Italia por la persecución emprendida por

Crie agora seu perfil grátis para visualizar sem restrições.