Nombre de partitions d'un ensemble

BMaths

Bonjour,
dans un exercice, on pose $S(n,k)$ le nombre de partitiosn de l'ensemble $1,n$ à $k$ éléments.
Je dois prouver que $S(n,k)=S(n-1,k-1)+kS(n-1,k)$.
Une indication est de distinguer les partitions selon qu'il y a le singleton $\{n\}$ ou pas.

Avant de faire la démonstration, j'essaye de comprendre ce qu'il se passe pour de petites valeurs.
Prenons par exemple $E=1,4=\{1,2,3,4\}$. Disons que l'on souhaite partitionner E en 3 parties.
Il s'agit donc de trouver des sous-ensembles disjoints de $E$ de sorte que la réunion donne $E$.
Je cherche les sous-ensembles de $E$. Je trouve :
1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234
Je dois donc choisir 3 sous-ensembles parmi les 16 ci-dessus dont la réunion donne E.

La formule dit que le nombre de partitions de $\{1,2,3,4\}$ en 3 parties est égale au nombre de partitions de $\{1,2,3\}$ en 2 parties plus 2 fois le nombre de $\{1,2,3\}$ en 3 parties.

Je ne vois pas comment l'établir
Pouvez-vous m'aider ?
D'avance merci.

gb

Bonjour

Il faut se servir de l'indication:
— ou un des sous-ensembles de la partition est \(\lbrace4\rbrace\) et il te reste à choisir…
— ou aucun es sous-ensembles de la partition n'est \(\lbrace4\rbrace\) et, en supprimant l'élément \(4\) du sous-ensembles auquel il appartient, tu obtiens…

BMaths

Bonsoir gb,

si l'un des sous-ensembles de la partition est $\{4\}$ alors il reste à choisir 2 parties parmi les 15 sous-ensembles sachant que ces 2 parties restantes doivent former une partition de \{1,2,3\} en 2 parties : il y en a donc $S(3,2)$.
Pour le point suivant, j'ai plus de mal.

gb

Les trois ensembles \(\lbrace 1 \rbrace\), \(\lbrace 2,4 \rbrace\), \(\lbrace 3 \rbrace\) constituent une partition de \(\lbrace 1,2,3,4 \rbrace\) que l'on peut obtenir à partir de la partition de \(\lbrace 1,2,3 \rbrace\) constituée de \(\lbrace 1 \rbrace\), \(\lbrace 2 \rbrace\) et \(\lbrace 3 \rbrace\).

BMaths

Ah.
Si aucun des sous-ensembles n'est $\{4\}$, en le supprimant de l'ensemble dans lequel il appartient, on obtient une partition $\{1,2,3\}$ en 3 parties, c'est-à-dire $S(3,3)$.

D'où $S(n-1,k)$.
Et comment expliquer le k devant ?

GaBuZoMeu

Où mets tu le $n$ quand tu veux fabriquer une partition de $\{1,\ldots,n\}$ en $k$ parties à partir d'une partition de $\{1,\ldots,n-1\}$ en $k$ parties ?

Kcg

Pour constituer des partitions de l'ensemble {1,2,...,n} à k éléments, on peut :
- en considérant un élément x de {1,...,n} ,constitué toutes les partitions à (k-1) éléments de l'ensemble {1,..,n}\{x} soit $S(n-1,k-1)$ possibilité ; et pour chaque partition à (k-1) éléments,ajouter le singleton {x} pour former une partition à k éléments ,on peut ajouter le singleton {x} d'une seule façon. Donc finalement on aura $S(n-1,k-1)$ possibilité ;
- en considérant le même éléments x, on constitue toutes les partitions de {1,...n}\{x} à k éléments, soit $S(n-1,k)$ possibilité , pour chaque partition , on insère l'élément x dans un ensemble de cette partition (chaque partition est constitué de k sous ensemble de {1,...,n}\{x}) il y'a donc k possibilité d'insérer x. Donc on a $k S(n-1,k)$ possibilité.
Les deux cas étant disjoints et complémentaire, car pour le premier cas les partitions ont l'élément x comme un ensemble ({x}) et pour le second cas x est un élément d'un ensemble.
On conclut que $S(n,k)= S(n-1,k-1) + kS(n-1,k)$.
Ma rédaction est un peu lourde mais l'idée est là.

