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 189049 by mr W last updated on 11/Mar/23

Commented by mr W last updated on 13/Mar/23

this is an old question (Q164560).   maybe meanwhile somebody has got   a new solution.

$${this}\:{is}\:{an}\:{old}\:{question}\:\left({Q}\mathrm{164560}\right).\: \\ $$$${maybe}\:{meanwhile}\:{somebody}\:{has}\:{got}\: \\ $$$${a}\:{new}\:{solution}. \\ $$

Commented by nikif99 last updated on 11/Mar/23

Answered by nikif99 last updated on 11/Mar/23

132  At first, I tried to solve it graphically   [see attached; every row is a queue   of girls (pink) and boys (blue)] not  creating problem to the cashier.  Then, I tried to generalise the solution  (5g+5b: 42; 4g+4b: 14) without succes.  Later, I noticed a comment in a (greek)  article about the principle of reflection  in combinatorics with the solution:  The probability for not problem to the  cashier is 1/(n+1).  Considering all possible arrangements  in queue is C_n ^(2n) , the accepted queues are  (1/(n+1)) C_n ^(2n)  =(1/7)∙924=132

$$\mathrm{132} \\ $$$${At}\:{first},\:{I}\:{tried}\:{to}\:{solve}\:{it}\:{graphically}\: \\ $$$$\left[{see}\:{attached};\:{every}\:{row}\:{is}\:{a}\:{queue}\:\right. \\ $$$$\left.{of}\:{girls}\:\left({pink}\right)\:{and}\:{boys}\:\left({blue}\right)\right]\:{not} \\ $$$${creating}\:{problem}\:{to}\:{the}\:{cashier}. \\ $$$${Then},\:{I}\:{tried}\:{to}\:{generalise}\:{the}\:{solution} \\ $$$$\left(\mathrm{5}{g}+\mathrm{5}{b}:\:\mathrm{42};\:\mathrm{4}{g}+\mathrm{4}{b}:\:\mathrm{14}\right)\:{without}\:{succes}. \\ $$$${Later},\:{I}\:{noticed}\:{a}\:{comment}\:{in}\:{a}\:\left({greek}\right) \\ $$$${article}\:{about}\:{the}\:{principle}\:{of}\:{reflection} \\ $$$${in}\:{combinatorics}\:{with}\:{the}\:{solution}: \\ $$$${The}\:{probability}\:{for}\:{not}\:{problem}\:{to}\:{the} \\ $$$${cashier}\:{is}\:\mathrm{1}/\left({n}+\mathrm{1}\right). \\ $$$${Considering}\:{all}\:{possible}\:{arrangements} \\ $$$${in}\:{queue}\:{is}\:{C}_{{n}} ^{\mathrm{2}{n}} ,\:{the}\:{accepted}\:{queues}\:{are} \\ $$$$\frac{\mathrm{1}}{{n}+\mathrm{1}}\:{C}_{{n}} ^{\mathrm{2}{n}} \:=\frac{\mathrm{1}}{\mathrm{7}}\centerdot\mathrm{924}=\mathrm{132} \\ $$

Commented by nikif99 last updated on 11/Mar/23

Commented by nikif99 last updated on 11/Mar/23

Commented by manxsol last updated on 12/Mar/23

interesante.comand in   excel creation table .please or    macro.thank Sr nikki.  ah link article?

$${interesante}.{comand}\:{in}\: \\ $$$${excel}\:{creation}\:{table}\:.{please}\:{or} \\ $$$$\:\:{macro}.{thank}\:{Sr}\:{nikki}. \\ $$$${ah}\:{link}\:{article}? \\ $$

Commented by mr W last updated on 12/Mar/23

my consideration:  at any point in the queue the total   number of girls must be more than   or equal to the total number of boys.   we can display this as a step path like   the following one.  if such a path lies  completely above the diagonal   (shaded zone), then the cashier has   no problem with change.

$$\underline{{my}\:{consideration}:} \\ $$$${at}\:{any}\:{point}\:{in}\:{the}\:{queue}\:{the}\:{total}\: \\ $$$${number}\:{of}\:{girls}\:{must}\:{be}\:{more}\:{than}\: \\ $$$${or}\:{equal}\:{to}\:{the}\:{total}\:{number}\:{of}\:{boys}.\: \\ $$$${we}\:{can}\:{display}\:{this}\:{as}\:{a}\:{step}\:{path}\:{like}\: \\ $$$${the}\:{following}\:{one}.\:\:{if}\:{such}\:{a}\:{path}\:{lies} \\ $$$${completely}\:{above}\:{the}\:{diagonal}\: \\ $$$$\left({shaded}\:{zone}\right),\:{then}\:{the}\:{cashier}\:{has}\: \\ $$$${no}\:{problem}\:{with}\:{change}. \\ $$

Commented by mr W last updated on 12/Mar/23

Commented by mr W last updated on 12/Mar/23

this example shows a path for the   case with 6 girls and 6 boys. it   represents the queue: 2 girls, 1 boy,   1 girl, 2 boys, 2 girls, 1 boy, 1 girl and  finally 2 boys.  generally with n girls and n boys, the  number of valid paths is  C_n =(C_n ^(2n) /(n+1))=(((2n)!)/((n+1)!n!))  which is the Catalan number.

