t¿De cuántas maneras podemos dividir un conjunto S en dos subconjuntos bajo las siguientes restricciones?

¿De cuántas maneras podemos dividir un conjunto S en dos subconjuntos tales que:

El conjunto S puede tener norte elementos de la gama 1 a 1000 (inclusivo). Sean los dos subconjuntos A y B . Para todos X en el rango 1 a 1000 contamos el número de elementos en cada subconjunto que son iguales a X . Deja que el conjunto A tiene a elementos iguales a X , y y el conjunto B tiene b elementos de igual a X . Calculamos la suma de todos estos a 'arena b 's. Ahora cómo determinar cuántos subconjuntos la suma de todos a 's es más que la suma de todos esos b 's (sin iterar realmente a través de todos los subconjuntos)

Ejemplo:

Dejar S = { 1 , 1 , 3 , 2 } en estos casos la respuesta es 5 . Y la elección del subconjunto de A son: { 1 , 1 , 3 } , { 1 , 1 , 2 } , { 1 , 3 , 2 } , { 1 , 3 , 2 } , { 1 , 1 , 3 , 2 }

Tenga en cuenta: cualquiera de las particiones puede estar vacía para este problema.

¿Esas sumas no te dan el número de elementos de A y de B ? Entonces, ¿no estás obteniendo todas las particiones donde A tiene más elementos que B ?
Normalmente un conjunto no puede tener dos elementos iguales, por lo que { 1 , 1 , 3 , 2 } no sería un conjunto. Un conjunto múltiple puede tener elementos iguales. Si S tiene que ser un conjunto, Gerry Myerson tiene razón en que las sumas son solo el número de elementos en A y B . ¿Estás tratando de calcular el número de pares? A , B donde el tamaño de A es mayor que el tamaño de B ? Hacer A y B tener que agotar S ?
@RossMillikan Yo diría eso { 1 , 1 , 3 , 2 } es un conjunto, es igual a { 1 , 3 , 2 } (así como para { 1 , 2 , 3 } , etc.) En el desarrollo habitual de la teoría axiomática de conjuntos, es importante que la operación de emparejamiento se pueda usar para obtener singletons { X , X } .

Respuestas (1)

Lo que tomas en realidad no son conjuntos, sino algo como esto: para cada número k , se especifica un número máximo s ( k ) ∈ norte 0 de ocurrencias. Solo hay un número finito k con s ( k ) ≠ 0 . Queremos encontrar todas las opciones posibles para las funciones. a tal que 0 ≤ a ( k ) ≤ s ( k ) para todos k y ∑ k a ( k ) > 1 2 ∑ k s ( k ) .

Si eliminamos la condición ∑ k a ( k ) > 1 2 ∑ k s ( k ) por un momento hay ∏ k ( s ( k ) + 1 ) posibles funciones a . Dejar σ = ∑ k s ( k ) . Para cada a con ∑ k a ( k ) < 1 2 σ , su complemento tiene suma > 1 2 σ . Por lo tanto, si σ es impar, entonces el número deseado es simplemente

(1) 1 2 ∏ k ( s ( k ) + 1 ) .
Sin embargo, si σ es par, necesitamos contar explícitamente el número de funciones a tal que ∑ k a ( k ) = 1 2 σ y luego restar la mitad de este número de ( 1 ) . El conteo en este caso, supongo, se hace mejor usando las técnicas de programación dinámica...

Excelente respuesta +1
t¿De cuántas maneras podemos dividir un conjunto S en dos subconjuntos bajo las siguientes restricciones?
RespuestasAquíPolítica de privacidad1y, 0v