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... Maths sup ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Partager :

dénombrements

Posté par
mellepapillon 03-12-05 à 20:00

bonsoir,
J'ai un gros problème avec mon dm sur le dénombrement, j'espère que vous aller m'éclairer

la situation:
une sérrure de sécurité possède n boutons numérotés de 1 à n et n supérieur ou égal à 1
une n-combinaison consiste à pousser dans un certain ordre tous les boutons, chaque bouton n'est poussé qu'une seul fois mais il est possible de pousser simultanément plusieurs boutons.
la modélisation est effectuée de la manière suivante: pour une valeur donnée de l'entier n An={1,2....n}. Par définition, une n-combinaison est une liste ordonnée (P1,P2....,Pj) de j parties P1,P2,...Pj de l'ensemble An (1<=j<=n); ces parties Pj, 1<=i<=j, sont deux à deux disjointes, différentes de la partie vide et leur réunion est égale à An, on note an le nombre de n-combinaisons.
exemple, n=1 une seule 1-combinaisons a1=1
n=2 il y a trois 2-combinaisons a2=3 ({1},{2}), ({2},{1}), ({1,2})

D'abord y a des petites questions qui ne m'ont pas posés de problème, je les passe, passons à ce qui me pose problème:

Soit S une n-combinaison ( n est un entier naturel non nul fixé)
Combien y a t il de choix possibles pour la partie P1 lorqu'elle est de cardinal k?
là j'ai répondu "k parmi n" ( ou peut se lire B(n,k) )
ensuite ça se corse

Pour une partie Pi fixée de cardinal k avec k entre 1 et n compris , combien y a til de n-combinaisons S dot le premier terme est Pi ( ce résultat sera exprimé à l'aide des réels ap)
là je ne vois pas comment je dois exprimé tout les cas possibles, car les parties d'après doivent ranger les n-k élements restants, mais comment je dois différencier les parties ayant 1 éléments, celles 2 ,ect...

ensuite: exprimer an en fonction de a0 ,a1, ...a(n-1).

Retrouver les valeurs obtenues pour a2 et a3 ( on avait trouver a3 = 13  dans une question préliminaire, si je n'ai pas fait d'erreur) et calculer a4

On note bn= an/ n!. Justifier pour tout entier naturel non nul n: bn= somme de k=1 à n de b(n-k) sur k!

merci d'avance pour votre aide
et bonne soirée
Marie

Posté par
elhor_abdelali Correcteurre:dénombrements 04-12-05 à 01:03

Bonsoir mellepapillon;
Disons que la question vise à te faire trouver une relation de récurrence entre a_n et les (a_k)_{1\le k\le n}.
Le raisonnement est le suivant:
on compte les n-combinaisons suivant le cardinal k de leur première partie k=1..n
-pour k=1 il y'en a (c'est à dire les n-combinaisons débutant par un singleton) C_{n}^{1}a_{n-1} le C_{n}^{1} représente le nombre de choix possibles d'un singleton de A_n=\{1,..,n\} et le a_{n-1} représente le nombre de façons possibles pour compléter un singleton en une n-combinaison (qui débute par ce singleton).
-tu vois alors que pour k=i il y'a exactement C_{n}^{i}a_{n-i} n-combinaisons débutant par une partie à i éléments.
-jusqu'à k=n et il y'a 1 façon de choisir une n-combinaison débutant par une partie à n éléments c'est la n-combinaison (A_n)=(\{1,..,n\}).
On peut alors écrire que 3$\fbox{a_1=1\\(\forall n\ge2)\hspace{5}a_n=1+\Bigsum_{k=1}^{n-1}C_{n}^{k}a_{n-k}=1+\Bigsum_{k=1}^{n-1}C_{n}^{k}a_k}
ou encore en convenant que 2$\blue\fbox{a_0=1} que 4$\blue\fbox{(\forall n\ge1)\hspace{5}a_n=\Bigsum_{k=0}^{n-1}C_{n}^{k}a_k} on trouve bien \fbox{a_2=C_{2}^{0}\times1+C_{2}^{1}\times1=3} , \fbox{a_3=C_{3}^{0}\times1+C_{3}^{1}\times1+C_{3}^{2}\times3=13} et \fbox{a_4=C_{4}^{0}\times1+C_{4}^{1}\times1+C_{4}^{2}\times3+C_{4}^{3}\times13=75}
tu vois bien aussi que 4$\fbox{(\forall n\ge1)\hspace{5}\frac{a_n}{n!}=\Bigsum_{k=0}^{n-1}\frac{1}{k!(n-k)!}a_k} donc si on note \fbox{b_n=\frac{a_n}{n!}} on a bien 4$\blue\fbox{b_0=1\\(\forall n\ge1)\hspace{5}b_n=\Bigsum_{k=0}^{n-1}\frac{b_k}{(n-k)!}=\Bigsum_{k=1}^{n}\frac{b_{n-k}}{k!}}

Sauf erreurs bien entendu

Posté par
mellepapillonre : dénombrements 04-12-05 à 10:33

merci beaucoup, j'étudie tout ça dans une heure! et je dis si je comprends tout, encore merci pour votre aide , bonne journée

Posté par
mellepapillonre : dénombrements 04-12-05 à 16:50

J'ai tout compris pour ce point là, maintenant c'est la suite qui me pose problème...les dénombrements c'est vraiment pas mon fort.

On note an^k le nombre de n-combinaisons comportant k parties.
J'ai dit que an^1=1 et an^n=n! ( j'espère que j'ai bien compté )
Ensuite je dois préciser la valeur de an^k et là je bloque.
Je vois pas comment on pourrait les compter puisque les k parties n'ont pas forcément le même nombre d'éléments...

Par la suite on doit démontrer la relation a(n+1)^(p+1) = (p+1)(an^(p+1)+ an^p) ( on pourra pour cela considérer les n+1 combinaisons comportant p+1 parties en distinguant celles qui possèdent le singleton {n+1} et celles qui ne le possédents pas)

ensuite on pose la suitr S(n,p)= somme de k=0 à p de (-1) ^(p-k) fois (Cp^k) k^n

il faut montrer que S(n,p+1)=-S(n,p)+1/(p+1) S(n+1,p+1), en déduire S(1,k) pour k>0

Merci beaucoup d'avance, ça me géne de demander tout ça mais je comprends vraiment pas comment je dois penser...Merci.
Bonne fin d'après midi ,Mademoiselle Papillon


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 !