Una contribución a los ejercicios de combinatoria.
Sean \(A\eq=\{1,2,...,15\},\;B\eq=\{1,2,...,27\}\). Calcular el número de funciones estrictamente crecientes \(f:A\rightarrow B\) tales que \(f(2)>5\)
Esta es la solución que se me ocurrió; no se si hay una forma más fácil, pero bueno. Observemos que una función es estrictamente creciente si y solo si \(f(i)<f(j)\Leftrightarrow i<j\). Además, será conveniente empezar estudiando la condición más dura, \(f(2)>5\Leftrightarrow f(2)\geq6\). Luego, empezaremos contando de la siguiente manera:
-\(f(2)\eq=14\). Notemos que en este caso, por ser la función estrictamente creciente, solamente puede valer la distribución \(f(3)\eq=15,\;f(4)\eq=16,\;...f(15)\eq=27\)(pues tengo para elegir para las otras 13 imágenes 13 números; y solo hay UNA manera de ordenarlos de menor a mayor). Es decir, contamos 1 caso.
-\(f(2)\eq=13\). En este caso, podemos pensar los subcasos \(f(3)\eq=15,\;f(3)\eq=14\). En el primer caso, solo hay una manera, por lo explicado anteriormente. En el segundo caso, podemos pensar lo siguiente; tenemos para elegir del conjunto \(\{15,16,...,27,\}\), que tiene 13 elementos. Como necesitamos 12, si sacamos 1, tenemos solo UNA manera de ordenar de menor a mayor los 12 números. Como podemos sacar ese pobre elemento de 13 maneras distintas(\(13 \choose 1\)), concluímos que tenemos 13 maneras con esta elección. En este caso, contamos 13+1 distribuciones.
-\(f(2)\eq=12\). Usamos un razonamiento análogo; si fijamos \(f(3)\eq=15\), una sola manera. Si fijamos \(f(3)\eq=14\), nuevamente tenemos 13 distribuciones. Y si fijamos \(f(3)\eq=13\)... tenemos que eliminar de nuestro anterior conjunto, que ahora tiene un elemento más(el 14) dos pobres elementos, y por cada eliminación, tenemos UNA sola de ordenar los 12 elementos restantes de menor a mayor. Luego tenemos de estas \(14 \choose 2\). Luego, en total, sumando todos los casos, 1+13+91 distribuciones.
A esta altura, ya se ve el patrón; si fijo \(f(2)\eq=k,\;6\leq k\leq 14\), tenemos para fijar \(f(3)\eq=15,\;f(3)\eq=14,\;...f(3)\eq=k+1\). En cada caso, eliminamos del conjunto \(\{k+1,k+2,...27)\), que tiene 27-k-1+1=27-k elementos, de los cuales tenemos que eliminar 15-k elementos, para que nos queden 12, que se ordenan de UNA sola manera. Tenemos \(27-k \choose 15-k\) maneras. Luego, por cada k tenemos \(\sum_{i\eq=k+1}^{15}{27-i \choose 15-i}\) maneras. Como k lo variamos entre 6 y 14, y sumamos todos los casos, podemos escribir \(\sum_{k\eq=6}^{14}\sum_{i\eq=k+1}^{15}{27-i \choose 15-i}\), y este es el total de los casos.
Ahora bien, dejamos solo al pobre \(f(1)\). Como este valor debe ser menor que \(f(2)\), una vez fijo este valor en \(k\), tenemos k-1 números para elegir(si \(f(2)\eq=6\), podemos elegir 1,2,3,4,5). Luego, por cada distribución, debemos multiplicar k-1, dentro de la suma más externa y fuera de la suma más interna. En definitiva: \(\sum_{k\eq=6}^{14}(k-1)\sum_{i\eq=k+1}^{15}{27-i \choose 15-i}\) maneras de elegir estas funciones. Y este era el número que queríamos calcular
Espero haber ayudado. Saludos
Firma
I offer her that kernel of myself that I have saved, somehow; the central heart that deals not in words, traffics not with dreams and is untouched by time, by joy, by adversities
Mm, yo lo resolvi de la siguiente forma:
Para contar las crecientes tales que \(f(2)>5\), hice el total de funciones estrictamente crecientes menos las funciones crecientes en donde \(f(2)\leq5\).
El total de funciones crecientes seria \(27 \choose 15\).
Y la cantidad de funciones que tengo que restar seria cuando \(f(2)=2, f(2)=3,...,f(2)=5\)
(\(f(2)=1\) no puede ser porque si no \(f(1) = k>1\) y f no sería creciente)
Ahora, para \(f(2) = 2\), automáticamente queda que \(f(1)=1\), y entonces habría que elegir 13 números de 25 para el resto, osea hay \(25 \choose 13\).
Para \(f(2)=3\), \(f(1)=1 \lor f(1) = 2\), y para el resto habría \(24 \choose 13\), lo que nos da un total de \(2.\)\(24 \choose 13\) funciones.
Siguiendo para 4 y 5, queda que la cantidad de funciones que cumplen lo pedido es:
\(27 \choose 15\) \(-\) \(25 \choose 13\) \(-2.\)\(24 \choose 13\) \(-3.\)\(23 \choose 13\) \(-4.\)\(22 \choose 13\) = \(1769394\)
La verdad no hice la cuenta a ver si la sumatoria a la que vos llegaste da lo mismo que mi resultado. Esperemos que si XDDD. Saludos!
Igual está mejor la que escribiste vos. Lo otro fue lo primero que se me ocurrió; por alguna razón pensé que me iba a ser menos cuentoso ir directo en vez de restar las funciones que no satisfacían las hipótesis. Gracias y saludos.
No, el de exequiel da distinto, a mí me dio como a Floyd y lo hice de otra forma (me gusta más la tuya que la mía igual, porque yo sumé todo en vez de restarle al total, lo cual eran menos cuentas).. Me inclino a pensar que el de Floyd está bien y el otro no, porque es menos rebuscado y le seguí mejor el razonamiento (al otro no le encuentro el error igual).. Ah, aclaro que puede ser que de bien y que esté tan quemado que hice mal la cuenta jaja..
A mí me dio esto:
\(\sum_{n=5}^{13}n \cdot {27-(n+1)\choose 13}\)
que da el mismo número que pusiste vos: 1769394
Para mí, el problema de la sumatoria que le quedó a exequiel es el 15-k, que para mí es un 13 siempre (de esa forma es la misma sumatoria que puse yo, si no me equivoco)..
Recién hice la suma, y me dio lo mismo; 1769394. Lo que pasa que la expresión de la suma es horrible. Ya dije, me gusta más la otra idea; mi razonamiento terminó en una fórmula; no en un número(lo que pasa es que lo pensé para el problema general; por eso dejé la expresión así). Así que da lo mismo. Igual gracias por verificar
perdón por mi ignorancia...
pero les quería preguntar cual fue es mi error en lo que pensé:
Si la función \(f:A\rightarrow B\) con \(A\eq=\{1,2,...,15\},\;B\eq=\{1,2,...,27\}\) es estrictamente creciente y \(f(2)>5\)
entonces para \(f(1)\) tengo sólo 5 posibilidades, \(f(1)=1, f(1)=2,..., o f(1)=5\)
después, lo que me queda es acomodar \(A\eq=\{2,...,15\}\rightarrow B\eq=\{6,...,27\}\) de tal manera de que sea estrictamente creciente... lo que sería:
$$22 \choose 14$$
finalmente concluyo que el numero de funciones estrictamente crecientes que cumplen con las condiciones es:
\(5.{22 \choose 14}=1598850\) =(
Bueno....segun fuentes me indican y parece totalmente lógico y de hecho es así,jajajaj
el tema es q vos estas fijando valores de f(1) para 1,2,3,4 y 5... cuando f(2) tranquilamente puede tomar el valor digamos... 7
y f(1) podria tomar entonces el valor 6...entendes?
esos casos no los estas considerando
esto se debe a q f(2) es quien acota a f(1) 😄
Gracias Nachito (que no se digna a venir a postear)
Firma
Pape Trataremos de buscarle una solución más útil que el famoso "reinicie el equipo y vea si mejora"
perdón por mi ignorancia...
pero les quería preguntar cual fue es mi error en lo que pensé:
Acá usé en parte lo que usaste vos y fue todo mas corto:
Si la función \(f:A\rightarrow B\) con \(A\eq=\{1,2,...,15\},\;B\eq=\{1,2,...,27\}\) es estrictamente creciente y \(f(2)>5\)
entonces tengo 2 casos disjuntos, supongamos primero que \(f(1) < 6\): para \(f(1)\) tengo sólo 5 posibilidades, \(f(1)=1, f(1)=2,..., o f(1)=5\)
después, lo que me queda es acomodar \(A\eq=\{2,...,15\}\rightarrow B\eq=\{6,...,27\}\) de tal manera de que sea estrictamente creciente... lo que sería:
\(22 \choose 14\).
Supongamos ahora que \(f(1) > 5\), lo cual son casos claramente disjuntos, luego
tengo \({23 \choose 15}\) funciones estrictamente crecientes que cumplen lo requerido.
finalmente concluyo que el numero de funciones estrictamente crecientes que cumplen con las condiciones es:
\(5.{22 \choose 14} + {23 \choose 15}=1769394\)
Acá usé en parte lo que usaste vos y fue todo mas corto:
Si la función \(f:A\rightarrow B\) con \(A\eq=\{1,2,...,15\},\;B\eq=\{1,2,...,27\}\) es estrictamente creciente y \(f(2)>5\)
entonces tengo 2 casos disjuntos, supongamos primero que \(f(1) < 6\): para \(f(1)\) tengo sólo 5 posibilidades, \(f(1)=1, f(1)=2,..., o f(1)=5\)
después, lo que me queda es acomodar \(A\eq=\{2,...,15\}\rightarrow B\eq=\{6,...,27\}\) de tal manera de que sea estrictamente creciente... lo que sería:
\(22 \choose 14\).
Supongamos ahora que \(f(1) > 5\), lo cual son casos claramente disjuntos, luego
tengo \({23 \choose 15}\) funciones estrictamente crecientes que cumplen lo requerido.
finalmente concluyo que el numero de funciones estrictamente crecientes que cumplen con las condiciones es:
\(5.{22 \choose 14} + {23 \choose 15}=1769394\)
Cuidado que la cuenta está mal al final.
\(5.{22 \choose 14} + {23 \choose 15}=2089164\)
Me parece que en vez de 23 quisiste escribir 22.
$$5.{22 \choose 14} + {22 \choose 15}=1769394$$
Si no hay equivocación no entiendo de donde sale el 23.
Si tengo que acomodar los números entre el 27 y el 6 inclusive eso son 22 lugares.