Uno de combinatoria

[^Cuervo^]

Un granjero tiene que plantar una hilera de 50 árboles. Para ello dispone de dos clases de árboles, robles y pinos.
La única condición que se le ha impuesto, es que entre dos pinos siempre debe haber almenos un roble, es decir, que no puede plantar dos pinos de forma consecutiva.
Con estas premisas, decidme, de cuantas formas distintas podra nuestro granjero plantar la hilera en cuestión?

[carroza]

Re: Uno de combinatoria

Hola.

No se si habrá una forma más elegante , pero mi resultado es el siguiente:

Primero, utilizo el resultado siguiente: las formas de agrupar m objetos iguales en n grupos
(que pueden tener cero objetos) es ${m+n-1 \choose n-1}$.

Luego, considero los casos siguientes.

No hay pinos. La forma de ponerlos es RRR----RRR (todo robles).
Tengo 50 robles en un grupo: ${50 \choose 0}$ casos.

Hay un pino. La forma de ponerlos es ---P--- (numero arbitrario de robles antes y después del pino)
Tengo 49 robles en dos grupos: ${50 \choose 1}$


Hay dos pinos. La forma de ponerlos es ---PR---P--- (detrás del primer pino hay un roble; aparte de esto, puedo agrupar los 47 robles restantes arbitrariamente)
Tengo 47 robles en tres grupos: ${49 \choose 2}$

Hay tres pinos. ---PR---PR---P---
Tengo 45 robles en 4 grupos: ${48 \choose 3}$


etc.

hasta 25 pinos: Un roble en 26 grupos: ${26 \choose 25}$


El resultado final es la suma de todos estos números combinatorios.

A ver si alguien encuentra una solución más elegante.

[Machinegun]

Re: Uno de combinatoria

Si sólo tuviéramos que plantar 1 árbol, tendríamos 2 posibilidades.

P, R

Si sólo tuviéramos que plantar 2 árboles, tendríamos 3 posibilidades.

PR, RP, RR

Si sólo tuviéramos que plantar 3 árboles, tendríamos 5 posibilidades.

PRP, PRR, RPR, RRP, RRR

Si sólo tuviéramos que plantar 4 árboles, tendríamos 8 posibilidades.

PRPR, PRRP, PRRR, RPRP, RPRR, RRPR, RRRP, RRRR

Si seguimos por este camino, vemos que tenemos una serie de Fibonacci empezando en su cuarto término (el 2), por lo que calculo que el número que estamos buscando corresponde al término 53 de dicha serie. No sé cómo se calcula ese número, pero supongo que vendrá en alguna calculadora o tabla.

Si mi respuesta anda muy descaminada, no hagan caso; pero si no, entonces sí, jeje.

Saludos

Edito sólo para incluir el resultado que obtuve usando una hoja de cálculo: 32951280099.

[carroza]

Re: Uno de combinatoria

Muy elegante, sí señor.

Habría que demostrar, más allá de la evidencia empírica, que efectivamente es una serie de fibonacci:

Si con n árbores hay P casos, y con n-1 arboles hay Q casos, entonces para

n+1 arboles, habría P casos (los grupos de n arboles con un roble añadido) mas Q casos (los grupos de n-1 arboles mas roble y pino).

[Machinegun]

Re: Uno de combinatoria

En una serie de Fibonacci tenemos que si multiplicamos por dos un número fn de la serie y le sumamos el número anterior $(f_{n-1})$, obtenemos otro número de la serie $(f_{n+2})$, es decir:

$2f_n + f_{n-1} = f_{n+2}$

