{x2, x3}{x1} poniendo a x1 mismo En general, sea S n, r número de formas en que un conjunto de tamaño n se puede particionar en r subconjuntos...

{x2, x3}{x1} poniendo a x1 mismo

En general, sea

S n, r número de formas en que un conjunto de tamaño
n se puede particionar en r subconjuntos

Entonces, por la ecuación anterior, S3.2 3. Los números S n, r se llaman números de
Stirling de segunda clase.

Nota Los números de
Stirling de primera clase
se utilizan para contar
r-permutaciones con varias
propiedades.


9.5 Conteo de subconjuntos de un conjunto: combinaciones 579

Ejemplo 9.5.12 Valores de los números de Stirling

Determine S 4, 1, S 4, 2, S 4, 3 y S 4, 4.

Solución Dado un conjunto con cuatro elementos, se denotan por {x1, x2, x3, x4}. El número
de Stirling S 4, 1 1 debido a un conjunto de cuatro elementos se puede particionar en un
subconjunto de una sola forma:

{x1, x2, x3, x4}.
Similarmente, S 4, 4 1 ya que hay sólo una manera de particionar un conjunto de cuatro
elementos en cuatro subconjuntos:

{x1}{x2}{x3}{x4}.
El número S 4, 2 7. La razón es que cualquier partición de {x1, x2, x3, x4} en dos
subconjuntos debe consistir en cualquiera de los dos subconjuntos de tamaño dos o de
un subconjunto tener tamaño tres y un subconjunto de tamaño uno. Las particiones para
las cuales ambos conjuntos tienen tamaño dos deben emparejar con x1 con x2, con x3 o con
x4, lo que da lugar a estas tres particiones:

x1 x2 x3 x4 x2 asociado con x1

asociado con x1

asociado con x1

x1 x3 x2 x4 x3

x1 x4 x2 x3 x4

Las particiones para un subconjunto tienen tamaño uno y el otro tiene tamaño tres pueden
tener cualquiera de los cuatro elementos en el subconjunto de tamaño uno, lo que conduce
a estas cuatro particiones:

x1 x2 x3 x4 x1 por sí mismo

x2 x1 x3 x4 x2 por sí mismo

x3 x1 x2 x4 x3 por sí mismo

x4 x1 x2 x3 x4 por sí mismo

Por lo que se deduce que el número total de maneras que el conjunto {x1, x2, x3, x4} se
puede particionar en dos subconjuntos es 3 4 7.
Por último, S4,3 6 porque cualquier particición de un conjunto de cuatro elementos en
tres subconjuntos debe tener dos elementos en un subconjunto y los otros dos elementos
en subconjuntos por ellos mismos. Hay
(4

2

)
= 6 maneras de elegir los dos elementos que

se ponen juntos, lo que resulta en las siguientes seis posibles particiones:



x1 x2 x3 x4 x2 x3 x1 x4

x1 x3 x2 x4 x2 x4 x1 x3

x1 x4 x2 x3 x3 x4 x1 x2

Ejemplo 9.5.13 Determinación de una relación de recurrencia de Sn. r

Determine una relación de recurrencia Sn,r para valores de la sucesión con índices bajo n
y r y que dan las condiciones para la recursión.

Solución Para resolver este problema de forma recursiva, supongamos que ha encontrado un
procedimiento para contar el número de formas de dividir un conjunto de n ฀ 1 elementos
en r ฀ 1 subconjuntos y el número de formas para particionar un conjunto de n ฀ 1 ele-
mentos en r subconjuntos. Las particiones de un conjunto de n elementos {x1, x2,…, xn} en
r subconjuntos se puede dividir, como se muestra en la figura 9.5.8 en la siguiente página,
en los que contienen al conjunto {xn} y los que no.
Para obtener el resultado que se muestra en la figura 9.5.8 primero se cuenta el número
de particiones de {x1, x2,…, xn} en r subconjuntos, donde uno de los subconjuntos es {xn}.
Para hacer esto, imagine cualquiera de las Sn ฀ 1, r ฀ 1 particiones de {x1, x2,…, xn฀1 } en

580 Capítulo 9 Conteo y probabilidad

Particiones de {x1, x2, . . . , xn}en r subconjuntos

Particiones de {x1, x2,…, xn}
en r subconjuntos donde uno de
los subconjuntos es {xn}

Particiones de {x1, x2,…, xn}
en r subconjuntos donde ninguno
de los subconjuntos es {xn}

