Question Number 195079 by sonukgindia last updated on 23/Jul/23 | ||
Answered by witcher3 last updated on 24/Jul/23 | ||
$$\mathrm{we}\:\mathrm{applie}\:\mathrm{S}_{\mathrm{n}} \:\mathrm{to}\:\mathrm{this}\:\mathrm{sum}\:\mathrm{witch}\:\mathrm{symetric}\:\mathrm{Groupe}\:\mathrm{of} \\ $$$$\mathrm{n}\:\mathrm{element}\:\mathrm{we}\:\mathrm{not}\:\mathrm{this}\:\mathrm{elements}\:\sigma \\ $$$$\mathrm{cardS}_{\mathrm{n}} =\mathrm{n}!;\left\{\mathrm{1}.....\mathrm{n}\right\}\overset{\sigma} {\rightarrow}\left\{\mathrm{1},....,\mathrm{n}\right\} \\ $$$$\mathrm{S}=\underset{\mathrm{k}_{\mathrm{1}} +...+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } \right)....\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +...+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$=\underset{\mathrm{k}_{\mathrm{1}} +...+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } \left(\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } +\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{2}\right)} } \right)....\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +...+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}=\frac{\mathrm{1}}{\mathrm{n}!}\underset{\sigma\in\mathrm{S}_{\mathrm{n}} } {\sum}\underset{\mathrm{k}_{\mathrm{1}} +...+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } \left(\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{1}} \right)} +\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{2}} \right)} \right)....\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +...+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\underset{\sigma\in\mathrm{S}_{\mathrm{n}} } {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{1}} \right)} \left(\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{1}} \right)} +\mathrm{2}^{\sigma\left(\mathrm{k}_{\mathrm{2}} \right)} \right).....\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +...+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)}=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} +..+\mathrm{k}_{\mathrm{n}} } } \\ $$$$\mathrm{proof}\: \\ $$$$\mathrm{tack}\:\tau\left(\mathrm{1},\mathrm{2}\right)\:\:\mathrm{transposition}\:\mathrm{of}\:\mathrm{1}\:\&\mathrm{2} \\ $$$$\mathrm{2S}_{\mathrm{1}} =\Sigma\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } .....\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +..\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)}+\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } \right)...\left(\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } ....+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}_{\mathrm{2}} =\mathrm{2S}_{\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{3}} } \right)\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +...+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}_{\mathrm{2}} \tau\left(\mathrm{1},\mathrm{3}\right)+\mathrm{S}_{\mathrm{2}} \tau\left(\mathrm{2},\mathrm{3}\right)+\mathrm{S}_{\mathrm{2}} =\mathrm{S}_{\mathrm{3}} =\mathrm{3S}_{\mathrm{2}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} +\mathrm{k}_{\mathrm{3}} } \left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{3}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{4}} } \right)...\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +..\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}^{\left(\mathrm{t}\right)} =\underset{\mathrm{k}=\mathrm{1}} {\overset{\mathrm{t}−\mathrm{1}} {\sum}}\mathrm{S}_{\mathrm{m}−\mathrm{1}} \tau\left(\mathrm{1},\mathrm{t}\right)+\mathrm{S}_{\mathrm{m}−\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +...+\mathrm{k}_{\mathrm{t}} } .\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +..+\mathrm{2}^{\mathrm{k}_{\mathrm{t}+\mathrm{1}} } \right)..\left(\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +\mathrm{2}^{\mathrm{k}_{\mathrm{2}} } +..+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \right)} \\ $$$$\mathrm{S}^{\mathrm{n}} =\mathrm{nS}_{\mathrm{n}−\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +...+\mathrm{k}_{\mathrm{n}} } } \\ $$$$\mathrm{n}!\mathrm{S}=\underset{\mathrm{k}_{\mathrm{1}} +..+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +...+\mathrm{k}_{\mathrm{n}} } }=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{m}} }\:\:\underset{\mathrm{k}_{\mathrm{1}} +..+\mathrm{k}_{\mathrm{n}} =\mathrm{m}} {\sum}\mathrm{1}=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{m}} }\begin{pmatrix}{\mathrm{m}+\mathrm{n}−\mathrm{1}}\\{\:\:\:\:\:\:\:\mathrm{m}}\end{pmatrix} \\ $$$$\mathrm{S}=\frac{\begin{pmatrix}{\:\:\:\mathrm{m}+\mathrm{n}−\mathrm{1}}\\{\:\:\:\:\:\:\:\:\:\:\mathrm{m}}\end{pmatrix}}{\mathrm{n}!\mathrm{2}^{\mathrm{m}} } \\ $$$$``\underset{\sigma\in\mathrm{S}_{\mathrm{n}} } {\sum}\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\sigma\left(\mathrm{1}\right)} } \left(\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{1}\right)} +\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{2}\right)} \right)...\left(\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{1}\right)} +\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{2}\right)} +\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{n}\right)} \right.}=\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{k}_{\mathrm{1}} +\mathrm{k}_{\mathrm{2}} +..+\mathrm{k}_{\mathrm{n}} } }'' \\ $$$$\mathrm{was}\:\mathrm{the}\:\mathrm{key} \\ $$$$\sigma\left[\mathrm{1}..\mathrm{n}\right]=\left[\mathrm{1}...\mathrm{n}\right]\Rightarrow\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{1}\right)} +...+\mathrm{2}^{\mathrm{k}\sigma\left(\mathrm{n}\right)} =\mathrm{2}^{\mathrm{k}_{\mathrm{1}} } +...+\mathrm{2}^{\mathrm{k}_{\mathrm{n}} } \:\sigma\:\mathrm{is}\:\mathrm{bijection} \\ $$$$ \\ $$$$ \\ $$$$ \\ $$$$ \\ $$$$ \\ $$ | ||
Commented by witcher3 last updated on 24/Jul/23 | ||
$$\mathrm{car}\:\left(\mathrm{k}_{\mathrm{1}} ,\mathrm{k}_{\mathrm{2}} ...\mathrm{k}_{\mathrm{n}} \right)\mid\left(\mathrm{k}_{\mathrm{1}} +...+\mathrm{k}_{\mathrm{n}} =\mathrm{m}\right)=\begin{pmatrix}{\mathrm{m}+\mathrm{n}−\mathrm{1}}\\{\:\:\:\:\:\:\:\mathrm{m}}\end{pmatrix} \\ $$ | ||