Menu Close

Question-146987




Question Number 146987 by KONE last updated on 16/Jul/21
Answered by Olaf_Thorendsen last updated on 17/Jul/21
1)  Supposons que a = 0  on  a donc les solutions suivantes :  (0,0,n)  (0,1,n−1)  (0,2,n−2)  ...  (0,n−1,1)  (0,n,0)  Soit (n+1) triplets solutions.    Supposons que a = 1  on  a donc les solutions suivantes :  (1,0,n−1)  (1,1,n−2)  (1,2,n−3)  ...  (1,n−2,1)  (1,n−1,0)  Soit n triplets solutions.    Pour a = 2, on a (n−1) triplets  solutions et bien sur, pour a = n, on a  une seule solution (n,0,0).    Le nombre total de triplets solutions  est donc :  (n+1)+(n)+(n−1)+...+1  = Σ_(k=0) ^(n+1) k = (((n+1)(n+2))/2)    2)  Combien y a−t−il de suites  croissantes de p termes de [[1,n]] ?    On etablit une suite de la maniere   suivante. Tant que les entiers de 1 a k  ont pour image 1 on ecrit k “1” qui se  suivent et on termine par une cloison.  Si aucun entier n′a pour image 1, on  commence par une cloison.    On poursuit avec autant de 2 qu′il  y a d′entiers suivants qui ont pour  image 2 puis une cloison. Si aucun  entier n′a pour image 2 on met  simplement une cloison.    Et ainsi de suite sauf que lorsqu′on  arrive aux derniers entiers qui ont  pour image n il est inutile de   terminer par une cloison.    Un exemple  :    Soit l′application de [[1,4]] dans [[1,5]]  telle que f(1) = 1, f(2) = 1, f(3) = 3,   f(4) = 5. Elle est representee par  11//3//5.    Si f(1) = f(2) = 2 et f(3) = f(4) = 4, la  representation est /22//44/    On a donc ecrit n nombres et p−1  cloisons donc n+p−1 symboles.    Une application croissante   est determinee par la place des p−1  cloisons. Le nombre d′applications  croissates est donc C_(p−1) ^(n+p−1) .    Dans notre cas particulier, on a une  suite de n nombres donc p = n. Et le  nombre de suites croissantes de n  termes de [[1,n]] est alors :  C_(n−1) ^(2n−1) .    Par exemple, pour les 5−uplets de  nombres de 1 a 5, il y en a :  C_(5−1) ^(2×5−1)  = C_4 ^9  = ((9!)/(4!5!)) = 126 dont les 5  nombres sont ranges dans l′ordre  croissant.
$$\left.\mathrm{1}\right) \\ $$$$\mathrm{Supposons}\:\mathrm{que}\:{a}\:=\:\mathrm{0} \\ $$$$\mathrm{on}\:\:\mathrm{a}\:\mathrm{donc}\:\mathrm{les}\:\mathrm{solutions}\:\mathrm{suivantes}\:: \\ $$$$\left(\mathrm{0},\mathrm{0},{n}\right) \\ $$$$\left(\mathrm{0},\mathrm{1},{n}−\mathrm{1}\right) \\ $$$$\left(\mathrm{0},\mathrm{2},{n}−\mathrm{2}\right) \\ $$$$… \\ $$$$\left(\mathrm{0},{n}−\mathrm{1},\mathrm{1}\right) \\ $$$$\left(\mathrm{0},{n},\mathrm{0}\right) \\ $$$$\mathrm{Soit}\:\left({n}+\mathrm{1}\right)\:\mathrm{triplets}\:\mathrm{solutions}. \\ $$$$ \\ $$$$\mathrm{Supposons}\:\mathrm{que}\:{a}\:=\:\mathrm{1} \\ $$$$\mathrm{on}\:\:\mathrm{a}\:\mathrm{donc}\:\mathrm{les}\:\mathrm{solutions}\:\mathrm{suivantes}\:: \\ $$$$\left(\mathrm{1},\mathrm{0},{n}−\mathrm{1}\right) \\ $$$$\left(\mathrm{1},\mathrm{1},{n}−\mathrm{2}\right) \\ $$$$\left(\mathrm{1},\mathrm{2},{n}−\mathrm{3}\right) \\ $$$$… \\ $$$$\left(\mathrm{1},{n}−\mathrm{2},\mathrm{1}\right) \\ $$$$\left(\mathrm{1},{n}−\mathrm{1},\mathrm{0}\right) \\ $$$$\mathrm{Soit}\:{n}\:\mathrm{triplets}\:\mathrm{solutions}. \\ $$$$ \\ $$$$\mathrm{Pour}\:{a}\:=\:\mathrm{2},\:\mathrm{on}\:{a}\:\left({n}−\mathrm{1}\right)\:\mathrm{triplets} \\ $$$$\mathrm{solutions}\:\mathrm{et}\:\mathrm{bien}\:\mathrm{sur},\:\mathrm{pour}\:{a}\:=\:{n},\:\mathrm{on}\:\mathrm{a} \\ $$$$\mathrm{une}\:\mathrm{seule}\:\mathrm{solution}\:\left({n},\mathrm{0},\mathrm{0}\right). \\ $$$$ \\ $$$$\mathrm{Le}\:\mathrm{nombre}\:\mathrm{total}\:\mathrm{de}\:\mathrm{triplets}\:\mathrm{solutions} \\ $$$$\mathrm{est}\:\mathrm{donc}\:: \\ $$$$\left({n}+\mathrm{1}\right)+\left({n}\right)+\left({n}−\mathrm{1}\right)+…+\mathrm{1} \\ $$$$=\:\underset{{k}=\mathrm{0}} {\overset{{n}+\mathrm{1}} {\sum}}{k}\:=\:\frac{\left({n}+\mathrm{1}\right)\left({n}+\mathrm{2}\right)}{\mathrm{2}} \\ $$$$ \\ $$$$\left.\mathrm{2}\right) \\ $$$$\mathrm{Combien}\:\mathrm{y}\:\mathrm{a}−\mathrm{t}−\mathrm{il}\:\mathrm{de}\:\mathrm{suites} \\ $$$$\mathrm{croissantes}\:\mathrm{de}\:{p}\:\mathrm{termes}\:\mathrm{de}\:\left[\left[\mathrm{1},{n}\right]\right]\:? \\ $$$$ \\ $$$$\mathrm{On}\:\mathrm{etablit}\:\mathrm{une}\:\mathrm{suite}\:\mathrm{de}\:\mathrm{la}\:\mathrm{maniere}\: \\ $$$$\mathrm{suivante}.\:\mathrm{Tant}\:\mathrm{que}\:\mathrm{les}\:\mathrm{entiers}\:\mathrm{de}\:\mathrm{1}\:\mathrm{a}\:{k} \\ $$$$\mathrm{ont}\:\mathrm{pour}\:\mathrm{image}\:\mathrm{1}\:\mathrm{on}\:\mathrm{ecrit}\:{k}\:“\mathrm{1}''\:\mathrm{qui}\:\mathrm{se} \\ $$$$\mathrm{suivent}\:\mathrm{et}\:\mathrm{on}\:\mathrm{termine}\:\mathrm{par}\:\mathrm{une}\:\mathrm{cloison}. \\ $$$$\mathrm{Si}\:\mathrm{aucun}\:\mathrm{entier}\:\mathrm{n}'\mathrm{a}\:\mathrm{pour}\:\mathrm{image}\:\mathrm{1},\:\mathrm{on} \\ $$$$\mathrm{commence}\:\mathrm{par}\:\mathrm{une}\:\mathrm{cloison}. \\ $$$$ \\ $$$$\mathrm{On}\:\mathrm{poursuit}\:\mathrm{avec}\:\mathrm{autant}\:\mathrm{de}\:\mathrm{2}\:\mathrm{qu}'\mathrm{il} \\ $$$$\mathrm{y}\:\mathrm{a}\:\mathrm{d}'\mathrm{entiers}\:\mathrm{suivants}\:\mathrm{qui}\:\mathrm{ont}\:\mathrm{pour} \\ $$$$\mathrm{image}\:\mathrm{2}\:\mathrm{puis}\:\mathrm{une}\:\mathrm{cloison}.\:\mathrm{Si}\:\mathrm{aucun} \\ $$$$\mathrm{entier}\:\mathrm{n}'\mathrm{a}\:\mathrm{pour}\:\mathrm{image}\:\mathrm{2}\:\mathrm{on}\:\mathrm{met} \\ $$$$\mathrm{simplement}\:\mathrm{une}\:\mathrm{cloison}. \\ $$$$ \\ $$$$\mathrm{Et}\:\mathrm{ainsi}\:\mathrm{de}\:\mathrm{suite}\:\mathrm{sauf}\:\mathrm{que}\:\mathrm{lorsqu}'\mathrm{on} \\ $$$$\mathrm{arrive}\:\mathrm{aux}\:\mathrm{derniers}\:\mathrm{entiers}\:\mathrm{qui}\:\mathrm{ont} \\ $$$$\mathrm{pour}\:\mathrm{image}\:{n}\:\mathrm{il}\:\mathrm{est}\:\mathrm{inutile}\:\mathrm{de}\: \\ $$$$\mathrm{terminer}\:\mathrm{par}\:\mathrm{une}\:\mathrm{cloison}. \\ $$$$ \\ $$$$\mathrm{Un}\:\mathrm{exemple}\:\:: \\ $$$$ \\ $$$$\mathrm{Soit}\:\mathrm{l}'\mathrm{application}\:\mathrm{de}\:\left[\left[\mathrm{1},\mathrm{4}\right]\right]\:\mathrm{dans}\:\left[\left[\mathrm{1},\mathrm{5}\right]\right] \\ $$$$\mathrm{telle}\:\mathrm{que}\:{f}\left(\mathrm{1}\right)\:=\:\mathrm{1},\:{f}\left(\mathrm{2}\right)\:=\:\mathrm{1},\:{f}\left(\mathrm{3}\right)\:=\:\mathrm{3},\: \\ $$$${f}\left(\mathrm{4}\right)\:=\:\mathrm{5}.\:\mathrm{Elle}\:\mathrm{est}\:\mathrm{representee}\:\mathrm{par} \\ $$$$\mathrm{11}//\mathrm{3}//\mathrm{5}. \\ $$$$ \\ $$$$\mathrm{Si}\:{f}\left(\mathrm{1}\right)\:=\:{f}\left(\mathrm{2}\right)\:=\:\mathrm{2}\:\mathrm{et}\:{f}\left(\mathrm{3}\right)\:=\:{f}\left(\mathrm{4}\right)\:=\:\mathrm{4},\:\mathrm{la} \\ $$$$\mathrm{representation}\:\mathrm{est}\:/\mathrm{22}//\mathrm{44}/ \\ $$$$ \\ $$$$\mathrm{On}\:\mathrm{a}\:\mathrm{donc}\:\mathrm{ecrit}\:{n}\:\mathrm{nombres}\:\mathrm{et}\:{p}−\mathrm{1} \\ $$$$\mathrm{cloisons}\:\mathrm{donc}\:{n}+{p}−\mathrm{1}\:\mathrm{symboles}. \\ $$$$ \\ $$$$\mathrm{Une}\:\mathrm{application}\:\mathrm{croissante}\: \\ $$$$\mathrm{est}\:\mathrm{determinee}\:\mathrm{par}\:\mathrm{la}\:\mathrm{place}\:\mathrm{des}\:{p}−\mathrm{1} \\ $$$$\mathrm{cloisons}.\:\mathrm{Le}\:\mathrm{nombre}\:\mathrm{d}'\mathrm{applications} \\ $$$$\mathrm{croissates}\:\mathrm{est}\:\mathrm{donc}\:\mathrm{C}_{{p}−\mathrm{1}} ^{{n}+{p}−\mathrm{1}} . \\ $$$$ \\ $$$$\mathrm{Dans}\:\mathrm{notre}\:\mathrm{cas}\:\mathrm{particulier},\:\mathrm{on}\:\mathrm{a}\:\mathrm{une} \\ $$$$\mathrm{suite}\:\mathrm{de}\:{n}\:\mathrm{nombres}\:\mathrm{donc}\:{p}\:=\:{n}.\:\mathrm{Et}\:\mathrm{le} \\ $$$$\mathrm{nombre}\:\mathrm{de}\:\mathrm{suites}\:\mathrm{croissantes}\:\mathrm{de}\:{n} \\ $$$$\mathrm{termes}\:\mathrm{de}\:\left[\left[\mathrm{1},{n}\right]\right]\:\mathrm{est}\:\mathrm{alors}\:: \\ $$$$\mathrm{C}_{{n}−\mathrm{1}} ^{\mathrm{2}{n}−\mathrm{1}} . \\ $$$$ \\ $$$$\mathrm{Par}\:\mathrm{exemple},\:\mathrm{pour}\:\mathrm{les}\:\mathrm{5}−\mathrm{uplets}\:\mathrm{de} \\ $$$$\mathrm{nombres}\:\mathrm{de}\:\mathrm{1}\:\mathrm{a}\:\mathrm{5},\:\mathrm{il}\:\mathrm{y}\:\mathrm{en}\:\mathrm{a}\:: \\ $$$$\mathrm{C}_{\mathrm{5}−\mathrm{1}} ^{\mathrm{2}×\mathrm{5}−\mathrm{1}} \:=\:\mathrm{C}_{\mathrm{4}} ^{\mathrm{9}} \:=\:\frac{\mathrm{9}!}{\mathrm{4}!\mathrm{5}!}\:=\:\mathrm{126}\:\mathrm{dont}\:\mathrm{les}\:\mathrm{5} \\ $$$$\mathrm{nombres}\:\mathrm{sont}\:\mathrm{ranges}\:\mathrm{dans}\:\mathrm{l}'\mathrm{ordre} \\ $$$$\mathrm{croissant}. \\ $$

Leave a Reply

Your email address will not be published. Required fields are marked *