Nr. de expresii obtinute folosind reuniunea si intersectia

[lasamasatelas]

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.

[Cezar Lupu]

Foarte misto problema, Nicu! Eu sincer n-am vazut-o nicaieri, dar nu sunt un guru in ale combinatoricii. Eu te-as sfatui s-o traduci in enegleza si s-o dai la AMM. Uite, ii trimiti un e-mail lui Doug Hensley pentru asta la adresa: dhensley@math.tamu.edu.