Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau autre
Partager :

Nombre de Stirling

Posté par pia_harpa (invité) 25-10-05 à 19:17

Salut! Bien qu'ayant déja expérimenté divers dénombrements de mots, colliers et autres astuces de combinatoire, je me trouve coincée par le nombre de Stirling!:
s(p,n) : nombre de surjections de A sur B (ensembles finis non vides tq A a p éléments et B a n éléments, 1<n<p )
mais aussi s(p,n) : nombre de partitions de A en n parties de A.
comment calculer s(p,1) ? s(p,p)?
comment trouver de nombre de partitions de A en n parties de A tq la partie  }x1} soit(puis ne soit pas) l'une d'entre elles?
quelle est la démo de s(p,n)=s(p-1,n-1) + n*s(p-1,n)
> j'ai pensé à énumérer toutes les partitions sans restreindre le nombre de parties afin de trouver notre énumération de parties mais ss succès pour ces questions.
> kk1 aurait-il 1 astuce à me glisser svp ?

Posté par
Titi de la TS3re : Nombre de Stirling 25-10-05 à 19:24

Je peux seuleument te donner une indication:
le nombre de partie P(E) d'un ensemble E à n eléments:
Card(P(E))=2^n.

Et le nombre de parties à p éléments dans un ensemble E à n éléments, noté Pp(E) est:
Card(Pp(E))= binôme (n,p).

Voilà avec ça tu devrais t'en sortir.@+. Titi

Posté par pia_harpa (invité)re : Nombre de Stirling 25-10-05 à 19:25

dja essayé merci qd mm !

Posté par biondo (invité)re : Nombre de Stirling 25-10-05 à 23:42

Salut,

Allez, le debut...

s(p,1) = 1

En effet, il n'y a qu'une seule surjection entre un ensemble a p elements et un ensemble a 1 element: la surjection en question envoie chaque element de l'ensemble de deparet sur l'unique element de l'ensemble d'arrivee.


s(p,p) = p!

En effet, une surjection de A vers B, tous deux a p elements, se definit par le choix de l'image du premier element de A parmi p elements de B, puis l'image du deuxieme element de A parmi (p-1) elements de B, etc...
Ce sont bien des surjections, et il n'y en a pas d'autres, car en fait ce sont des bijections (je te laisse le montrer/le voir).


Je te rends la main...


A+
biondo

Posté par
elhor_abdelali Correcteurre : Nombre de Stirling 26-10-05 à 06:44

Bonsoir;
Notations:
p\ge n\ge1\\A=\{x_1,..,x_p\}\hspace{5}\hspace{5}B=\{y_1,..,y_n\}\\\scr S=\left\{ f \inf B^{A}\hspace{5}/\hspace{5}f\hspace{5}surjective\right\}\hspace{5}\hspace{5}s(p,n)=Card(\scr S)\\\scr P=\{partitions\hspace{5}ordonnees\hspace{5}de\hspace{5}A\hspace{5}en\hspace{5}n\hspace{5}parties\hspace{5}non\hspace{5}vides\}

Calcul de s(p,n) (nombre de stirling):
Il est facile de voir que l'application 3$\fbox{{:}\scr S\to\scr P\\f\to({f^{-1}(\{y_1\})},..,{f^{-1}(\{y_n\})\hspace{5})} est une bijection et donc que 5$\blue\fbox{Card(\scr P)=s(p,n)}

Pour calculer 3$\fbox{Card(\scr P)} on peut faire le raisonnement combinatoire suivant:
étant donné le n-uplet 3$(p_1,..,p_n)\in{\mathbb{N}}^{*n} tel que 3$p_1+..+p_n=p,combien y a t il de partitions 3$(A_1,..,A_n) telles que 3$Card(A_i)=p_i\hspace{5}1\le i\le n\hspace{5}?
je dirais qu'il y a 3$C_{p}^{p_1} façons différentes de choisir 3$A_1 puis 3$C_{p-p_1}^{p_2} façons différentes de choisir 3$A_2 puis 3$C_{p-p_1-p_2}^{p_3} façons différentes de choisir 3$A_3 .. jusqu'à 3$C_{p-p_1-p_2-..-p_{n-1}}^{p_n} façons différentes de choisir 3$A_n
il y a donc 4$\fbox{C_{p}^{p_1}\times C_{p-p_1}^{p_2}\times C_{p-p_1-p_2}^{p_3}\times..\times C_{p-p_1-..-p_{n-1}}^{p_n}=\frac{p!}{p_1!p_2!..p_n!}} façons différentes de choisir la partition ordonnée 3$(A_1,..,A_n) et ainsi on voit que:
5$\red\fbox{Card(\scr P)=s(p,n)=\Bigsum_{(p_1,..,p_n)\in{\mathbb{N}}^{*n}\\p_1+..+p_n=p}\frac{p!}{p_1!p_2!..p_n!}}
Une seconde expression de s(p,n):
Pour simplifier l'expression ci-dessus on peut remarquer que le terme 4$\fbox{\Bigsum_{(p_1,..,p_n)\in{\mathbb{N}}^{*n}\\p_1+..+p_n=p}\frac{1}{p_1!p_2!..p_n!}} représente le coefficient de 4$\fbox{X^p} dans le développement du polynome 4$\fbox{(\Bigsum_{k=1}^{p}\frac{X^k}{k!})^n} ou encore plus astucieusement le coefficient de 4$\fbox{x^p} dans le développement en série entière de la fonction 4$\fbox{(\Bigsum_{k=1}^{+\infty}\frac{x^k}{k!})^n} c'est à dire celui de la fonction 5$\fbox{h(x)=(e^x-1)^n} et donc que ce coefficient n'est autre que 5$\fbox{\frac{h^{(p)}(0)}{p!}}
En développant h par la formule du binome on a que 4$\fbox{h(x)=\Bigsum_{k=0}^{n}(-1)^{n-k}C_{n}^{k}e^{kx}} les dérivées successives de h étant facile à calculer on voit que finalement:
5$\red\fbox{s(p,n)=\Bigsum_{k=1}^{n}(-1)^{n-k}C_{n}^{k}k^p}

