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.](Q147065.png)
$$\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}. \\ $$