Prev: A question on Farey's sequences.
Next: THE HOLY GRAIL ~ CANTOR DISPROOF
From: amarj japp on 23 May 2010 08:34
Q. How many 6 digit number without repetition of digits are there such
that the
digits are all non-zero and 1 and 2 do not appear consecutively
in either order.

Soln: The Book considers for cases
(i) Neither 1 nor 2 appears as digits : (P 7 6) = 7!
(ii) 1, but not 2 appears as a digit : 6 (P 7 5)
(iii) 2, but not 1 appears : 6 (P 7 5)
(iv) Both 1 and 2 appears : 2.7.4.P(6,3) +
4.7.6.3.P(5,2)

We add them to get the total of 52080

My question is , if i tries to do this using indirect counting i.e
Number of ways , when the 1 and 2 appears together is 2*P(8,6)
If is subtract above from P(9 6) i.e P(9,6) - 2*P(8,6) = 20160

I don't understand how i am not getting same answer , please suggest
what i am doing wrong.
Thanks
From: David C. Ullrich on 23 May 2010 09:58
On Sun, 23 May 2010 05:34:51 -0700 (PDT), amarj japp
<amarj.rocky(a)gmail.com> wrote:

>Q. How many 6 digit number without repetition of digits are there such
>that the
> digits are all non-zero and 1 and 2 do not appear consecutively
>in either order.
>
>Soln: The Book considers for cases
> (i) Neither 1 nor 2 appears as digits : (P 7 6) = 7!
> (ii) 1, but not 2 appears as a digit : 6 (P 7 5)
> (iii) 2, but not 1 appears : 6 (P 7 5)
> (iv) Both 1 and 2 appears : 2.7.4.P(6,3) +
>4.7.6.3.P(5,2)
>
>We add them to get the total of 52080
>
>My question is , if i tries to do this using indirect counting i.e
>Number of ways , when the 1 and 2 appears together is 2*P(8,6)
>If is subtract above from P(9 6) i.e P(9,6) - 2*P(8,6) = 20160
>
>I don't understand how i am not getting same answer , please suggest
>what i am doing wrong.

Why do you think that the number of permutations where a 1 and a 2
appear together is 2*P(8,6)?

I verified the answer using brute-force calculation.
Extremely bad, maximally inefficient Python that
does the job:

def bad(x,y):
return (x,y) == (0,1) or (x,y) == (1,0)

def ok(s):
for j in range(5):
if bad(s[j],s[j+1]): return 0
return 1

ss = [()]
for places in range(6):
ss = [s+(j,) for s in ss for j in range(9) if not j in s]

count = 0
for s in ss:
if ok(s):
count = count + 1


print count #5280

>Thanks

From: amzoti on 23 May 2010 13:11
On May 23, 6:58 am, David C. Ullrich <ullr...(a)math.okstate.edu> wrote:
> On Sun, 23 May 2010 05:34:51 -0700 (PDT), amarj japp
>
>
>
> <amarj.ro...(a)gmail.com> wrote:
> >Q. How many 6 digit number without repetition of digits are there such
> >that the
> >     digits are all non-zero and 1 and 2 do not appear consecutively
> >in either order.
>
> >Soln: The Book considers for cases
> >         (i)   Neither 1 nor 2 appears as digits :  (P 7 6) = 7!
> >         (ii)  1, but not 2 appears as a digit  : 6 (P 7 5)
> >        (iii)  2, but not 1 appears                : 6 (P 7 5)
> >        (iv) Both 1 and 2 appears              : 2..7.4.P(6,3) +
> >4.7.6.3.P(5,2)
>
> >We add them to get the total of 52080
>
> >My question is , if i tries to do this using indirect counting i.e
> >Number of ways , when the 1 and 2 appears together is 2*P(8,6)
> >If is subtract above from P(9 6) i.e P(9,6) - 2*P(8,6) = 20160
>
> >I don't understand how i am not getting same answer , please suggest
> >what i am doing wrong.
>
> Why do you think that the number of permutations where a 1 and a 2
> appear together is 2*P(8,6)?
>
> I verified the answer using brute-force calculation.
> Extremely bad, maximally inefficient Python that
> does the job:
>
> def bad(x,y):
>   return (x,y) == (0,1) or (x,y) == (1,0)
>
> def ok(s):
>   for j in range(5):
>    if bad(s[j],s[j+1]): return 0
>   return 1
>
> ss = [()]
> for places in range(6):
>   ss = [s+(j,) for s in ss for j in range(9) if not j in s]
>
> count = 0
> for s in ss:
>   if ok(s):
>     count = count + 1
>
> print count #5280
>
> >Thanks
>
>

