Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Nombre de n-combinaisons

Posté par
Thoy
28-11-09 à 17:18

Re-bonjour

Une serrure de sécurité possède n boutons numérotés de 1 à n. Une n-combinaison consiste à pousser dans un certain ordre tous les boutons. Chaque bouton n'est poussé qu'une seule fois mais il est possible de pousser simultanément plusieurs boutons.
La modélisation est effectuée de la façon suivante : pour tout entier n1, on appalle n-combinaison toute suite ordonnée (P1,P2,P3...Pj) de j parties P1,P2,...Pj de l'ensemble [1,n] (1jn ; ces parties sont toutes non vides, deux à deux disjointes et leur réunion est égale à l'ensemble [1,n]. On note an le nombre de n-combinaisons.
On conviendra que a0=1.

1) Je trouve n! n-combinaisons pour lesquelles les boutons sont poussés l'un après l'autre.
par ex pour je trouve a3=13

2)Soit n1. et S=(P1,P2...Pj) une n-combiansion.
- Soit k[1,n]. Combien ya-t-il de choix possibles pour la partie P1 lorsque l'on impose que CardP1=k ?

Je trouve 2n-1.

- Combien ya-t-il de n-combinaisons S dont le premier élément P1 possède k éléments ?

Pour un P1 donné à k touches appuyées. Pour P2, il reste n-k touches à appuyer :
on appuie sur une seule touche : n-k choix
on appuie sur 2 touches simultanément : 2 parmi n-k choix
...
on appuie sur n-k touches simultanéments : 1 seul choix
donc
sum( p=1 à n-k (C(p:n-k)) choix possibles

Mais en fait je ne suis sûre de rien du tout :/

- Exprimer an en fonction de a0,a1...an-1.

3) Pour tout entier n, on pose bn=an/n!
Démontrer que l'on a n1, bn= sum(k=1 à n (bn-k/k!)))

J'ai essayé de travailler la somme je n'en tire rien...

4) Démontrer que x réel et n entier on a
exp(x) sum (k=0 à n (xk/k!)
En déduire
n entier, bn1/(ln2)n


Merci pour votre aide

Posté par
Thoy
re : Nombre de n-combinaisons 28-11-09 à 19:57

Pouvez vous m'aider? ...

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 28-11-09 à 21:48

Bonjour,

1) Je trouve aussi n! pour le nombre de n-combinaisons pour lesquelles les boutons sont poussés l'un après l'autre

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 28-11-09 à 21:49

2)a) Combien y a-t-il de choix possibles pour la partie P1 lorsque l'on impose que Card(P1)=k ?

Il me semble que la réponse est 3$C_n^k={n\choose k}

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 28-11-09 à 22:02

2)b) Combien y a-t-il de n-combinaisons S dont le premier élément P1 possède k éléments ?

On choisit les membres de P1 : 3${n\choose k} possibilités
On construit le reste de la suite : 3$a_{n-k} possibilités
Le nombre recherché est donc 3$\fbox{{n\choose k}\,a_{n-k}}

2)c) Exprimer an en fonction de a0,a1...an-1

3$\fbox{a_n=\Bigsum_{1\le k\le n}{n\choose k}\,a_{n-k}}

3) "Pour tout entier n, on pose bn=an/n! Démontrer que l'on a n>=1, bn= sum(k=1 à n (bn-k/k!)))"

On déduit de la question précédente que :
3$n!\,b_n = \Bigsum_{1\le k\le n}{n\choose k}\,(n-k)!\,b_{n-k}
3$n!\,b_n = \Bigsum_{1\le k\le n}\frac{n!}{k!(n-k)!}\,(n-k)!\,b_{n-k}
3$\fbox{b_n = \Bigsum_{1\le k\le n}\frac{b_{n-k}}{k!}}

Posté par
Thoy
re : Nombre de n-combinaisons 28-11-09 à 22:41

Bonsoir Olivier

Voila ce que j'ai fait pour la question 2a :

