División de Polígonos

Un granjero tiene una tierra de determinadas dimensiones con forma de un polígono convexo de n-lados. Quiere saber de cuántas maneras diferentes puede dividir su tierra en parcelas triangulares utilizando, para unir los vértices, separaciones diagonales.

Definimos entonces E_n como el número de posibilidades de división o parcelamiento de la tierra del granjero. Tenemos entonces las siguientes situaciones:

E_3 = 1 en este caso tenemos un terreno con forma de triángulo.

E_4 = 2 sería el caso de un cuadrilátero divisible de la siguiente forma:

E_5 = 5 las cinco divisiones posibles serían de la siguiente forma:

Así, se pueden ir determinando los próximos valores de la serie:

E_6 = 14

E_7 = 42

E_8 = 132

Considerando el caso general, según la siguiente ilustración tenemos que:

Uniendo los vértices n, 1 y r, se obtiene el triángulo n1r con dos polígonos más pequeños a cada lado de este, existen entonces dos casos a considerar:

Caso 1: 3\leq r \leq n-2 en este caso tenemos por un lado un polígono de  r -lados y por el otro un polígono de (n-r+1)-lados.

Caso 2: r=2 o r=n-1 aquí obtenemos un triángulo y un polígono de (n-1)-lados.

Definimos E_2 = 1, entonces al contar el número total de divisiones cuando r varía, tenemos la siguiente relación recursiva o recurrente:

E_n = E_2\times E_{n-1} + E_3\times E_{n-2} +...+ E_r\times E_{n-r+1}+...+ E_{n-2}\times E_3 + E_{n-1}\times E_2.

Referencia:

# Catalan Numbers – Isaac Vun and Paul Belcher – Mathematical Spectrum Volume 30  Number 1 (1997/1998) pp 3-5.

(Entrada propuesta para la VII edición del Carnaval de Matemáticas organizado por el blog El Máquina de Turing).

About these ads

Una respuesta

  1. Está buenísimo contar :D Los números de Catalán aparecen por todos lados…

    Saludos, Diego.

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 28 seguidores

%d personas les gusta esto: