Question and Answers Forum

All Questions      Topic List

Permutation and Combination Questions

Previous in All Question      Next in All Question      

Previous in Permutation and Combination      Next in Permutation and Combination      

Question Number 155257 by mr W last updated on 27/Sep/21

Commented by mr W last updated on 28/Sep/21

the grid has m×n steps.  find the number of routes with k  turns.

$${the}\:{grid}\:{has}\:\boldsymbol{{m}}×\boldsymbol{{n}}\:{steps}. \\ $$$${find}\:{the}\:{number}\:{of}\:{routes}\:{with}\:\boldsymbol{{k}} \\ $$$${turns}. \\ $$

Commented by mr W last updated on 28/Sep/21

it is to find the number of routes  with exactly k turns. the example  shows a route with 7 turns. the grid  is generally of size m×n.

$${it}\:{is}\:{to}\:{find}\:{the}\:{number}\:{of}\:{routes} \\ $$$${with}\:{exactly}\:{k}\:{turns}.\:{the}\:{example} \\ $$$${shows}\:{a}\:{route}\:{with}\:\mathrm{7}\:{turns}.\:{the}\:{grid} \\ $$$${is}\:{generally}\:{of}\:{size}\:{m}×{n}. \\ $$

Commented by bemath last updated on 28/Sep/21

 C_( 8) ^( 18) = C_(10) ^(18) = 43758  required number of routes  is a number of ways of taking  m right turns (or n down turns)

$$\:\mathrm{C}_{\:\mathrm{8}} ^{\:\mathrm{18}} =\:\mathrm{C}_{\mathrm{10}} ^{\mathrm{18}} =\:\mathrm{43758} \\ $$$$\mathrm{required}\:\mathrm{number}\:\mathrm{of}\:\mathrm{routes} \\ $$$$\mathrm{is}\:\mathrm{a}\:\mathrm{number}\:\mathrm{of}\:\mathrm{ways}\:\mathrm{of}\:\mathrm{taking} \\ $$$$\mathrm{m}\:\mathrm{right}\:\mathrm{turns}\:\left(\mathrm{or}\:\mathrm{n}\:\mathrm{down}\:\mathrm{turns}\right) \\ $$

Commented by mathdanisur last updated on 28/Sep/21

bemath = benjo qoarto gultom)  this solution does not apply to you..  this solution #lekraj beedassy is the solution..

$$\left.\boldsymbol{\mathrm{b}}\mathrm{emath}\:=\:\boldsymbol{\mathrm{b}}\mathrm{enjo}\:\boldsymbol{\mathrm{q}}\mathrm{oarto}\:\boldsymbol{\mathrm{g}}\mathrm{ultom}\right) \\ $$$$\mathrm{this}\:\mathrm{solution}\:\mathrm{does}\:\mathrm{not}\:\mathrm{apply}\:\mathrm{to}\:\mathrm{you}.. \\ $$$$\mathrm{this}\:\mathrm{solution}\:#\boldsymbol{\mathrm{l}}\mathrm{ekraj}\:\boldsymbol{\mathrm{b}}\mathrm{eedassy}\:\mathrm{is}\:\mathrm{the}\:\mathrm{solution}.. \\ $$

Commented by mr W last updated on 28/Sep/21

please explain what you mean!

$${please}\:{explain}\:{what}\:{you}\:{mean}! \\ $$

Answered by TheHoneyCat last updated on 29/Sep/21

If n+m−k>0:  there are 2.(k+1)^(n+m−(k+1))  routes    if not there arn′t any.    (proof down below, sorry for not typing it  but I feel like the drawings help the   understanding)

$$\mathrm{If}\:{n}+{m}−{k}>\mathrm{0}: \\ $$$$\mathrm{there}\:\mathrm{are}\:\mathrm{2}.\left({k}+\mathrm{1}\right)^{{n}+{m}−\left({k}+\mathrm{1}\right)} \:\mathrm{routes} \\ $$$$ \\ $$$$\mathrm{if}\:\mathrm{not}\:\mathrm{there}\:\mathrm{arn}'\mathrm{t}\:\mathrm{any}. \\ $$$$ \\ $$$$\left(\mathrm{proof}\:\mathrm{down}\:\mathrm{below},\:\mathrm{sorry}\:\mathrm{for}\:\mathrm{not}\:\mathrm{typing}\:\mathrm{it}\right. \\ $$$$\mathrm{but}\:\mathrm{I}\:\mathrm{feel}\:\mathrm{like}\:\mathrm{the}\:\mathrm{drawings}\:\mathrm{help}\:\mathrm{the}\: \\ $$$$\left.\mathrm{understanding}\right) \\ $$

Commented by TheHoneyCat last updated on 29/Sep/21

Commented by mr W last updated on 29/Sep/21

for k=1 there are two routes. but you  get 2×(1+1)^(n+m−2) =2^(n+m−1) !

$${for}\:{k}=\mathrm{1}\:{there}\:{are}\:{two}\:{routes}.\:{but}\:{you} \\ $$$${get}\:\mathrm{2}×\left(\mathrm{1}+\mathrm{1}\right)^{{n}+{m}−\mathrm{2}} =\mathrm{2}^{{n}+{m}−\mathrm{1}} ! \\ $$

Commented by TheHoneyCat last updated on 29/Sep/21

Damn it! You are right...    I have forgotten that the constraint on  length and turns is not an equivalence...  I am counting both:  →↓↓↓ & →→↓↓    My method can still be modified without  a lot of work to get the correct solution  I must make a distinction betwee “→”  and “↓”   But I am quite too tired to do it now.  (I live in Europe)  This weekend maybe...    Sorry for not double checking

$$\mathrm{Damn}\:\mathrm{it}!\:\mathrm{You}\:\mathrm{are}\:\mathrm{right}... \\ $$$$ \\ $$$$\mathrm{I}\:\mathrm{have}\:\mathrm{forgotten}\:\mathrm{that}\:\mathrm{the}\:\mathrm{constraint}\:\mathrm{on} \\ $$$$\mathrm{length}\:\mathrm{and}\:\mathrm{turns}\:\mathrm{is}\:\mathrm{not}\:\mathrm{an}\:\mathrm{equivalence}... \\ $$$$\mathrm{I}\:\mathrm{am}\:\mathrm{counting}\:\mathrm{both}: \\ $$$$\rightarrow\downarrow\downarrow\downarrow\:\&\:\rightarrow\rightarrow\downarrow\downarrow \\ $$$$ \\ $$$$\mathrm{My}\:\mathrm{method}\:\mathrm{can}\:\mathrm{still}\:\mathrm{be}\:\mathrm{modified}\:\mathrm{without} \\ $$$$\mathrm{a}\:\mathrm{lot}\:\mathrm{of}\:\mathrm{work}\:\mathrm{to}\:\mathrm{get}\:\mathrm{the}\:\mathrm{correct}\:\mathrm{solution} \\ $$$$\mathrm{I}\:\mathrm{must}\:\mathrm{make}\:\mathrm{a}\:\mathrm{distinction}\:\mathrm{betwee}\:``\rightarrow'' \\ $$$$\mathrm{and}\:``\downarrow''\: \\ $$$$\mathrm{But}\:\mathrm{I}\:\mathrm{am}\:\mathrm{quite}\:\mathrm{too}\:\mathrm{tired}\:\mathrm{to}\:\mathrm{do}\:\mathrm{it}\:\mathrm{now}. \\ $$$$\left(\mathrm{I}\:\mathrm{live}\:\mathrm{in}\:\mathrm{Europe}\right) \\ $$$$\mathrm{This}\:\mathrm{weekend}\:\mathrm{maybe}... \\ $$$$ \\ $$$$\mathrm{Sorry}\:\mathrm{for}\:\mathrm{not}\:\mathrm{double}\:\mathrm{checking} \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com