Petit denombrement et permutation

[Anonyme]

bonjour,

qqn pourrait-il me dire quelle est la proba qu apres 1 permutation, aucun
des N nombres ne se trouve a sa place d origine.

EX1: on considere {1,2,3,4}
on compte {2,3,4,1} mais on ne compte pas {1,3,4,2} car le "1" est tjs en
premiere place

EX2: {1,2,3}
on compte {2,3,1}, {3,1,2}
on ne compte pas {1,2,3} ni {1,3,2} ni {3,2,1} ni {2,1,3}
donc proba de 1/3


J espere que j ai ete assez clair.

Merci bien

Antoine

[Anonyme]

Salut

> bonjour,
>
> qqn pourrait-il me dire quelle est la proba qu apres 1 permutation, aucun
> des N nombres ne se trouve a sa place d origine.
>

Si je me gourre pas dans le calcul la formule du crible te permet de dire
que ta probabilité vaut:
sum((-1)^k/k!, k=2..N).

[Anonyme]

maison wrote:

> bonjour,
>
> qqn pourrait-il me dire quelle est la proba qu apres 1 permutation, aucun
> des N nombres ne se trouve a sa place d origine.
>
> EX1: on considere {1,2,3,4}
> on compte {2,3,4,1} mais on ne compte pas {1,3,4,2} car le "1" est tjs en
> premiere place
>
> EX2: {1,2,3}
> on compte {2,3,1}, {3,1,2}
> on ne compte pas {1,2,3} ni {1,3,2} ni {3,2,1} ni {2,1,3}
> donc proba de 1/3
>
>
> J espere que j ai ete assez clair.

Voui. Il s'agit des DERANGEMENTS de Sigma_n. On peut trouver un certain
nombre de relations de recurrences, en particulier

D_n + binom(n,1)*D_(n-1) + ... + binom(n,n)*D_0=n!

qui revient a classer les permutations en fonction du nombre de leurs points
fixes.

Apres division par n!, on en deduit que la serie generatrice S de D_n
(sum(D_n/n! X^n)) verifie S(X)=1/(1-X)exp(-X), ce qui, redeveloppe par un
produit de Cauchy, donne :

D_n=n! * sum((-1)^p/p!,p=0..n)

Il n'est pas ininteressant de constater que D_n/n! tend vers 1/e lorsque n
tend vers l'infini. D'ou une "proportion etrange" de plus de notre univers
(un nombre "bigre", comme disait F. Pohl)

\bye

--

Nicolas FRANCOIS
http://nicolas.francois.free.fr

We are the Micro$oft.
Resistance is futile.
You will be assimilated.