$${this}\:{example}\:{shows}\:{a}\:{path}\:{for}\:{the}\: \\ $$$${case}\:{with}\:\mathrm{6}\:{girls}\:{and}\:\mathrm{6}\:{boys}.\:{it}\: \\ $$$${represents}\:{the}\:{queue}:\:\mathrm{2}\:{girls},\:\mathrm{1}\:{boy},\: \\ $$$$\mathrm{1}\:{girl},\:\mathrm{2}\:{boys},\:\mathrm{2}\:{girls},\:\mathrm{1}\:{boy},\:\mathrm{1}\:{girl}\:{and} \\ $$$${finally}\:\mathrm{2}\:{boys}. \\ $$$${generally}\:{with}\:{n}\:{girls}\:{and}\:{n}\:{boys},\:{the} \\ $$$${number}\:{of}\:{valid}\:{paths}\:{is} \\ $$$${C}_{{n}} =\frac{{C}_{{n}} ^{\mathrm{2}{n}} }{{n}+\mathrm{1}}=\frac{\left(\mathrm{2}{n}\right)!}{\left({n}+\mathrm{1}\right)!{n}!} \\ $$$${which}\:{is}\:{the}\:{Catalan}\:{number}. \\ $$

Commented by mr W last updated on 12/Mar/23

nikif sir has got 14 for n=4 and 42  for n=5 and 132 for n=6, they are  all correct and are the corresponding  Catalan numbers.

$${nikif}\:{sir}\:{has}\:{got}\:\mathrm{14}\:{for}\:{n}=\mathrm{4}\:{and}\:\mathrm{42} \\ $$$${for}\:{n}=\mathrm{5}\:{and}\:\mathrm{132}\:{for}\:{n}=\mathrm{6},\:{they}\:{are} \\ $$$${all}\:{correct}\:{and}\:{are}\:{the}\:{corresponding} \\ $$$${Catalan}\:{numbers}. \\ $$

Commented by nikif99 last updated on 12/Mar/23

Wonderful lesson. Thank you Sir!

$${Wonderful}\:{lesson}.\:{Thank}\:{you}\:{Sir}! \\ $$

Commented by manxsol last updated on 12/Mar/23

Thank you very much   Sir. W and Sr. Nikkif for   your effort and  for sharing

$${Thank}\:{you}\:{very}\:{much} \\ $$$$\:{Sir}.\:{W}\:{and}\:{Sr}.\:{Nikkif}\:{for} \\ $$$$\:{your}\:{effort}\:{and}\:\:{for}\:{sharing} \\ $$

Commented by nikif99 last updated on 12/Mar/23

@manxsol  −no macro used in excel. Rows   created manually in blocks, following  combination pattern.  −I have not the article, just a picture  kept. The problem is presented more  complicated. Text says:  There is a queue of 2n persons over the  cashier of a theater. Half of them have  only banknotes of 1000, while the other  half have some 1000s and only one  banknote of 500. Tickets cost 2500 and  3500. The cashier has no money at  the beginning. It is clear that they are  ( determinant (((2n)),(n))) ways to arrange in queue.  In how many of these ways the cashier  has always 500, so no problem occurs?  Frame bottom right: probability for  no problem: 1/(n+1).

$$@{manxsol} \\ $$$$−{no}\:{macro}\:{used}\:{in}\:{excel}.\:{Rows}\: \\ $$$${created}\:{manually}\:{in}\:{blocks},\:{following} \\ $$$${combination}\:{pattern}. \\ $$$$−{I}\:{have}\:{not}\:{the}\:{article},\:{just}\:{a}\:{picture} \\ $$$${kept}.\:{The}\:{problem}\:{is}\:{presented}\:{more} \\ $$$${complicated}.\:{Text}\:{says}: \\ $$$${There}\:{is}\:{a}\:{queue}\:{of}\:\mathrm{2}{n}\:{persons}\:{over}\:{the} \\ $$$${cashier}\:{of}\:{a}\:{theater}.\:{Half}\:{of}\:{them}\:{have} \\ $$$${only}\:{banknotes}\:{of}\:\mathrm{1000},\:{while}\:{the}\:{other} \\ $$$${half}\:{have}\:{some}\:\mathrm{1000}{s}\:{and}\:{only}\:{one} \\ $$$${banknote}\:{of}\:\mathrm{500}.\:{Tickets}\:{cost}\:\mathrm{2500}\:{and} \\ $$$$\mathrm{3500}.\:{The}\:{cashier}\:{has}\:{no}\:{money}\:{at} \\ $$$${the}\:{beginning}.\:{It}\:{is}\:{clear}\:{that}\:{they}\:{are} \\ $$$$\left(\begin{matrix}{\mathrm{2}{n}}\\{{n}}\end{matrix}\right)\:{ways}\:{to}\:{arrange}\:{in}\:{queue}. \\ $$$${In}\:{how}\:{many}\:{of}\:{these}\:{ways}\:{the}\:{cashier} \\ $$$${has}\:{always}\:\mathrm{500},\:{so}\:{no}\:{problem}\:{occurs}? \\ $$$${Frame}\:{bottom}\:{right}:\:{probability}\:{for} \\ $$$${no}\:{problem}:\:\mathrm{1}/\left({n}+\mathrm{1}\right). \\ $$

Commented by nikif99 last updated on 12/Mar/23

Commented by manxsol last updated on 12/Mar/23

thansSr.nikkifor dedicating   your time for my question

$${thansSr}.{nikkifor}\:{dedicating} \\ $$$$\:{your}\:{time}\:{for}\:{my}\:{question} \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com