Re: Uno de niños y niñas

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).

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 ...

-- 
Saludos,

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