analisis combinatorio aplicado a la contabilidad

Cap´
ıtulo 2

Las t´cnicas b´sicas de la
e
a
Combinatoria
Contar es una t´cnica . . . y un arte. Averiguar cu´ntos objetos existen que se ajustan a
e
a
o ısica, concreta,
determinadas caracter´
ısticas puede no ser f´cil1 . En el caso de una colecci´n f´
a
de objetos se trata simplemente de enumerarlos, es decir, de decir qui´n es el primero, qui´n
e
e
el segundo, etc. Pero si,como es habitual, lo que tenemos es una colecci´n definida abstraco
tamente (como por ejemplo, los pasos de un algoritmo cuando los datos de entrada son de un
determinado tama˜o), el procedimiento tiene que ser otro. Con frecuencia, la unica alternan
´
tiva es indirecta y consiste en comparar la colecci´n dada con otra colecci´n de objetos (cuyo
o
o
n´mero conocemos) y comprobar, si fuera elcaso, que tienen el mismo n´mero de objetos.
u
u
En este cap´
ıtulo discutiremos t´cnicas utiles para llevar a cabo ese tipo de comprobaciones;
e
´
pero c´mo seleccionar la colecci´n adecuada con la que se compara es m´s una cuesti´n de
o
o
a
o
experiencia, y de prueba y error; todo un arte.
Las colecciones de objetos que nos interesar´n vienen a veces ordenadas de forma natural
a
yotras veces el orden resulta irrelevante. En ocasiones las colecciones se forman atendiendo
a ciertos principios de exclusi´n que impiden repeticiones, y en otras no. Estos dos condicioo
nantes, orden y repetici´n, aparecen siempre en cualesquiera cuestiones de Combinatoria. Y
o
siempre, en cada caso particular, habr´ que precisarlos.
a
Un conjunto es una colecci´n (no ordenada) de objetos,que llamaremos sus elementos.
o
Un conjunto muy especial es el conjunto vac´ Ø, aqu´l que no tiene elemento alguno. Geneıo,
e
ralmente, representaremos un conjunto escribiendo sus elementos entre llaves. Si permitimos
que el conjunto contenga elementos repetidos, utilizaremos un nombre especial, multiconjuntos. Nos interesar´, fundamentalmente, contar el n´mero de elementos de que consta una
u
conjunto, lo que llamaremos su tama˜ o o cardinal. En un momento precisaremos esta idea.
n
En muchas ocasiones convendr´ considerar listas, colecciones ordenadas de objetos, en las
a
que deberemos distinguir si se permite o no la aparici´n repetida de elementos (hablaremos
o
de listas con y sin repetici´n permitida). Las representaremos generalmente escribiendo sus
o
elementos entrepar´ntesis. El n´mero de elementos de que consta una lista ser´ su longitud.
e
u
a
A una lista de longitud k nos referiremos en ocasiones, por abreviar, como una k-lista.
1

Es bien sabido que hay tres tipos de matem´ticos: los que saben contar y los que no.
a

51

52

´
Cap´
ıtulo 2. Las t´cnicas basicas de la Combinatoria
e

Todas estas ideas ser´n convenientementedesarrolladas en las p´ginas siguientes, donde
a
a
nos entrenaremos en la tarea de decidir qu´ tipo de objetos son los adecuados para describir
e
cada problema particular.
A veces tendremos que mezclarlos y considerar, por ejemplo, conjuntos cuyos elementos
son listas, o listas cuyos t´rminos son conjuntos. Supongamos, por ejemplo, que tenemos los
e
objetos a, b y c. Podemos, por ejemplo,considerar los conjuntos de tama˜o 2 que podemos
n
formar con estos objetos,
{a, b}, {a, c}, {b, c} ,
o quiz´s las listas sin repetici´n de longitud 2,
a
o
(a, b), (b, a), (a, c), (c, a), (b, c), (c, b) .
Si permiti´ramos repetici´n de elementos, deber´
e
o
ıamos a˜adir, en el primer caso, los conjuntos
n
{a, a}, {b, b} y {c, c}; y, en el segundo, las listas (a, a), (b, b) y (c, c).Obs´rvese el uso que hemos hecho de la notaci´n de las llaves y los par´ntesis en esta
e
o
e
enumeraci´n. Por ejemplo, el conjunto {a, b} es el mismo que {b, a}, mientras que la lista
o
(a, b) es distinta de la lista (b, a).

2.1.

Aprendiendo a contar

Se dice que un conjunto A tiene cardinal n si existe una funci´n biyectiva f del conjunto
o
{1, . . . , n} en el conjunto A. Por convenio...