A few examples often make things easier to understand.
Let's look at A(1). There are 4 sequences; 0,1,2,3. Of these, one sequence (0) has an odd number of 0s, the other three have an even number of 0s.
Let's look at A(2). We generate this sequence by sticking 0,1,2, or 3 on the end of our previous sequences to get 4x4 = 16 possible sequences. These are: 00,01,02,03,10,11, ..., 33. Now, notice that when we add a 0, if the sequence had an odd number of 0s beforehand, it has an even number afterwards; and vice versa. if we add anythuing else, the number of 0s is unchanged.
ASo, let's look at the general case, starting with A(n-1) and attempting to derive A(n).
A(n-1) is the number of sequences of length (n-1) with an even number of 0s
4^(n-1) is the number of possible sequences of length (n-1)
So 4^(n-1)-A(n-1) is the number if sequences with an odd number of zeros.
So, adding a digit to the end, 3 possibilities don't change the number of zeros, but one does.
A(n), then , is 3 x the number of sequences with even 0s + 1 x number of sequences with odd 0s
A(n) = 3A(n-1) + 4^(n-1)-A(n)
A(n) = 2A(n-1) + 4^(n-1)
... the solution was actuially quite explicit. You just have to learn the language ;)
--
CH3 Stephen Tavener
| DigiText Programmer, BBC News, New Media.
N
/ \ Room BC3 xtn (020 800)84739
N----C C==O Broadcast Centre, 201 Wood Lane, London. W12 7TP
|| || |
|| || | mailto:Stephen.Tavener@bbc.co.uk (Work)
CH C N--CH3 mailto:mrraow@gmail.com (Home)
\ / \ /
N C http://www.scat.demon.co.uk/ (Games)
| ||
CH3 O Baby pictures:
http://rainbot.pwp.blueyonder.co.uk/Katiefrog/group.jpg
From: Math4u@yahoogroups.com [mailto:Math4u@yahoogroups.com] On Behalf Of Ashok Hari
Sent: 02 November 2007 05:56
To: grpashok@yahoo.co.in
Subject: [Math4u] Help me plz1. - Math doubt
Dear all,
I am studying open university. So I didn't have a proper teacher who can teach me, perticularly math, because of that i studing my self. While i go through the math i have some doubts. Please and kindly give your ideas and notes to clear those my doubts.
Math Name : Discrete Mathematics.
Topic : Recurrence Relations
---------------
Problem 1:-
Set up a recurrence relation for the number of n digit sequence on integers (0,1,2,3) having an even number of 0's
Solution:-
Let An denote the number of n-digit sequence containing an even number of 0's. Then there are An-1(n-1) - digit sequence that have an even number of 0's and 4^(n-1)-An-1(n-1) - digit sequence that have an odd number of 0's. To! each of the An-1 sequences that have an even number of 0's, the digit 1,2 or 3 can be appended to yield sequence of length n that contain an even number of 0's. To each of the 4^(n-1)-An-1 sequences that have an odd number of 0's, the digit 0 must be appended to yield sequences of length n that contain an even number of 0's.Therefore,for n>=2, An = 3An-1 + 4^(n-1) - An-1 = 2An-1+4^(n-1), with a1=3
--------------
Can anyone help me to understand solution based on the problem. If you mention the with example it would be the great.
My Adv. Thank you,
Regards
H.Ashok
Unlimited freedom, unlimited storage. Get it now
http://www.bbc.co.uk
This e-mail (and any attachments) is confidential and may contain personal views which are not the views of the BBC unless specifically stated.
If you have received it in error, please delete it from your system.
Do not use, copy or disclose the information in any way nor act in reliance on it and notify the sender immediately.
Please note that the BBC monitors e-mails sent or received.
Further communication will signify your consent to this. __._,_.___
Your email settings: Individual Email|Traditional
Change settings via the Web (Yahoo! ID required)
Change settings via email: Switch delivery to Daily Digest | Switch to Fully Featured
Visit Your Group | Yahoo! Groups Terms of Use | Unsubscribe
Change settings via the Web (Yahoo! ID required)
Change settings via email: Switch delivery to Daily Digest | Switch to Fully Featured
Visit Your Group | Yahoo! Groups Terms of Use | Unsubscribe
__,_._,___
No comments:
Post a Comment