Problema de combinatoria

Sea S   1, 2,

, k  . Queremos hallar el número de secuencias de longitud n (formadas por los

elementos de S) pero donde sólo uno de los elementos de S puede aparecer repetido en la secuencia.
Por ejemplo, si S   1, 2, 3 y n  5 las secuencias 11213 ó 12222 son válidas, pero 12123 no lo es.
Hallar una fórmula para calcular ese número de formas.

En primer lugar, quiero establecerque el problema tiene interés si el cardinal de S es S  2
(es decir, que S tiene al menos 2 elementos). Si S  1 , para una secuencia de longitud fija n sólo
es posible una única secuencia; del mismo modo, podríamos plantear la situación de que S fuera
el conjunto vacío

S

 0  , para la cual el número de secuencias es evidentemente nulo.

También conviene señalar que, si la longitudde la secuencia es n = 1, el problema planteado
también es trivial y carente de interés, incluso podríamos decir que carece de sentido, puesto que
en tal caso no hay repetición posible de elementos (para que tal circunstancia se dé, ha de ser
como mínimo n = 2); para no dejar fuera ninguna posibilidad, por trivial que pueda parecer,
diremos que en tal caso, como podemos elegir un elemento de kformas para formar una
secuencia de longitud n = 1, el número de secuencias es N = k.
Considerados dichos casos triviales y carentes de interés (salvo por tener consideradas todas
las posibilidades), pasamos a estudiar qué sucede cuando podemos tener secuencias con posibles
repeticiones de elementos, y estamos interesados en encontrar aquellas en que sólo uno de los
elementos puede aparecerrepetido; no podemos olvidar que la condición solicitada es que puede
aparecer un elemento repetido, no siendo obligatorio que esto suceda. Si la longitud (n) de la
secuencia es menor o igual que el cardinal (k) de S, podrá haber secuencias sin repetición de
elementos, válidas para el recuento que hemos de realizar; sin embargo, si n > k, necesariamente
aparecerán elementos repetidos en lasecuencia, y para el recuento sólo podremos considerar
aquellas en que aparezca un único elemento repetido.
El estudio del número de secuencias es diferente dependiendo de si se verifica 2 ≤ n ≤ k o
alternativamente 2 ≤ k < n. Consideraremos cada una de las posibilidades por separado.

• Caso 2 ≤ n ≤ k
Dado que si se tiene n ≤ k puede suceder que no haya elementos repetidos en la secuencia, elplanteamiento empieza por separar las secuencias válidas en dos grupos mutuamente exclu yentes:
a) Aquellas secuencias que no tengan elementos repetidos; el número N1 de tales secuencias
de longitud n que podremos formar con k elementos corresponde a las variaciones sin
repetición V  k , n  , que podemos expresar en términos de números combinatorios como:

k 
N1  V  k , n      n!
n
b) Aquellas secuencias que tengan un único elemento repetido; el número de tales secuencias
de longitud n que podremos formar corresponderá con las que obtendremos a partir de los
elementos que integran dos subconjuntos, el del elemento que se repite y el de los
restantes elementos. Elegido el elemento que se repite (que lo hace i veces en la
secuencia), nos quedan k  1 elementos delos cuales seleccionamos n  i elementos
ordenados; una vez definida la subsecuencia de elementos no repetidos, sólo resta colocar
los i elementos repetidos, teniendo n  i  1 posiciones posibles, con lo cual el problema es
equivalente al de repartir i bolas idénticas en n  i  1 cajas. Por lo tanto, una vez hayamos
elegido un elemento determinado de S   1, 2,

, k  , de acuerdo con elprincipio

multiplicativo, el número de secuencias con ese elemento repetido i veces sería:

 i  (n  i  1)  1
 n   k  1


  V  k  1, n  i   

  (n  i)! (*)
 (n  i  1)  1 
ni ni

 n   k  1
1
 
  (n  i)!
i  ni


Como el número de veces que se repite el elemento tiene un valor mínimo i  2 (si aparece repetido, por lo menos...