Sauf erreurs bien entendu


Posté par
elhor_abdelali Correcteurre : Nombre de Stirling 26-10-05 à 22:47

Bonsoir;
Par la seconde expression on vérifie que 3$\blue\fbox{s(p,1)=1\\s(p,2)=2^p-2} et par la première que 3$\blue\fbox{s(p,p)=p!}
On vérifie également aisément en utilisant la seconde expression que:
5$\red\fbox{s(p,n)=n(s(p-1,n)+s(p-1,n-1))}

Sauf erreurs bien entendu

Posté par pac (invité)re : Nombre de Stirling 27-10-05 à 12:49

Bonjour elhor_abdelali,

Je les trouve super tes réponses! Jolies, claires, agréables à lire. Ca donne envie de faire des maths tout ça!

Pac

Posté par pac (invité)re : Nombre de Stirling 27-10-05 à 12:50

Et pas seulement pour ce topic, pour tous les topics bien sûr.

Pac

Posté par philoux (invité)re : Nombre de Stirling 27-10-05 à 12:50

je suis du même avis que pac !

tu veux pas venir faire prof chez nous, elhor ?

Philoux

Posté par
elhor_abdelali Correcteurre : Nombre de Stirling 27-10-05 à 13:14

Bonjour pac,bonjour philoux;
Je suis trés touché par votre considération et croyez moi le plaisir est pour moi.J'apprends beaucoup sur ce ce Forum et répondre à un élève en difficulté est pour moi un devoir.
Philoux,si une occasion se présente pour moi pour enseigner en france j'en serais enchanté
Merci encore.

Posté par philoux (invité)re : Nombre de Stirling 27-10-05 à 13:16

avec plaisir,

A suivre alors...

Philoux

Posté par
clemclem Posteur d'énigmesre : Nombre de Stirling 06-09-07 à 20:47

Bonjour,

Je sais je remonte un vieux topic . Mais je dois trouver une formule, un résultat plus simple que l'expression donnée :

5$\red\fbox{s(p,n)=\Bigsum_{k=0}^{n}(-1)^{k}C_{n}^{k}k^p}

Une piste?

Merci d'avance

A plus

Posté par
clemclem Posteur d'énigmesre : Nombre de Stirling 06-09-07 à 22:07

Personne?

Posté par
monrow Posteur d'énigmesre : Nombre de Stirling 06-09-07 à 22:10

Bonjour clemclem

une récurrence n'a rien fait?

Posté par
monrow Posteur d'énigmesre : Nombre de Stirling 06-09-07 à 22:15

voilà j'ai trouvé un petit truc pareil à ce que tu demandes sur un livre mais avant il demandent de montrer que: 3$S(n,p)=p(S(n-1,p-1),S(n-1,p))

Posté par
infophilere : Nombre de Stirling 20-01-08 à 14:17

Bonjour

Je découvre une fois de plus un sublime post d'ehlor !

Si on note a(n,p) le nombre de partitions de En en p parties non vides et s(n,p) le nombre de surjections de En sur Ep on peut aussi montrer que s(n,p) = p!a(n,p).

En partant de ta bijection ehlor je dirais qu'à chaque surjection on peut associer une partition de En. Et que si on prend une application qui donne la même partition alors c'est que ça vient d'une permutation donc s(n,p)=p!a(n,p).

C'est pas très bien expliqué mais c'est le seul moyen que je vois pour faire intervenir ce facteur p!

Posté par
elhor_abdelali Correcteurre : Nombre de Stirling 20-01-14 à 00:02

Curieusement une application à l'arithmétique des entiers !


on vient en particulier d'établir l'identité \Large \red\Largebox{\forall n\in\mathbb{N}^*\;,\;n!\;=\;\sum_{k=1}^n(-1)^{n-k}\;C_n^k\;k^n}

qui donne pour \Large n=p-1 où \Large p est un nombre premier , \Large \red\Largebox{(p-1)!\;=\;\sum_{k=1}^{p-1}(-1)^{p-1-k}\;C_{p-1}^k\;k^{p-1}}

soit en passant aux classes modulo \Large p et en utilisant le petit théorème de Fermat , \Large \red(p-1)!\equiv-1\;[p] sauf erreur bien entendu


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !