Cardinal d'un ensemble

  Par exemple, soit f(n) le nombre de sous-ensembles distincts de nombres entiers dans l'intervalle [1, n] qui ne contiennent pas deux nombres entiers consécutifs. 

Par exemple, avec n = 4, nous obtenons ∅, { 1 }, { 2 }, { 3 }, { 4 }, { 1, 3 }, { 1, 4 }, { 2, 4 }, et donc f(4) = 8.

 Il s'avère que f(n) est le nème nombre de Fibonacci, qui peut être exprimé sous la forme « fermée » suivante :

${\displaystyle �(�)=\frac{{�}^{�}}{\sqrt{5}}-\frac{(1-�{)}^{�}}{\sqrt{5}}}$

où Φ = (1 + √5)/2, est le nombre d'or. Cependant, étant donné que nous considérons des ensembles de nombres entiers, la présence du √5 dans le résultat peut être considérée comme inesthétique d'un point de vue combinatoire. Aussi f(n) peut-il être exprimé par une relation de récurrence :

f(n) = f(n - 1) + f (n - 2)

ce qui peut être plus satisfaisant (d'un point de vue purement combinatoire), puisque la relation montre plus clairement comment le résultat a été trouvé.

Dans certains cas, un équivalent asymptotique g de f,

f(n)~g(n) quand n tend vers l'infini

où g est une fonction « familière », permet d'obtenir une bonne approximation de f. Une fonction asymptotique simple peut être préférable à une formule « fermée » extrêmement compliquée et qui informe peu sur le comportement du nombre d'objets. Dans l'exemple ci-dessus, un équivalent asymptotique serait :

${\displaystyle �(�)\sim \frac{{�}^{�}}{\sqrt{5}}}$

quand n devient grand.

Une autre approche est celle des séries entières. f(n) peut être exprimé par une série entière formelle, appelée fonction génératrice de f, qui peut être le plus couramment :

• la fonction génératrice ordinaire

• ou la fonction génératrice exponentielle

Une fois déterminée, la fonction génératrice peut permettre d'obtenir toutes les informations fournies par les approches précédentes. En outre, les diverses opérations usuelles comme l'addition, la multiplication, la dérivation, etc., ont une signification combinatoire ; et ceci permet de prolonger des résultats d'un problème combinatoire afin de résoudre d'autres problèmes.

Combinatoire — Wikipédia (wikipedia.org)

• Un produit cartésien A × B est vide si et seulement si A ou B est vide. En particulier : pour tout ensemble ${\displaystyle �}$,${\displaystyle \varnothing \times �=�\times \varnothing =\varnothing }$.
• Les deux facteurs d'un produit sont entièrement déterminés par ce produit, s'il est non vide. Plus précisément : si ${\displaystyle �\ne \varnothing }$ alors ${\displaystyle �\in �\iff \mathrm{\exists }�(�,�)\in �\times �}$ et de même, si ${\displaystyle �\ne \varnothing }$ alors ${\displaystyle �\in �\iff \mathrm{\exists }�(�,�)\in �\times �}$.
• Si A et B sont finis, alors le cardinal de A × B est égal au produit des cardinaux de A et de B

Produit cartésien — Wikipédia (wikipedia.org)