TASK: Count derangements of N objects, a sequence depending on two previous values.
COMMENT: Given the letters A, B, C and D, we can make 24 different "words", that use each letter once, starting with "ABCD". In exactly 9 of these words, such as "DCAB", no letter appears in its original position. Such a scrambling is called a derangement. Thus, there are 9 possible derangements of 4 letters, which we symbolized as "D(4)=9".
The number of derangments of I letters is symbolized by D(I). The sequence starts out with D(0)=1, D(1)=0. If you have two successive values of D, you can compute the next one. The rule is:
D(I) = ( I - 1 ) * ( D(I-1) + D(I-2) )
so you can compute
D(0) = 1
D(1) = 0
D(2) = 1 * ( D(1) + D(0) ) = 1 * ( 0 + 1 ) = 1
D(3) = 2 * ( D(2) + D(1) ) = 2 * ( 1 + 0 ) = 2
D(4) = 3 * ( D(3) + D(2) ) = 3 * ( 2 + 1 ) = 9 ...
Given the values of D(0) and D(1), we want to compute D(2) through D(10).
INSTRUCTIONS:
D(I) is a sequence whose next value depends on two old values.
We won't store all the values of the sequence, just the previous
two values that we need, and the next one that we compute.
We could use the names "DOLD" and "DOLDER" for the old data, and "DNEW"
for the new value.
Initialize DOLD to 1. % This is D(0)
Initialize DNEW to 0. % This is D(1)
Create a for loop that counts from 2 to 10.
copy DOLD into DOLDER
copy DNEW into DOLD
compute the value of DNEW using the formula
Print the value like this:
fprintf ( ' D(%d) = %d\n', i, DNEW );
end your FOR loop
(To make the table nicer, you could print the values of D(0) and D(1)
before the loop begins.)
CHECK: If your program is running correctly, you should see the following line as part of your output:
D(8) = 14833
SUBMIT: Your work should be stored in a script file called "hw020.m". Your script file should begin with at least three comment lines:
% hw020.m
% YOUR NAME
% This script (describe what it does)
% Add any comments here that you care to make.
If this problem is part of an assignment, then submit it to Canvas.