¿Cuántos elementos tiene P(A)P(A)\mathcal{P}(A)?

Question

¿Cuántos elementos tiene P(A)P(A)\mathcal{P}(A)?

Matemáticas
combinatoria
teoría de los números

usuario142198

Dejar $A$ ser un conjunto de talla quince. Dejar $\mathcal{P}(A)$ denota el conjunto potencia de $A$ , que es el conjunto de todos los subconjuntos de $A$ . cuantos elementos tiene $\mathcal{P}(A)$ ¿contener?

Esto es lo mismo que ser $0$ o $1$ , conjuntos binarios de tamaño $1\to 14$ ?

¿Significa esto que la respuesta es

${15\choose 0} + {15\choose 1} + {15\choose 2} +\dots +{15\choose 13}+{15\choose 14}+{15\choose 15}$ ?

¿O hay algo que no estoy considerando?

André Nicolás

de tamaño

0

$0$ a

15

$15$ . Tu expresión es correcta. No es realmente necesario, el número es

2^{15}

$2^{15}$ .

usuario169852

Su respuesta es correcta, pero tenga en cuenta que se puede expresar de una forma mucho más simple, a saber

(1 + 1)^{15} = 2^{15}

$(1+1)^{15} = 2^{15}$ . Este es un resultado del teorema del binomio:

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k}

$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k}$ con

x = y = 1

$x=y=1$ . Otra forma de pensarlo es que cada uno de los

15

$15$ los elementos se pueden incluir o excluir, por lo que hay

2^{15}

$2^{15}$ posibilidades.

usuario142198

@Bungo Ahhh, esa era la dirección en la que iba mi lógica con la comparación binaria, ¡pero supongo que no hizo clic por completo!

José Antonio

O incluso puede mostrar usando inducción, por ejemplo, que cualquier conjunto de potencia de un conjunto finito tiene cardinalidad

2^{# set}

$2^{\#\text{ set}}$

usuario142198

@JoseAntonio Eso fue

2^{size of set}

$2^{\text{ size of set }}$ ?

José Antonio

Sí, o puede mostrar un mapa biyectivo de

{0, 1}^{n} \to P (n)

$\{0,1\}^n\to \mathcal{P}(n)$ y el resultado es casi trivial, pista: utilice la función de indicador.

n

$n$ es el conjunto con

n

$n$ elementos perdón por la notación es tardía

Respuestas (1)

¿Cuántos elementos tiene P(A)P(A)\mathcal{P}(A)?

de tamaño $0$ a $15$ . Tu expresión es correcta. No es realmente necesario, el número es $2^{15}$ .
Su respuesta es correcta, pero tenga en cuenta que se puede expresar de una forma mucho más simple, a saber $(1+1)^{15} = 2^{15}$ . Este es un resultado del teorema del binomio: $(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k}$ con $x=y=1$ . Otra forma de pensarlo es que cada uno de los $15$ los elementos se pueden incluir o excluir, por lo que hay $2^{15}$ posibilidades.
@Bungo Ahhh, esa era la dirección en la que iba mi lógica con la comparación binaria, ¡pero supongo que no hizo clic por completo!
O incluso puede mostrar usando inducción, por ejemplo, que cualquier conjunto de potencia de un conjunto finito tiene cardinalidad $2^{\#\text{ set}}$
Sí, o puede mostrar un mapa biyectivo de $\{0,1\}^n\to \mathcal{P}(n)$ y el resultado es casi trivial, pista: utilice la función de indicador. $n$ es el conjunto con $n$ elementos perdón por la notación es tardía

pedro huxford · Answer 1

Su suma es correcta, y además en general:

(\binom{norte}{0}) + (\binom{norte}{1}) + (\binom{norte}{2}) + \dots + (\binom{norte}{norte - 1}) + (\binom{norte}{norte}) = 2^{norte} .

$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+\binom{n}{n}=2^n.$

Así que otra forma de realizar tu suma es $2^{15}$ .

Una prueba combinatoria de que el tamaño del conjunto potencia de un $n$ conjunto de elementos $A$ es $2^n$ (que también se puede usar para probar la identidad anterior) es el siguiente.

Hay una biyección entre subconjuntos. $X\subset A$ y $n$ -secuencias binarias de bits, donde hay un 1 en el $i$ ª posición de la secuencia si y sólo si la $i$ el elemento de $A$ está en el subconjunto correspondiente. Es fácil demostrar que se trata de una biyección. Además, el número de $n$ Las secuencias binarias de bits son claramente $2^n$ (usted tiene dos opciones para cada uno de los $n$ bits). Esto prueba la afirmación.

¡Gracias, eso tiene sentido! Una pregunta más: ¿cuántas cadenas de bits hay que contengan exactamente nueve $0$ s y seis $1$ 's, si cada 1 debe ser seguido inmediatamente por un $0$ ? ¿Emparejaría el $10$ me está atrapando $3 \;\;0$ 'arena $6$ pares, lo que significa que solo tengo que mirar el número de combinaciones de esto? $\frac{9!}{6!3!}$
Sí, así es, si lo reescribió de modo que cada uno de los "10" pares fuera un 2, entonces está contando la cantidad de formas de organizar tres 0 y seis 2, lo que da $\frac{9!}{3!6!}$ .
Resulta que por esta razón, el conjunto potencia de $A$ a veces se escribe $2^A$ .

¿Cuántos elementos tiene P(A)P(A)\mathcal{P}(A)?

usuario142198

André Nicolás

usuario169852

usuario142198

José Antonio

usuario142198

José Antonio

Respuestas (1)

pedro huxford

usuario142198

pedro huxford

Parcly Taxel

¿La Regla de Collatz 3x+53x+53x+5 tiene un sesgo para ciertos bucles, o mis resultados son defectuosos?

Dado el MCD y el MCM de n enteros positivos, ¿cuántas soluciones hay?

Dos relaciones en serie, cada una implica a la otra - del libro de particiones de Andrews

Existencia de un subconjunto tal que el producto de sus elementos es un cuadrado perfecto

¿Hay alguna identidad de poder que no pertenezca a esta lista?

si |S∩{1,2,3,…,n}|≥un|S∩{1,2,3,…,n}|≥un|S\cap \{1,2,3,\ldots, n\}|\ge un, etc. muestran que Z+⊂S+TZ+⊂S+T\Bbb Z_{+}\subset S+T

¿Cómo elegir nnn bolas de las bolsas?

¿Cómo encuentra el número de subarreglos de al menos tamaño k en un arreglo dado?

Número de composiciones de nnn tales que cada término es menor que igual a kkk

Demuestre estas identidades usando la identidad del triple producto de Jacobi.