Les séries de puissances sur ensembles, souvent appelées "Hajime Polynomials" dans le jargon des compétitions de programmation, représentent une généralisation des polynômes où les termes sont indexés par des sous-ensembles d'un univers donné. Pour un univers univers \(U = \{1, 2, \dots, n\}\), un sous-ensemble \(S \subseteq U\) peut être associé à un monôme \(x^S\). Une série de puissances sur ensembles s'écrit alors sous la forme \(\sum_{S \subseteq U} f(S) x^S\), où \(f(S)\) est un coefficient (réel ou entier).

Opérations sur les Séries de Puissances sur Ensembles

La multiplication de deux séries de puissances sur ensembles, disons \(F(x) = \sum_{A \subseteq U} f(A) x^A\) et \(G(x) = \sum_{B \subseteq U} g(B) x^B\), aboutit à une nouvelle série \(H(x) = \sum_{S \subseteq U} h(S) x^S\). Le terme \(x^S\) dans le produit est obtenu par \(x^A \odot x^B = x^{A \odot B}\), où \(\odot\) est une opération binaire sur les ensembles. Les opérations les plus courantes pour \(\odot\) sont l'union (\(\cup\)), l'intersection (\(\cap\)), et la différence symétrique (\(\oplus\)).

Cas de l'Union (\(\odot = \cup\)) et de l'Intersection (\(\odot = \cap\))

Pour l'opération d'union, la relation entre les coefficients est \(h(S) = \sum_{A \cup B = S} f(A)g(B)\). Une computation directe de cette somme sur tous les sous-ensembles est coûteuse.

C'est là qu'intervient la Transformée de Möbius sur les Ensembles (FMT). La FMT transforme une fonction \(f\) en \(\hat{f}\), où \(\hat{f}(S) = \sum_{T \subseteq S} f(T)\). Cette transofrmation est analogue à la convolution de somme de préfixes multidimensionnelle. L'opération inverse, la transformée inverse de Möbius (IFMT), s'obtient en remplaçant les additions par des soustractions dans l'algorithme.

L'implémentation typique de la FMT pour l'union est la suivante :

for j from 0 to n-1:
  for i from 0 to (1<<n if="">> j) & 1:
      f[i ^ (1 << j)] += f[i]
</n>

L'intérêt de la FMT réside dans la relation suivante pour le produit de deux séries : \(\hat{h}(S) = \hat{f}(S) \cdot \hat{g}(S)\). En effet, \(\hat{h}(S) = \sum_{R \subseteq S} h(R) = \sum_{R \subseteq S} \sum_{A \cup B = R} f(A)g(B)\). Cette double somme équivaut à sommer \(f(A)g(B)\) sur toutes les paires \((A, B)\) telles que \(A \cup B \subseteq S\). Or, cette condition est équivalente à \(A \subseteq S\) et \(B \subseteq S\). La deuxième partie de l'égalité est \(\hat{f}(S) \cdot \hat{g}(S) = \left(\sum_{A \subseteq S} f(A)\right) \left(\sum_{B \subseteq S} g(B)\right)\), qui, par produit, somme \(f(A)g(B)\) sur toutes les paires \((A, B)\) avec \(A \subseteq S\) et \(B \subseteq S\). Les deux expressions sont donc identiques.

Après avoir calculé \(\hat{h}(S) = \hat{f}(S) \cdot \hat{g}(S)\) terme à terme, on peut retrouver \(h(S)\) en appliquant l'IFMT.

Pour l'opération d'intersection (\(\odot = \cap\)), la FMT peut être adaptée en utilisant des transformées de suffixse. Alternativement, on peut transformer le problème en utilisant le complémentaire des ensembles par rapport à l'univers \(U\).

Cas de la Différence Symétrique (\(\odot = \oplus\))

Pour l'opération de différence symétrique, on utilise la Transformée de Faisceau sur Ensembles (FWT), qui est analogue à la Transformée de Fourier Rapide (FFT).

Considérons un univers à deux éléments, représenté par les nombres binaires 00, 01, 10, 11. La FWT effectue une transformation récursive sur les bits de poids fort. Pour un niveau de récursion, la transformation est :

\hat{f}_0 = f_0 + f_1
\hat{f}_1 = f_0 - f_1

où \(f_0\) et \(f_1\) représentent les sommes des coefficients pour les nombres ayant le bit de poids fort à 0 et 1 respectivement. Cette opération s'apparente au papillon de la FFT.

L'algorithme FWT pour la différence symétrique se présente comme suit :

for mid from 2 to n step << 1:
  for i from 0 to N step mid: // N est la taille de l'univers, N = 1<<n appliqu="" array="" est="" for="" from="" ici="" inv2="" inverse="" j="" l="" mid="" mod="" n="" par="" si="" to="" u="array[i" v="array[i">

<p>Après avoir appliqué la FWT aux deux séries \(f\) et \(g\) pour obtenir \(\hat{f}\) et \(\hat{g}\), on calcule le produit \(\hat{h} = \hat{f} \cdot \hat{g}\) terme à terme. L'application de la transformée inverse de FWT (IFWT) permet ensuite d'obtenir les coefficients \(h\).</p>

<h3>Convolution de Sous-Ensembles</h3>

<p>Une forme spécifique de convolution est la convolution de sous-ensembles, définie par \(h(S) = \sum_{T \subseteq S} f(T)g(S \setminus T)\). La condition clé ici est que les deux sous-ensembles \(T\) et \(S \setminus T\) sont disjoints et leur union est \(S\). Une approche pour résoudre ce type de convolution consiste à séparer le calcul en fonction de la taille des ensembles, puis à appliquer la transformée FMT pour l'union aux coefficients appropriés.</p>

<h3>Fonctions Exponentielle et Logarithmique</h3>

<p>Les extensions des fonctions exponentielle et logarithmique aux séries de puissances sur ensembles sont des sujets plus avancés et ne sont pas détaillés ici.</p></n>