A maior rede de estudos do Brasil

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

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

grupo conteniendo k2
elementos, etc. El i-ésimo grupo corresponde a los factores
de los cuales seleccionamos xi.
Corolario 27 ∑
k1,k2,...,kr≥0
k1+k2+···+kr=n
(
n
k1, k2, . . . , kr−1
)
= rn.
Demostración: En efecto, obtenemos este resultado al tomar
xi = 1, i = 1, . . . , r.
3.5 Ejercicios
64. Demuestre que para todos n y m ∈ N se cumple la iden-
tidad
m∑
k=0
(
n+ k
k
)
=
(
n+m+ 1
m
)
.
65. Demuestre que el número de maneras en que m obje-
tos indistinguibles pueden ser distribuidos en n urnas dis-
tinguibles, quedando todas las urnas ocupadas, es ( m−1m−n).
Sugerencia: emplee la fórmula del problema 64.
3.5. Ejercicios 43
66. Demuestre las siguientes identidades:
(a)
n∑
k=0
k
(
n
k
)
= n 2n−1; n ∈ N.
(b)
n∑
k=0
(−1)kk
(
n
k
)
= 0; n ∈ N.
(c)
n∑
k=0
(
n
k
)2
=
(
2n
n
)
; n ∈ N.
(d)
n∑
k=0
(
n
k
)(
n− k
m− k
)
= 2m
(
n
m
)
; n,m ∈ N, n ≥ m.
(e)
n∑
k=0
(−1)k
(
n
k
)(
n− k
m− k
)
= 0; n,m ∈ N, n ≥ m.
(f)
n−r∑
k=0
(
r + k
k
)
=
(
n+ 1
r + 1
)
; r, n ∈ N, r ≤ n.
(g)
m∑
k=0
(
m
k
) (
n
r + k
)
=
(
m+ n
m+ r
)
; r, n,m ∈ N, r ≤ n.
(h)
m∑
k=0
(
m− k
r
) (
n+ k
s
)
=
(
m+ n+ 1
r + s+ 1
)
; r, s, n,m ∈
N.
67. Evalúe la suma
∑n
k=3(k − 2)(k − 1)k.
Sugerencia: el término (k − 2)(k − 1)k es igual a 3!(k3 ).
68. Evalúe la suma
∑n
k=1 k
2.
Sugerencia: k2 = (k − 1)k + k.
69. Utilice la identidad(
n
k
)
− 1 =
(
n− 1
k
)
+
(
n− 2
k − 1
)
+ · · ·+
(
n− k
1
)
44 Caṕıtulo 3. Coeficientes binomiales y multinomiales
para demostrar que, para cualquier k ≥ 1 dado, todo entero
positivo n puede ser representado de manera única como
n =
(
m1
1
)
+
(
m2
2
)
+ · · ·+
(
mk
k
)
,
donde 0 ≤ m1 < m2 < · · · < mk.
70. Demuestre, mediante un argumento combinatorio, que
(a)
(
2n
2
)
= 2
(
n
2
)
+ n2.
(b) (n− r)
(
n+ r − 1
r
)(
n
r
)
= n
(
n+ r − 1
2r
)(
2r
r
)
.
71. Demuestre que
(
n
1
)
+ 6
(
n
2
)
+ 6
(
n
3
)
= n3.
72. Evalúe las sumas
(a) 13 + 23 + · · ·+ n3 (b)
n∑
k=1
12(k + 1)k(k − 1)
(c)
n∑
k=0
(2 + 3k)2 (d)
n∑
k=0
k(n− k)
73. Evalúe la suma
1 + 2
(
n
1
)
+ · · ·+ (k + 1)
(
n
k
)
+ · · ·+ (n+ 1)
(
n
n
)
separándola en dos sumandos cuya suma es una identidad
conocida.
74. Dándole valores apropiados a x en la expansión binomial
3.5. Ejercicios 45
o en alguna de sus variantes, evalúe las siguientes sumas:
(a)
n∑
k=1
(−1)k k
(
n
k
)
(e)
n∑
k=1
(−1)k k2
(
n
k
)
(b)
n∑
k=2
k(k − 1)
(
n
k
)
(f)
n∑
k=0
1
k + 1
(
n
k
)
(c)
n∑
k=0
2k
(
n
k
)
(g)
n∑
k=0
(2k + 1)
(
n
k
)
(d)
n∑
k=1
k3k
(
n
k
)
75. Muestre que
n∑
k=m
(
k
r
)
=
(
n+ 1
r + 1
)
−
(
m
r + 1
)
.
76. Muestre que
m∑
k=1
(
m+ k − 1
k
)
=
m∑
k=1
(
n+ k − 1
k
)
.
77. Muestre que
n−1∑
k=0
[m+ k]m =
[m+ n]m+1
m+ 1
.
78. Muestre que
{ n∑
k=0
(
n
k
)}2
=
2n∑
k=0
(
2n
k
)
.
79. Encuentre el valor de k que maximiza las cantidades
siguientes:
(a)
(
n
k
)
(b)
(
2n+ k
n
)(
2n− k
n
)
80. Evalúe
n−1∑
k=0
(
n
k
)(
n
k + 1
)
.
46 Caṕıtulo 3. Coeficientes binomiales y multinomiales
81. Demuestre que(
n
1
)
+3
(
n
3
)
+5
(
n
5
)
+ · · · = 2
(
n
2
)
+4
(
n
4
)
+ · · · = n2n−2.
82. Evalúe
(
n
0
)
−2
(
n
1
)
+3
(
n
3
)
+ · · ·+(−1)n(n+1)
(
n
n
)
.
83. Muestre que
n∑
k=0
(2n)!
(k!)2((n− k)!)2
=
(
2n
n
)2
.
84. Evalúe
n/2∑
k=0
22k2k
(
n
2k
)
, para n par.
85. Muestre que
(a) (−1)n
(
−n
k − 1
)
= (−1)k
(
−k
n− 1
)
.
(b) (−1)n
(
−12
n
)
22n =
(
2n
n
)
.
(c) − 2
n
(
2n− 2
n− 1
)
= (−1)n
( 1
2
n
)
22n.
(d)
m∑
k=0
[m]k
[n]k
=
1
( nm)
m∑
k=0
(
n− k
n−m
)
=
n+ 1
n−m+ 1
, para m ≤
n.
86. Para cada n ∈ N definimos los números de Catalan, C2n,
mediante C2n = 1n+1(
2n
n ). Demuestre la siguiente relación
por recurrencia:
C2m =
m∑
k=1
C2k−2C2m−2k.
Caṕıtulo 4
Particiones de un conjunto
4.1 Números de Stirling de 2da especie
¿Cuántas particiones pueden hacerse del conjunto de 4 ele-
mentos {1, 2, 3, 4} en 2 clases? La respuesta es: siete en total.
Ellas son:
{1}|{2, 3, 4} {2}|{1, 3, 4} {3}|{1, 2, 4} {4}|{1, 2, 3}
{1, 2}|{3, 4} {1, 3}|{2, 4} {1, 4}|{2, 3}
Obsérvese que el orden entre las clases no interesa cuando
se habla de particiones. Aśı por ejemplo, son iguales las par-
ticiones {1, 2}|{3, 4} y {3, 4}|{1, 2}. El número de particiones
de un conjunto es dif́ıcil de calcular. En general, tenemos la
siguiente definición:
Definición 28 El número de particiones de un conjunto de
n elementos en k clases, con 1 ≤ k ≤ n, se denota por S kn . A
los números S kn se les llama números de Stirling
1 de segunda
especie.
1James Stirling (1692–1770) Matemático escocés, nacido en Gar-
den (cerca de Stirling). Estudió en la Universidad de Oxford y trabajó
por un corto peŕıodo en las universidades italianas de Venecia (1719) y
de Padua (1721), trasladándose en 1722 a Glasgow y posteriormente a
Londres en 1725. Fue miembro de la Sociedad Real de Londres (1729).
Su principal obra matemática es “El método de diferencias”, publi-
cado en 1730. Este libro es un tratado sobre series infinitas, métodos de
sumación, interpolación y cuadratura numérica. En él, Stirling obtiene
47
48 Caṕıtulo 4. Particiones de un conjunto
Es fácil deducir que, si k ≤ n, el número de Stirling S kn
coincide con el número de distintas maneras en que pueden
disponerse n objetos distinguibles en k cajas idénticas, no
permitiendo que ninguna caja quede vaćıa (si permitimos
que queden cajas vaćıas, entonces el número de maneras será
igual a S 1n + S
2
n + · · ·+ S kn , como puede el lector observar).
Es sencillo establecer relaciones por recurrencia que per-
mitan el rápido cálculo de los números de Stirling de segunda
especie.
Proposición 29 Los números de Stirling de segunda especie
S kn satisfacen las siguientes relaciones por recurrencia:
S kn+1 = S
k−1
n + kS
k
n , para 1 < k < n,
S 1n = S
n
n = 1.
Demostración: En efecto, considérese la tabla de todas las
particiones de n+ 1 objetos en k clases. En esta tabla pode-
mos distinguir entre dos tipos de particiones:
(i) Para algunas de estas particiones, el objeto número n+
1 conforma una clase unitaria. Claramente el número
de tales particiones es S k−1n .
(ii) Para el resto de las otras particiones, el objeto número
n + 1 se encuentra ubicado en una clase no unitaria.
Claramente el número de estas otras particiones es kS kn
(el objeto número n+1 puede quedar en cualquiera de
por primera vez un desarrollo asintótico para el logaritmo de la función
Gamma (serie de Stirling). Además estudia algunos productos infinitos,
aśı como ciertas propiedades de las funciones hipergeométricas y de la
función Beta. Su famosa fórmula de aproximación para n! aparece en
esta obra.
En 1736 retornó a Escocia donde trabajó como gerente de la Compañ́ıa
Minera Escocesa. En 1746 fue electo miembro de la Real Academia de
Berĺın. En el mismo año Maclaurin murió y Stirling fue llamado a
ocupar su plaza en la Universidad de Edimburgo, pero decidió declinar
la oferta.
4.1. Números de Stirling de segunda especie 49
las k clases en las cuales se particionan los primeros n
objetos).
Esto demuestra la relación por recurrencia S kn+1 = S
k−1
n +
kS kn . Los casos extremos S
1
n = S
n
n = 1 son evidentes.
A partir de estas recurrencias pueden calcularse fácilmen-
te los primeros números de Stirling de segunda especie, como
se exhiben en la Figura 4.1, en la llamada matriz de Stirling
de segunda especie.
S kn k = 1 2 3 4 5 6
n = 1 1 0 0 0 0 0
2 1 1 0 0 0 0
3 1 3 1 0 0 0
4 1 7 6 1 0 0
5 1 15 25 10 1 0
6 1 31 90 65 15 1
...
...
...
...
...
...
...
Figura 4.1: Primeros números de Stirling de segunda especie.
Proposición 30 El número de funciones sobreyectivas que
pueden construirse entre un conjunto X de n elementos y un
conjunto A de k elementos, con n ≥ k, es igual a k!S kn .
Demostración: En efecto, cada función sobreyectiva f de
X = {1, 2, . . . , n} en A = {a1, a2, . . . , ak} induce una única
partición de X en k clases

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