PDF de programación - Combinatoria

Imágen de pdf Combinatoria

Combinatoriagráfica de visualizaciones

Actualizado el 18 de Octubre del 2017 (Publicado el 9 de Julio del 2017)
1.273 visualizaciones desde el 9 de Julio del 2017
3,5 MB
138 paginas
Creado hace 3a (22/07/2016)
Combinatoria



Edición 2016

Colección Hojamat.es

© Antonio Roldán Martínez

http://www.hojamat.es

1







P R E S E N T AC I Ó N



No es fácil la Combinatoria. Por eso, la hoja de cálculo, los conteos
ordenados y las simulaciones ayudan mucho a su comprensión. En
este documento hemos omitido los aspectos teóricos, breves y muy
conocidos, prefiriendo en su lugar la resolución de problemas y
cuestiones.



Los problemas combinatorios
requieren
planteamientos ordenados y mucha atención para resolverlos. Suelen
admitir varios planteamientos, lo que refuerza la certeza de haberlos
resuelto bien.

resultan difíciles, y

En esta edición se han añadido los temas Función parking y Rachas de
dígitos.

Como advertiremos en todos los documentos de esta colección, el
material presentado no contiene desarrollos sistemáticos, ni pretende
ser un manual teórico. En cada tema se incluirán cuestiones curiosas o
relacionadas con las hojas de cálculo, con la única pretensión de
explicar algunos conceptos de forma amena.



2





T A B L A D E C O N T E N I D O



Presentación ..................................................................................................2

Problemas ......................................................................................................5

Combinado de murciélago ..........................................................................5

Coloreando el tablero .................................................................................6

Sumas generadas con tres cifras ...............................................................6

Fronteras en un tablero ..............................................................................7

Combinatoria con comprobación ............................................................. 11

Teoría y curiosidades ................................................................................ 13

Frobenius y los Mcnuggets ...................................................................... 13

Multicombinatorios ................................................................................... 17

Una concurrencia ..................................................................................... 18

Subfactoriales .......................................................................................... 20

Jugamos con Sidon y Golomb ................................................................. 22

Identidad del hexágono ........................................................................... 26

Chica, chico, chica ................................................................................... 26

Suma de los elementos de todos los subconjuntos ................................ 27

Función “parking” ..................................................................................... 30

Rachas de dígitos .................................................................................... 33

Profundizaciones ....................................................................................... 40

Montones de piezas ................................................................................. 40

Collares bicolores .................................................................................... 45

Lo tengo repe ........................................................................................... 53

Números digitalmente equilibrados ......................................................... 62

Permutaciones y ciclos ............................................................................. 76

Permutaciones obtenidas por simulación ................................................ 76

Grupo simétrico ....................................................................................... 82

Descomposición en ciclos ....................................................................... 85

Números de Stirling de primera especie. ................................................ 90

3





Funciones generatrices ............................................................................. 94

Un ejemplo introductorio .......................................................................... 94

La teoría ................................................................................................... 97

Combinaciones y variaciones ................................................................ 104

Particiones y funciones generatrices ..................................................... 109

Particiones con sumandos restringidos ................................................. 115

Ideas para el aula ..................................................................................... 121

Historias de un tanteo ............................................................................ 121

Soluciones ................................................................................................ 126

Problemas .............................................................................................. 126

Profundizaciones ................................................................................... 133

Ideas para el aula .................................................................................. 134

Apéndice ................................................................................................... 136



4





P R O B L E M AS



C O MB I N A D O D E M U R C I É L A G O



La palabra MURCIELAGO ha sido usada tradicionalmente para la
codificación en pequeños comercios, por tener diez letras distintas (5
vocales y 5 consonantes) que se pueden usar para representar las
cifras de 0 a 9 en una asignación decidida por cada comerciante: M=0,
C=1, E=2, etc.

Sobre ella se pueden plantear muchos problemas de distintos niveles.
Aquí hemos elegido tres:

