Autor Tema: Combinación sin repeticiones

0 Usuarios y 1 Visitante están viendo este tema.

28 Febrero, 2024, 04:28 am
Leído 1125 veces

rojamer

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 25
  • País: co
  • Karma: +0/-0
  • Sexo: Masculino
¿Puedo definir la combinación de los elementos de un conjunto finito de \( n \) elementos tomados \( k \) elementos a la vez, sin devoluciones, de esta manera?

Combinación sin repeticiones
Sea \( A \) un conjunto no vacío de \( n \) elementos y \( k \) un número entero tal que \( 0<k\leq{n} \). Si \( A=\{a_1,a_2,\ldots,a_n\} \), entonces, la combinación de sus elementos, tomando \( k \) a la vez sin devoluciones, es decir, el conjunto de los subconjuntos de \( k \) elementos, es dado por la expresión:

\( \displaystyle\bigcup_{m_i=m_{i-1}+1}^{n-(k-i)}\left\{\bigcup_{i=1}^k\{a_{m_i}\}\right\} \)

En donde \( m_{0}=0 \) y su cardinal es:
\( \dfrac{n!}{k!(n-k)!} \)

28 Febrero, 2024, 10:05 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Creo que la idea está bien. Recursivamente generas los índices de los subconjuntos de \( k \) elementos, eligiendo un elemento y tomando los subconjuntos de \( k-1 \) con los elementos mayores (en índice) que el elegido.

 Ahora esta expresión:

\( C_k(A)=\begin{cases}{\emptyset}&\text{si}& k=0\\\displaystyle\bigcup_{m_i=m_{i-1}+1}^{n-(k-i)}\left\{\mathbf{ \times}_{i=1}^k\{a_{m_i}\}\right\} & \text{si}& 0<k\leq n\end{cases} \)

En donde \( m_0=0 \). Y el cardinal es:

 No tiene mucho sentido como está escrita; ahí no se ve la recursividad y de hecho es difícil interpretar que se supone que quieres escribir ahí.

Saludos.

P.D. Por favor, en lo sucesivo no uses fotos para textos que puedes teclear perfectamente en el mensaje.

28 Febrero, 2024, 07:54 pm
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Gracias por la sugerencia, pero tengo otra pregunta. ¿Se podría cambiar, en la fórmula, el símbolo de producto cartesiano X por el de la unión de conjuntos U, porque sería posible rescindir del orden de las componentes en cada k-upla?

Pero es que ya te digo que no tiene sentido la expresión que has escrito. Entiendo más o menos el algoritmo, pero en cuanto a la "función" no se muy bien exactamente que quieres escribir. Una cosa es describir una forma de enumerar los índices de los elementos de los distintos subconjuntos; otra propiamente describir simplemente los subconjuntos.

Saludos.

29 Febrero, 2024, 10:13 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Perdona mi insistencia. Si tengo un conjunto finito no vacío puedo enumerar sus elementos en cualquier orden. Después puedo trabajar únicamente con los índices asignados; y luego reemplazar sus correspondientes valores. Por ejemplo, para una combinación sin repetición de un conjunto de n=9 elementos, puedo enumerar sus elementos, en cualquier orden del 1 al 9, después hago las combinaciones de los índices en ternas (k=3) que me resultan en 84 (los índices de las ternas son los m_{k}) y por último retorno sus correspondientes valores asignados (que son los a_{m_{k}}, es decir, elementos del conjunto inicial A), y ya está!

Ya te dije que el algoritmo es correcto.

Citar
Lo que traté de hacer fue escribir el algoritmo como una expresión matemática que pongo en discusión si es válida.

Y lo que te digo es que no tiene sentido como está escrito. En general un algoritmo lo lógico es escribirlo...¡cómo un algoritmo, describiendo sus pasos!.

La otra escritura que pretendes es confusa. Un algoritmo en principio no es una función; puede forzarse su escritura como una función, pero en mi opinión lo que se consigue es volver críptico algo claro.

Saludos.