Did you miss a zero or something is amiss? (52080)
From: Calculus Tutor Physics Tutor on 23 May 2010 13:18
On May 23, 7:34 am, amarj japp <amarj.ro...(a)gmail.com> wrote:
> Q. How many 6 digit number without repetition of digits are there such
> that the
>      digits are all non-zero and 1 and 2 do not appear consecutively
> in either order.
>
> Soln: The Book considers for cases
>          (i)   Neither 1 nor 2 appears as digits :  (P 7 6) = 7!
>          (ii)  1, but not 2 appears as a digit  : 6 (P 7 5)
>         (iii)  2, but not 1 appears                : 6 (P 7 5)
>         (iv) Both 1 and 2 appears              : 2.7.4.P(6,3) +
> 4.7.6.3.P(5,2)
>
> We add them to get the total of 52080
>
> My question is , if i tries to do this using indirect counting i.e
> Number of ways , when the 1 and 2 appears together is 2*P(8,6)
> If is subtract above from P(9 6) i.e P(9,6) - 2*P(8,6) = 20160
>
> I don't understand how i am not getting same answer , please suggest
> what i am doing wrong.
> Thanks
Your second term on LHS in P(9,6) - 2*P(8,6) = 20160 is not correct.
Instead of 2*P(8,6) it should be 2 x 5 x P(7,4) = 8400 which gives all
six digits numbers with 1 and 2 appearing as neighboring digits.
Consider 1 & 2 as a block (as if it is one digit).
# of ways for block to be placed in 6 slots = 5
# of ways 1 & 2 can be placed within block itself = 2
# of ways for remaining 7 digits to take remaining 4 slots = P(7, 4)
Thus,
Total numbers for deduction = 2 x 5 x P(7, 4)

= 20160

Required possibilities = P(9,6) - 2 x 5 x P(7, 4)

= 60480 - 8400 = 52080 as expected


Best regards.

Mohan Pawar
www.mpclasses.com
---------------------------------------------------------------------------
AP Calculus, AP Physics, Singapore Math Grades 7-12
---------------------------------------------------------------------------
US Central Time: 12:18 PM 5/23/2010
From: Calculus Tutor Physics Tutor on 23 May 2010 13:22
On May 23, 12:18 pm, Calculus Tutor Physics Tutor
<GoogleO...(a)mpClasses.com> wrote:
> On May 23, 7:34 am, amarj japp <amarj.ro...(a)gmail.com> wrote:
>
> > Q. How many 6 digit number without repetition of digits are there such
> > that the
> >      digits are all non-zero and 1 and 2 do not appear consecutively
> > in either order.
>
> > Soln: The Book considers for cases
> >          (i)   Neither 1 nor 2 appears as digits :  (P 7 6) = 7!
> >          (ii)  1, but not 2 appears as a digit  : 6 (P 7 5)
> >         (iii)  2, but not 1 appears                : 6 (P 7 5)
> >         (iv) Both 1 and 2 appears              : 2.7.4.P(6,3) +
> > 4.7.6.3.P(5,2)
>
> > We add them to get the total of 52080
>
> > My question is , if i tries to do this using indirect counting i.e
> > Number of ways , when the 1 and 2 appears together is 2*P(8,6)
> > If is subtract above from P(9 6) i.e P(9,6) - 2*P(8,6) = 20160
>
> > I don't understand how i am not getting same answer , please suggest
> > what i am doing wrong.
> > Thanks
>
> Your second term on LHS in P(9,6) - 2*P(8,6) = 20160 is not correct.
> Instead of 2*P(8,6) it should be 2 x 5 x P(7,4) = 8400 which gives all
> six digits numbers with 1 and 2 appearing as neighboring digits.
> Consider 1 & 2 as a block (as if it is one digit).
> # of ways for block to be placed in 6 slots = 5
> # of ways 1 & 2 can be placed within block itself = 2
> # of ways for remaining 7 digits to take remaining 4 slots = P(7, 4)
> Thus,
> Total numbers for deduction     = 2 x 5 x P(7, 4)
>
>                             = 20160
20160 is a typo & should be 8400
>
> Required possibilities          = P(9,6) -  2 x 5 x P(7, 4)
>
>                             = 60480 - 8400 = 52080 as expected
>
> Best regards.
>
> Mohan Pawarwww.mpclasses.com
> ---------------------------------------------------------------------------
> AP Calculus, AP Physics, Singapore Math Grades 7-12
> ---------------------------------------------------------------------------
> US Central Time: 12:18 PM 5/23/2010

 |  Next  |  Last
Pages: 1 2
Prev: A question on Farey's sequences.
Next: THE HOLY GRAIL ~ CANTOR DISPROOF