BMaths

Je voudrais en fait le faire avec n=3 ou n=4, parce que je trouve que l'on voit bien ce qu'il se passe avant de passer au cas général.

gb

Tu veux une partition de \(\lbrace1,2,3,4\rbrace\) en trois sous-ensembles.

Ou bien tu pars d'une partition de \(\lbrace1,2,3\rbrace\) en deux sous-ensembles, et tu rajoutes le singleton \(\lbrace4\rbrace\) pour obtenir ta partition de \(\lbrace1,2,3,4\rbrace\) :
\begin{align*}
\lbrace1\rbrace, \lbrace2,3\rbrace &\to \lbrace1\rbrace, \lbrace2,3\rbrace, \lbrace4\rbrace \\
\lbrace1,2\rbrace, \lbrace3\rbrace &\to \lbrace1,2\rbrace, \lbrace3\rbrace, \lbrace4\rbrace \\
\lbrace1,3\rbrace, \lbrace3\rbrace &\to \lbrace1,3\rbrace, \lbrace3\rbrace, \lbrace4\rbrace
\end{align*}

Ou bien tu pars d'une partition de \(\lbrace1,2,3\rbrace\) en trois sous-ensembles, et tu rajoutes l'élément \(4\) à un de ces sous ensembles pour obtenir ta partition de \(\lbrace1,2,3,4\rbrace\) :
\[\lbrace1\rbrace, \lbrace2\rbrace, \lbrace3\rbrace \to
\begin{cases}
\lbrace1,4\rbrace, \lbrace2\rbrace, \lbrace3\rbrace \\
\lbrace1\rbrace, \lbrace2,4\rbrace, \lbrace3\rbrace \\
\lbrace1\rbrace, \lbrace2\rbrace, \lbrace3,4\rbrace
\end{cases}\]

BMaths

Merci, je pense avoir compris.
On considère $S(n,k)$ le nombre de partition de $1,n$ en $k$ parties.
On va considérer les partitions dont l'une des parties est réduite à $\{n\}$ (cas 1), puis les partitions dont aucune n'est réduite à $\{n\}$ (cas 2). Ces deux cas étant disjoints.

Dans le cas 1 :
Pour les partitons dont l'une des parties est réduite à $\{n\}$, si l'on supprime cette partie, on obtient une partition de $1,n-1$ en $k-1$ parties. Par définition, il y en a $S(n-1,k-1)$.

Dans le cas 2 :
Pour les partitions dont aucune n'est réduite à $\{n\}$, si l'on supprime l'élément $n$ de la partie à laquelle il appartient, alors on obtient une partition de $1,n-1$ en $k$ parties. Par définition, il y en a $S(n-1,k)$. Pour obtenir une partition de $1,n$, il reste à insérer l'élément $n$ dans une des parties et il y a k possibilités. Ce qui donne $kS(n-1,k)$.

Par conséquent, $S(n,k)=S(n-1,k-1)+kS(n-1,k)$.

BMaths

Bonjour,

je reviens à cet exercice en me demandant quelles sont les différentes valeurs ci-dessous ?
1) S(n,0)
2) S(0,0)
3) S(n,1)

Pour le 1) je dirais, on cherche une partition de E_n en 0 parties, impossible car aucune des parties ne peut être nulles.
Pour le 2), je dirais qu'on cherche une partition d'un ensemble à 0 élément, c-à-d l'ensemble vide. Impossible aussi ! Pour les mêmes raisons que ci-dessus.
Et pour le 3, il n'y a qu'une seule façon de partitionner E_n en 1 partie.

Qu'en pensez-vous ?