En pocas palabras, mi pregunta es como tal: ¿por qué usamos la multiplicación? Por ejemplo, supongamos que tengo dos elementos en el conjunto $\{A,B\}$ y quiero saber cuántas formas posibles hay de ilustrarlos como palabras con 3 letras, sé que esto es $2*2*2=8$ , $\{AAA,AAB,ABB,...,BBB\}$ pero ¿Podría alguien explicar por qué esto funciona?
Respuestas
¿Demasiados anuncios?
$\newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]}$ Supongo que usted está buscando para las pruebas de los siguientes hechos (específicamente Teorema 3, pero pronto se desea que los demás también):
Teorema 1 (binario producto principio, producto directo de la versión). Deje $A$ e $B$ dos conjuntos finitos. A continuación, $\abs{A \times B} = \abs{A} \cdot \abs{B}$.
(Tenga paciencia conmigo, los siguientes son un poco complicado, pero voy a explicar su significado en breve).
Teorema 2 (binario producto principio, diagrama de ruta de la versión). Deje $W$ e $S$ finita de conjuntos, y deje $f : S \to W$ ser cualquier mapa. Deje $b$ ser un entero no negativo. Supongamos que para cada una de las $w \in W$, hay exactamente $b$ muchos elementos $s \in S$ satisfacción $f \tup{s} = w$. A continuación, $\abs{S} = \abs{W} \cdot b$.
Teorema 3 ($n$-ary producto principio, producto directo de la versión). Deje $A_1, A_2, \ldots, A_n$ ser $n$ finito de conjuntos. A continuación, $\abs{A_1 \times A_2 \times \cdots \times A_n} = \abs{A_1} \cdot \abs{A_2} \cdot \cdots \cdot \abs{A_n}$.
Teorema 4 ($n$-ary producto principio, diagrama de ruta de la versión). Deje $S_0, S_1, \ldots, S_n$ ser cualquier $n$ finito de conjuntos. Deje $f_i : S_i \to S_{i-1}$ ser un mapa para cada uno de los $i \in \set{1, 2, \ldots, n}$. Deje $b_1, b_2, \ldots, b_n$ ser números enteros no negativos. Supongamos que para cada una de las $i \in \set{1, 2, \ldots, n}$ y cada una de las $w \in S_{i-1}$, hay exactamente $b_i$ muchos elementos $s \in S_i$ tal que $f_i \tup{s} = w$. A continuación, $\abs{S_n} = \abs{S_0} \cdot b_1 b_2 \cdots b_n$.
Teorema 1, dice que si se tienen dos conjuntos finitos $A$ e $B$ de los tamaños de las $a$ e $b$, entonces no se $ab$ maneras de elegir un par ordenado $\tup{x, y} \in A \times B$. Teorema 3 es un análogo de hecho, para $n$-tuplas; esto es lo que está utilizando en el ejemplo.
Teoremas 2 y 4 representan más complicado de la situación, cuando usted está haciendo múltiples opciones y las opciones disponibles en un momento puede depender de su hecho anteriormente opciones. Por ejemplo, si queremos contar todos los pares $\tup{x, y} \in \set{1,2,3,4,5}^2$ satisfacción $x \neq y$, entonces podemos hacer esto por primera eligiendo $x$ (hay $5$ formas de hacerlo), y luego elegir la $y$ (hay $4$ formas de hacerlo, ya que debemos evitar que el valor de $x$). El resultado es $5 \cdot 4$, pero esto no es porque nos están mirando el tamaño de un producto Cartesiano de una $5$-element set con un $4$-elemento del conjunto. Más bien, estamos ante un gran conjunto $S$ que consta de todos nuestros pares $\tup{x, y}$ satisfacción $x \neq y$, y en un conjunto más pequeño $W = \set{1,2,3,4,5}$ que representan las opciones disponibles en el primer paso. Sabemos que después de la elección de un $x$ en el primer paso, hay exactamente $4$ opciones válidas para $y$. En otras palabras, cada una de las $x \in W$ puede ser extendido a un par $\tup{x, y} \in S$ exactamente $4$ maneras. En otras palabras, para cada una de las $w \in W$, hay exactamente $4$ elementos $s = \tup{x, y} \in S$ satisfacción $x = w$. En otras palabras, si se define un mapa de $f : S \to W$ por $f\tup{\tup{x, y}} = x$, entonces para cada a$w \in W$, hay exactamente $4$ muchos elementos $s \in S$ satisfacción $f \tup{s} = w$. Por lo tanto, estamos mirando la situación del Teorema 2 con $b = 4$. Por lo tanto el teorema de los rendimientos $\abs{S} = \abs{W} \cdot 4 = 5 \cdot 4$, que es exactamente lo que el sector informal de la idea de multiplicar el número de opciones sugiere. La respuesta por @MarianD visualiza este tipo de pensamiento muy bien el uso de "la ruta de los diagramas"; es por eso que me llama Teorema 2 el "diagrama de ruta de la versión". Teorema 4 es, de nuevo, un análogo del Teorema 2 para múltiples opciones (donde $S_i$ representa el conjunto de estados posibles después de hacer la primera $i$ opciones, y $b_i$ es el número de opciones posibles para la $i$-th elección). Tenga en cuenta que me han tirado un poco más de generalidad en el Teorema 4, permitiendo que el conjunto $S_0$ tener más de un elemento (es decir, incluso para el estado inicial puede haber varias opciones).
Viendo que todas estas afirmaciones son intuitivamente obvio una vez que se declaró en la lengua común (y Bourbaki nunca han llegado en torno a la publicación de un Combinatoire tomé), no es de extrañar que casi no hay texto demuestre explícitamente a ellos. La única excepción es Nicolás Loehr del Bijective Combinatoria (2011), lo que demuestra los Teoremas 1 y 3 en las Secciones 1.2--1.3 y 1.6, y de alguna manera se evita explícita de los Teoremas 2 y 4.
No tengo el tiempo para escribir completo de las pruebas de los cuatro teoremas ahora mismo, pero te voy a dar algunos consejos. Primero de todo, Teoremas 3 y 4 siga por inducción (en $n$) de los Teoremas 1 y 2, respectivamente. Por lo tanto, queda por probar a los dos últimos teoremas. Segundo, Teorema 1 sigue por el Teorema 2 (aplicado a $S = A \times B$ e $W = A$ e $b = \abs{B}$ e $f = \tup{\text{the map $A \times B \a$ sending each $\tup{x, y}$ to $x$}}$). Por lo tanto, queda por demostrar el Teorema 2. El más simple -- para mí -- forma de hacerlo es mediante la reducción a la siguiente hecho:
Teorema 5 (suma principio de separación). Deje $W$ e $S$ se establece, y deje $f : S \to W$ ser cualquier mapa. Deje $a_s$ ser un número (por ejemplo, integer) para cada una de las $s \in S$. A continuación, \begin{align} \sum_{s \in S} a_s = \sum_{w \in W} \sum_{\substack{s \in S; \\ f\tup{s} = w}} a_s . \end{align}
Esta es una propiedad básica de finito de sumas, diciendo que se puede dividir un número finito de resumir en un montón de pequeñas sumas de dinero, cada uno de los cuales combina los sumandos de la suma original con un cierto valor de $f\tup{s}$. Por ejemplo, este es el principio detrás de la reescritura de $1 + 2 + 3 + \cdots + 2n$ como $\tup{1 + 3 + 5 + \cdots + \tup{2n-1}} + \tup{2 + 4 + 6 + \cdots + 2n}$ ( $S = \set{1,2,3,\ldots,2n}$ e $W = \set{0, 1}$ e $a_s = s$, e $f$ es el mapa enviar a cada entero $s \in S$ a su resto en la división por $2$). Ahora, el Teorema 5 es una expresión algebraica de la declaración y de probabilidades de estar en Bourbaki; de todos modos también es el Teorema de 2.127 en mis Notas sobre la combinatoria fundamentos de álgebra donde he demostrado en todos los detalles. Una vez que usted acepta el Teorema 5, es fácil probar el Teorema 2:
La prueba del Teorema 2. Teorema 5 (aplicado a $a_s = 1$) de los rendimientos de \begin{align} \sum_{s \in S} 1 = \sum_{w \in W} \sum_{\substack{s \in S; \\ f\tup{s} = w}} 1 = \sum_{w \in W} \sum_{s \in \set{t \in S \mid f\tup{t} = w}} 1. \label{darij1.pf.t2.1} \tag{1} \end{align} Pero cada conjunto finito $P$ satisface $\sum_{s \in P} 1 = \abs{P}$. Por lo tanto, $\sum_{s \in S} 1 = \abs{S}$. Por la misma razón, cada una de las $w \in W$ satisface $\sum_{s \in \set{t \in S \mid f\tup{t} = w}} 1 = \abs{\set{t \in S \mid f\tup{t} = w}} = \abs{\set{s \in S \mid f\tup{s} = w}} = b$ (por la suposición de que hay exactamente $b$ muchos elementos $s \in S$ satisfacción $f\tup{s} = w$). Por lo tanto, \eqref{darij1.pf.t2.1} se reescribe como \begin{align} \abs{S} = \sum_{w \in W} b = \abs{W} \cdot b . \end{align} Esto demuestra el Teorema 2. $\blacksquare$
palmpo
Puntos
26
MarianD
Puntos
304
Primera carta puede ser a o B, por lo que tenemos 2 opciones:
Para cada una de esas 2 opciones (1 de la letra a, 1º letra B) tenemos 2 opciones para la segunda letra, es decir, a o B:
Así que ahora tenemos 2 * 2 = 4 opciones para las 2 primeras letras, es decir, AA, AB, BA, BB:
Y para cada uno de esos 2 * 2 (i. e. 4) las opciones para las primeras 2 letras (AA, AB, BA, BB) tenemos 2 opciones para la tercera carta, es decir, a o B:
Así que finalmente nos han 2 * 2 * 2 opciones: AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB:
MarianD
Puntos
304
Para las primeras 2 letras obtenemos un cuadrado de 2 x 2, por lo que hay 4 opciones:
A B
┼────┼────┤
A │ AB │ BB │
┼────┼────┤
B │ BA │ BB │
┴────┴────┘
Ahora podemos agregar una A como la tercera letra:
A B
┼─────┼─────┤
A │ ABA │ BBA │
┼─────┼─────┤
B │ BAA │ BBA │
┴─────┴─────┘
o B como la tercera letra:
A B
┼─────┼─────┤
A │ ABB │ BBB │
┼─────┼─────┤
B │ BAB │ BBB │
┴─────┴─────┘
Puedes imaginar esos dos cuadrados de 3 letras como dos capas del cubo resultante, cuyo volumen será 2.2.2 = 8.
MarianD
Puntos
304
