thanks that was a very nice tutorial..... but i am still stuck with
S(n,3) = A(n+3) = 6*A(n+2) - 11*A(n+1) + 6*A(n) ------------------- 1 S(n+1,4)=S(n,3)+4*S(n,4) -------------------- 2nd stirling number 3*S(n+1,4) = 0, 0, 3, 30, 195, 1050, 5103, 23310........ what will be the matrix for the second sequence i know how to solve the first recurrence, but how to solve the second one............ On Sun, Jan 9, 2011 at 6:13 PM, radha krishnan <[email protected] > wrote: > You find this so useful .... > http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html > > On Sun, Jan 9, 2011 at 6:10 PM, shady <[email protected]> wrote: > > I am not familiar with such techniques, can you please refer to some > article > > where such techniques are explained, ... > > Regards, > > Shady > > > > On Sun, Jan 9, 2011 at 5:44 PM, juver++ <[email protected]> wrote: > >> > >> There is very useful technique for this kind of problem. > >> A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3). > >> Let's introduce matrix B: > >> C1 -C2 C3 > >> 1 0 0 > >> 0 1 0. > >> A(n-1) A(n) > >> B x A(n-2) = A(n-1) > >> A(n-3) A(n-2) > >> and so on.. > >> So to find A(n) you should muultiply matrix B^n by initial vector (A2, > A1, > >> A0). > >> B^n can be calculated using fast exponention algorithm. > >> Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3. > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]<algogeeks%[email protected]> > . > >> For more options, visit this group at > >> http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%[email protected]> > . > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
