Re: Uno de niños y niñas

Ignacio Larrosa Cañestro wrote:
> Antonio González wrote:
>> El problema anterior me ha recordado el siguiente problema:
>>
>> ¿De cuantas formas puede ponerse en fila k escolares si las niñas han
>> de ir al menos en grupos de 2?
>>
>> Por ejemplo, para k = 1 hay un caso (un niño), para k = 2 hay dos
>> (dos niños, OO o dos niñas, AA). Para k = 3 hay: OOO, OAA, AAO, AAA.
>>
>> ¿Y para k genérico?
>
> Sea O(n) el número de configuraciones con n 'menudencias' en la que la
> última es un niño, y A(n) el número de ellas en que la última es una
> niña.
> Tenemos que
>
> O(n) = O(n-1) + A(n-1)      (#1)
> A(n) = O(n-2) + A(n-1)      (#2)
>
> Restando #2 - #1 y despejando A(n),
>
> A(n) = O(n) - O(n-1) + O(n-2)      (#3)
>
> Sustituyendo n por n-1 en #3 y sustituyendo A(n-1) en #1,
>
> O(n) = 2O(n-1) - O(n-2) + O(n-3)
>
> Llamando T(n) al total,
>
> T(n) = O(n) + A(n) = O(n+1)
>
> Las tres sucesiones obedecen pues la misma recurrencia, aunque con
> diferentes valores iniciales. Para el total,
>
> T(n) = 2T(n-1) - T(n-2) + T(n-3), T(1) = 1, T(2) = 2, T(3) = 4
>
> Esto da lugar a
>
> T(n): 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897,
> 3329, 5842, 10252, 17991, 31572, 55405, ...
>
> (n = 1, 2, ..., 20, ...)
>
> Dado lo 'impresentables' de las raíces de la ecuación característica,
> cúbica, me niego a intentar hallar una fórmula explícita para T(n).

Lo que si puede hallarse fácilmente es la función generatriz. Considerando 
T(0) = 1 (hay una sola dissposición con 0 niños/as), queda

t(x) = Sum(T(n)x^n, n, 0, inf) = (1 - x + x^2)/(1 - 2x + x^2 - x^3)


-- 
Saludos,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUITARMAYUSCULAS@mundo-r.com


> Nota: El de las salas comunicadas por tres puertas, en el caso de
> edificios de 2*n salas, es parecido pero bastante más simple ...