(a) ¿De cuántas
letras de
MURCIELAGO, de forma que no caigan todas las vocales seguidas?
(Se prohíben permutaciones como MRCOAEIULG)

formas se pueden ordenar

las

(b) ¿Y si deseamos que nunca aparezcan vocales consecutivas,
aunque sólo sean dos? (Deseamos que todas estén separadas)

(c) ¿Y si, por el contrario, deben estar las cinco vocales consecutivas y
en su orden natural?

Se pueden inventar más, pero la Combinatoria cansa mucho.



5







C O L O R E A N D O E L T A B L E R O



¿De cuántas formas se puede
colorear un tablero de ajedrez
usando sólo los colores Blanco y
Negro, de
forma que cada
cuadrado del mismo, de dos
casillas de lado, contenga dos de
ellas coloreadas en blanco y las
otras dos en negro?

Para encontrar la solución puedes considerar las formas de rellenar de
color la primera fila y cómo influye su contenido en las demás filas de
más abajo, cumpliéndose la condición de que cada cuadrado de 2 por
2 contenga dos casillas blancas y dos negras.

Aquí la hoja de cálculo te puede ayudar a visualizar cada situación,
como puedes observar en la imagen adjunta. Puedes usar el
“deshacer” para ir viendo posibilidades

¿Cuántas formas de colorear pueden existir?



S U MA S G E N E R A D A S C O N T R E S CI F R A S



Consideramos los números enteros menores que 1000, desde el 000
hasta el 999. Para cada uno sumamos sus cifras y obtendremos una
suma S. Encuentra un valor de S para el que hay exactamente 63
números que la producen.



Tres ayudas:

Para suma S=4 hay 15 números que la producen, desde 004 hasta
400.

6





Para suma S=15 tendremos 69 soluciones.

Te puede ayudar este esquema de decisión, si llamas A a la primera
cifra

Y una curiosidad:

Si representamos el número de soluciones para cada valor de S entre
0 y 27, nos resulta esto:



¿Te recuerda algo?



F R O N T E R A S E N UN T A B L E R O


Partimos de un problema

Se tiene un tablero cuadriculado de 10 por 10 casillas. La mitad de sus
casillas se pintan de blanco, y la otra mitad de negro. Un lado común a
dos casillas en el tablero se llama lado frontera si estas dos casillas
tienen colores diferentes. Determinar el mínimo y el máximo número de
lados frontera que puede haber en el tablero (propuesto en la OMCC).

Unas cuestiones se nos ocurren a partir de este poblema:

7






a) ¿Son posibles soluciones del problema
los números
comprendidos entre 10 y 180, o existe algún valor que nunca se
produce?

todos

b) ¿De cuántas formas se pueden elegir los cincuenta cuadrados que
se pintan de negro?

La solución es 1008913445455641933334812497256.

c) ¿Se podría organizar alguna simulación con ordenador? Se
plantearían dos problemas:

c1) Si rellenamos aleatoriamente cincuenta cuadrados con color negro,
habrá que tomar nota de los que ya poseen ese color antes de elegir el
siguiente (que deberá ser blanco)

c2) Deberemos diseñar un procedimiento que recorra todos los bordes
interiores de los cuadrados del tablero y lleve la cuenta de los que
unen cuadrados de color diferente.

C3) Se podría completar con

Estúdialo antes de seguir leyendo.

Respuestas

la estimación de

la media

Por si no lo has intentado te ofrecemos dos versiones (Excel y
OpenOffice.org) en la dirección

http://hojamat.es/blog/lineafront.zip

Si entras en el editor de Basic podrás analizar los algoritmos
empleados. Son muy instructivos.

Nosotros hemos programado una serie de 500 simulaciones, lo que
nos ha dado una estimación de 91,096 para la media de líneas frontera
y 6,128 para la desviación estándar, así como que sólo son
ligera
  • Links de descarga
http://lwp-l.com/pdf5054

Comentarios de: Combinatoria (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad