Nr. de expresii obtinute folosind reuniunea si intersectia
Posted: Thu Mar 18, 2010 2:46 am
M-am gandit la urmatoarea problema. Daca \( n\geq 1 \) a un nr natural cate expresii (ne-echivalente) in \( n \) multimi variabile \( X_1,\ldots,X_n \) pot fi obtinute folosind numai reuniunea si intersectia. De ex. \( A\cap (B\cup C) \) si \( (A\cap B)\cup (A\cap C) \) sunt aceeasi expresie.
Daca punem problema expresiilor folosind si diferenta atunci raspunsul este mult mai simplu, \( 2^{2^n-1} \).
Sa introducem niste notatii. \( I:=\{1,\ldots,n\} \), \( A \) e multimea expresiilor folosind reuniunea, intersectia si diferenta, \( B \) e multimea expresiilor folosind doar reuniunea si intersectia, \( P(X) \) e multimea partilor lui \( X \), iar \( P_k(X) \) e multimea partilor cu exact \( k \) elemente.
Atunci exista bijectia \( f: P(P(I)\setminus\{\emptyset\} )\to A \) data de \( X\mapsto\cup_{J\in X}((\cap_{i\in J}X_i)\setminus (\cup_{i\in I\setminus J}X_i)) \). Deci \( |A|=|P(P(I)\setminus\{\emptyset\} )|=2^{2^n-1} \).
Pentru \( |B| \) avem bijectia \( g:M\to B \), unde \( M=\{ X\in P(P(I)\setminus\{\emptyset\} )\mid J\not\subset L\forall J,L\in X\} \), data de \( X\mapsto\cup_{J\in X}(\cap_{i\in J}X_i) \). Deci \( |B|=|M| \).
Probabil ca nu exista formula exacta pt. \( |B| \) dar ar fi interesant sa gasim estimari. O margine superioara e bineinteles \( 2^{2^n-1} \). Pt. margini inferioare observam ca \( M\supseteq\cup_{k=1}^nP(P_k(I)) \), de unde rezulta ca \( |B|=|M|\geq S:=\sum_{k=1}^n2^{C_n^k} \). Pt. \( n \) mare singurii termeni ai sumei \( S \) cu contributie importanta sunt cel pt. \( k=\frac n2 \) cand \( n \) e par si pt. \( k=\frac{n\pm 1}2 \) cand \( n \) e impar. Deci \( S\approx 2^{C_n^{\frac n2}} \), respectiv \( S\approx 2^{C_n^{\frac{n-1}2}}+2^{C_n^{\frac{n+1}2}}=2^{C_n^{\frac{n-1}2}+1} \). Folosind aproximatia lui Stirling \( n!\approx\sqrt{2\pi n}(\frac ne}^n \) se arata ca \( C_n^{\frac n2} \) si \( C_n^{\frac{n-1}2} \) sunt \( \approx\frac{2^{n+1}}{\sqrt{2\pi n}} \).
Prin urmare \( 2^n-1\geq\log_2|B|\geq\log_2 S\approx\frac{2^{n+1}}{\sqrt{2\pi n}} \).
Asta e tot ce pot sa fac deocamdata. Am o banuiala vaga ca \( |B|\approx S \), dar nu sunt sigur.
Are cineva vreo idee sau a mai vazut undeva problema asta? Poate ca nu sunt primul care s-a gandit la asta si undeva exista deja o estimare.
Daca punem problema expresiilor folosind si diferenta atunci raspunsul este mult mai simplu, \( 2^{2^n-1} \).
Sa introducem niste notatii. \( I:=\{1,\ldots,n\} \), \( A \) e multimea expresiilor folosind reuniunea, intersectia si diferenta, \( B \) e multimea expresiilor folosind doar reuniunea si intersectia, \( P(X) \) e multimea partilor lui \( X \), iar \( P_k(X) \) e multimea partilor cu exact \( k \) elemente.
Atunci exista bijectia \( f: P(P(I)\setminus\{\emptyset\} )\to A \) data de \( X\mapsto\cup_{J\in X}((\cap_{i\in J}X_i)\setminus (\cup_{i\in I\setminus J}X_i)) \). Deci \( |A|=|P(P(I)\setminus\{\emptyset\} )|=2^{2^n-1} \).
Pentru \( |B| \) avem bijectia \( g:M\to B \), unde \( M=\{ X\in P(P(I)\setminus\{\emptyset\} )\mid J\not\subset L\forall J,L\in X\} \), data de \( X\mapsto\cup_{J\in X}(\cap_{i\in J}X_i) \). Deci \( |B|=|M| \).
Probabil ca nu exista formula exacta pt. \( |B| \) dar ar fi interesant sa gasim estimari. O margine superioara e bineinteles \( 2^{2^n-1} \). Pt. margini inferioare observam ca \( M\supseteq\cup_{k=1}^nP(P_k(I)) \), de unde rezulta ca \( |B|=|M|\geq S:=\sum_{k=1}^n2^{C_n^k} \). Pt. \( n \) mare singurii termeni ai sumei \( S \) cu contributie importanta sunt cel pt. \( k=\frac n2 \) cand \( n \) e par si pt. \( k=\frac{n\pm 1}2 \) cand \( n \) e impar. Deci \( S\approx 2^{C_n^{\frac n2}} \), respectiv \( S\approx 2^{C_n^{\frac{n-1}2}}+2^{C_n^{\frac{n+1}2}}=2^{C_n^{\frac{n-1}2}+1} \). Folosind aproximatia lui Stirling \( n!\approx\sqrt{2\pi n}(\frac ne}^n \) se arata ca \( C_n^{\frac n2} \) si \( C_n^{\frac{n-1}2} \) sunt \( \approx\frac{2^{n+1}}{\sqrt{2\pi n}} \).
Prin urmare \( 2^n-1\geq\log_2|B|\geq\log_2 S\approx\frac{2^{n+1}}{\sqrt{2\pi n}} \).
Asta e tot ce pot sa fac deocamdata. Am o banuiala vaga ca \( |B|\approx S \), dar nu sunt sigur.
Are cineva vreo idee sau a mai vazut undeva problema asta? Poate ca nu sunt primul care s-a gandit la asta si undeva exista deja o estimare.