Estas son particiones
que incluyen a

Sn–1, r–1
{xn}.

Estas son particiones
que no incluyen a

rSn–1, r
{xn}.

Así el número total de particiones de
en r subconjuntos
es
{x1, x2 , . . . , xn}

Sn–1, r–1 + rSn–1, r .

Figura 9.5.8

r ฀ 1 subconjuntos y sumar el subconjunto {xn} a la partición. Por ejemplo, si n 4 y r 3,
que podría adoptar una de las tres particiones de {x1, x2, x3} en dos subconjuntos, a saber:

x1 x2 x3 x1 x3 x2 o x2 x3 x1

y sumando {x4}. El resultado sería una de las particiones

x1 x2 x3 x4 x1 x3 x3 x4 o x2 x3 x1 x4

Claramente, cualquier partición de {x1, x2,…, xn} en r subconjuntos con {xn} como uno
de los subconjuntos puede obtenerse de esta manera. Por tanto Sn฀1, r฀1 es el número de
particiones de {x1, x2,…, xn} en r subconjuntos, de los cuales uno es {xn}.
A continuación, cuente el número de particiones de {x1, x2,…, xn} en r subconjuntos
donde {xn} no es uno de los subconjuntos de la partición. Imagine que alguna de las Sn฀1,r
particiones de {x1, x2,…, xn฀1} en r subconjuntos. Ahora imagine elegir uno de los r subcon-
juntos de la partición y sumar en el elemento xn. El resultado es una partición de {x1, x2,…,
xn} en r subconjuntos de ninguno de los cuales es el subconjunto con un elemento {xn}. Ya
que el elemento xn podría sumarse cualquiera de los r subconjuntos de la partición, se deduce
de la regla de multiplicación que existen rSn฀1,r particiones de este tipo. Por ejemplo, si
n 4 y r 3, podría tomar la (única) partición de (x1, x2, x3} en tres subconjuntos, es decir
{x1}{x2}{x3} y sumar x4 a uno de estos conjuntos. El resultado sería una de las particiones

x1 x4 x2 x3 x1 x2 x4 x3 o x1 x2 x3 x4

x4 se suma a x1 x4 se suma a x2 x4 se suma a x3

Claramente, cualquier partición de {x1, x2,…, xn} en r subconjuntos, ninguno de los cua-
les es {xn}, puede obtenerse en la forma descrita anteriormente, para cuando se remueve
xn de cualquier subconjunto que lo contiene en una partición, el resultado es una partición
de {x1, x2,…, xn฀1} en r subconjuntos. Por tanto rSn฀1,r es el número de particiones de
{x1, x2,…, xn} que no contienen a {xn}.
Ya que cualquier partición de {x1, x2,…, xn} contiene {xn} o no,

el número de particiones
de x1 x2 xn

en r subconjuntos

el número de particiones de
x1 x2 xn en r subconjuntos

xnde los cuales es uno

el número de particiones de
x1 x2 xn en r subconjuntos

ninguno de los cuales es xn


9.5 Conteo de subconjuntos de un conjunto: combinaciones 581

Así
Sn,r = Sn−1,r−1 + r Sn−1,r

para todos los enteros n y r con 1 r n.
Las condiciones iniciales para la relación de recurrencia son

Sn 1 1 y Sn n 1 para todos los enteros n 1

ya que sólo hay una forma de particionar {x1, x2,…, xn} en un subconjunto, a saber:

{x1, x2, . . . , xn}.
y sólo una forma de particionar {x1, x2,…, xn} en n subconjuntos, a saber:

{x1}, {x2}, . . . , {xn}.

Autoexamen
1. El número de subconjuntos de tamaño r que se puede formar a

partir de un conjunto con n elementos se denota por , que
se lee como “ ”.

2. El número de r-combinaciones de un conjunto de n elementos es
.

3. Dos selecciones no ordenadas se dicen que son iguales si los ele-
mentos elegidos son los mismos, independientemente del .

4. Una fórmula que relaciona a
(

n
r

)
y P(n, r) es .

5. La frase “al menos n” significa y la frase “a lo más n”
significa .

6. Supongamos que una colección consiste de n objetos de los cuales,
para cada i con 1 i k, ni son del tipo i y son no distinguibles
entre sí. Suponga también que n n1 n2 . . . nk. Entonces
el número de permutaciones distintas de n objetos es .

7. El número de Stirling de segunda clase, Sn, r, se puede interpretar
como .