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?

--

Antonio

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

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

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

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

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

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

Ignacio Larrosa Cañestro wrote:
> 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).

Una cosa curiosa con las raíces de esta ecuación, r^3 -2r^2 + r - 1 = 0, es
que la raíz real parece ser exactamente 1 más el módulo de las complejas.


--
Saludos,

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

Ignacio Larrosa Cañestro wrote:
> 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).

Una cosa curiosa con las raíces de esta ecuación, r^3 -2r^2 + r - 1 = 0, es
que la raíz real parece ser exactamente 1 más el módulo de las complejas.


--
Saludos,

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

Ignacio Larrosa Cañestro wrote:
> 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).

Una cosa curiosa con las raíces de esta ecuación, r^3 -2r^2 + r - 1 = 0, es
que la raíz real parece ser exactamente 1 más el módulo de las complejas.


--
Saludos,

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