En nuestro caso tenemos que cada R de un paso genera dos posibilidades en elsiguiente caso (P y R) mientras que cada P genera sólo una posibilidad (R). El primer paso es considerar las posibilidades si sólo tuviéramos que plantar 1 árbol; el segundo, si fueran 2, y así sucesivamente. Como en el primer paso tenemos PR en el segundo vamos a tener, por cada P una R y por cada R una P y una R. Es decir, la R produce dos posibilidades para el siguiente paso y la P sólo una. En el primer paso tenemos 2 posibilidades y en el segundo tenemos 3. Como 2 y tres son números consecutivos de la serie, quiere decir que podemos considerar $f_n = 3$ y aplicar la fórmula de arriba para obtener $f_{n+2}$, un número de la serie, a saber, 8.

Espero que esto demuestre que se trata de una serie de Fibonacci; de lo contrario, tendremos que esperar que alguien más refute o confirme la tesis.

Saludos

[Machinegun]

Re: Uno de combinatoria

Creo que encontré una mejor demostración. Sea n el número de árboles a plantar. Para saber cuántas posibilidades hay, sumamos las posibilidades de que sea pino $(P_n)$ más las posibilidades de que sea roble $(R_n)$. Obviamente si el árbol anterior $(A_{n-1})$ es un pino, entonces $P_n = 0$, por lo que las posibilidades de que $A_n$ sea P se reducen a las posibilidades de que $A_{n-1}$ sea R (porque cada R brinda una posibilidad de que el siguiente A sea P, mientras que cada P no brinda ninguna de que el siguiente sea P). Esto lo podemos expresar así:

$P_n = R_{n-1}$ [1]

De la que fácil se desprende

$P_{n+1} = R_n$ [1a]

Ahora bien, como cada P brinda una posibilidad de R para el siguiente A, y cada P también brinda una posibilidad de R para el siguiente A, tenemos que las posibilidades de que $A_n$ sea R es igual a la suma de las posibilidades de que $A_{n-1}$ sea P y de que $A_{n-1}$ sea R, lo que expresamos así:

$R_n = R_{n-1} + P_{n-1}$ [2]

Sustituyendo [1a] en [2] tenemos:

$P_{n+1} = R_{n-1} + P_{n-1}$ [3]

Sustituyendo [1] en [3], llegamos a la definición de número de Fibonacci, a saber:

$P_{n+1} =P_n + P_{n-1}$

Tal vez así, sí queda demostrado más allá de la evidencia empírica.

Saludos

[carroza]

Re: Uno de combinatoria

OK

Queda demostrado; Qué te parece mi demostración de una línea:

Si con n árbores hay P casos, y con n-1 arboles hay Q casos, entonces para

n+1 arboles, habría P casos (los grupos de n arboles con un roble añadido) mas Q casos (los grupos de n-1 arboles mas roble y pino).

[Machinegun]

Re: Uno de combinatoria

Pues parece muy elegante, pero debo confesar que no alcanzo a entenderla (lo que está entre paréntesis no lo capto). Si se trata de una demostración de que el problema sí se ajusta a una serie de Fibonacci, puede que me convenza, aunque tal vez sea porque ya estoy convencido; habría que ver si convence a los no convencidos.

Saludos

[carroza]

Re: Uno de combinatoria

Bueno, voy a probar otra vez:

Para construir hileras de n+1 árboles que cumplan las condiciones descritas, lo puedo hacer de dos maneras:

1) Tomar una hilera de n árboles, y añadir un roble.

2) Tomar una hilera de n-1 árboles, y añadir un roble y un pino.

Todas las posibles soluciones pertenecen a la categoría 1) o a la categoría 2), y no hay ninguna solucuón común a ambas.

Por tanto, las posibles hileras de n+1 árboles son la suma de las posibles hileras de n árboles (caso 1) más las posibles hileras de n-1 árboles (caso 2).

[Machinegun]

Re: Uno de combinatoria

No había entendido que con “grupos de n árboles” te referías a “las posibles hileras de n árboles”. Tal vez mi confusión se debió a que en el primer post usas la palabra “grupo” en otro sentido. Una vez aclarado el punto, creo que tu demostración es válida y elegante. Enhorabuena.