Citation :
Pour un P1 donné à k touches appuyées. Pour P2, il reste n-k touches à appuyer :
on appuie sur une seule touche : n-k choix
on appuie sur 2 touches simultanément : 2 parmi n-k choix
...
on appuie sur n-k touches simultanéments : 1 seul choix
donc
sum( p=1 à n-k (C(p:n-k)) choix possibles



Simplement je ne suis pas d'accord avec toi, car en effet, on peut aussi appuyer simultanément sur les touches, non ??

Posté par
Thoy
re : Nombre de n-combinaisons 29-11-09 à 12:21

Olivier je compte sur toi pour m'expliquer dès que tu passes sur le forum quelques instants

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 29-11-09 à 15:55

J'ai comme un doute. Cet "Olivier" dont tu parles, est-ce moi (Nicolas) ?

Pour 2)a), je ne comprends pas ton avant-dernier message. Card(P1)=k signifie qu'on appuie simultanément sur k touches la première fois, non ?

Posté par
Thoy
re : Nombre de n-combinaisons 29-11-09 à 16:26

Pardon je parlais à mon frère quand j'écrivais ce message, il s'appelle Olivier, excuse-moi

Pour moi Card(P1)=k c'est le nombre de façons de toucher k touches...
Donc une à une, ou 2 simultanément et n-k-2 autres succesives... non?

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 29-11-09 à 16:44

Il me semble que tu n'as pas compris la modélisation indiquée par l'énoncé.

P1 est l'ensemble des touches appuyées ensemble à la première pression.
P2 est l'ensemble des touches appuyées ensemble à la seconde pression.
Etc...

Posté par
Thoy
re : Nombre de n-combinaisons 29-11-09 à 17:20

Effectivement, merci...

J'ai réussi la démonstration de l'exponentielle (par une récurrence) simplement je ne retrouve pas l'inégalité suivante, as-tu une idée?

Posté par
Thoy
re : Nombre de n-combinaisons 29-11-09 à 17:58

Et j'ai une autre question, pourrais-tu expliciter la 2c) ?

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 29-11-09 à 18:24

2)c) Exprimer an en fonction de a0,a1...an-1

Soit S une combinaison quelconque.
Son P1 a 1, 2, ... ou n éléments.
Donc
3$a_n=\Bigsum_{1\le k\le n}\mathrm{(nb\ de\ combinaisons\ dont\ P1\ a\ k\ elements)}

3$a_n=\Bigsum_{1\le k\le n}\mathrm{(nb\ de\ facons\ de\ former\ un\ P1\ de\ k\ elements)(nb\ de\ combinaisons\ que\ l'on\ peut\ former\ avec\ les\ n-k\ elements\ restants)}

3$\fbox{a_n=\Bigsum_{1\le k\le n}{n\choose k}\,a_{n-k}}

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 29-11-09 à 19:41

4)b)
Tu peux facilement le démontrer par récurrence.
Le cœur de la démonstration est le suivant.

3$b_n = \Bigsum_{1\le k\le n}\frac{b_{n-k}}{k!} \le \Bigsum_{1\le k\le n}\frac{\left( \frac{1}{\ln 2} \right)^{n-k}}{k!} = \frac{1}{\left(\ln 2\right)^n}\Bigsum_{1\le k\le n}\frac{\left(\ln 2\right)^k}{k!} \le \frac{1}{\left(\ln 2\right)^n}\left(e^{\ln 2}-1\right) = \frac{1}{\left(\ln 2\right)^n}

Posté par
Thoy
re : Nombre de n-combinaisons 29-11-09 à 23:09

Ah je comprend mieux pour la 2c maintenant!

D'accord mais je ne cmprend pas réellement d'où sortent les inégalités... Je vais essayer d'approfondire ça, mais je ne vois pas tellement...

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 30-11-09 à 06:40

La première découle de l'hypothèse de récurrence.
Et la seconde de la question précédente.

Posté par
Thoy
re : Nombre de n-combinaisons 30-11-09 à 21:04

Je comprend bien le raisonnement, mais à rédiger, je suppose que c'est vrai au rang n-k je démontre que c'est vrai au rang n c'est ça ?

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 02-12-09 à 07:19

Il y a chez moi un problème d'affichage : ce sont bien des signes \le qui doivent apparaître sous les \Bigsum.

Ici, il faut supposer la propriété vraie pour b0, b1, ..., b(n-1), et démontrer qu'elle est vraie pour bn.

Nicolas

Posté par
Nicolas_75 Correcteur
re : Nombre de n-combinaisons 02-12-09 à 07:19

(des signes )

Posté par
esta-fette
re : Nombre de n-combinaisons 02-12-09 à 07:57

bonjour.

Je trouve le problème intéressant.
Si j'ai un peu de temps libre, j'essaierai de participer....



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 1674 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 !