1. An involution is a permutation whose cycle structure consists only of cycles of length 1 and 2. Let p_3(n) be the number of permutations whose cycle structure consists of cycles of length 1, 2, or 3. Find a linear recurrence satisfied by p_3(n), and express the linear recurrence operator ope(n,N) annihilating it. What is the order of the recurrence? Using procedure SeqFromRec in in ComboProject4.txt find p_3(200).

p_3:= proc(n) local per, i, j, k, flad, ans:
option remember:
ans:=0:
per := permute(n):
for i in per do
flad:=true:
#print(i):
j:=PtoC(i):
for k in j do:
if nops(k) <> 1 and nops(k) <> 2 and nops(k) <> 3 then
flad:=false:
fi:
od:
if flad = true then
ans:=ans+1:
fi:
#print(j):
od:
ans
end proc:

I found this recurrence on OEIS

a(n-1) +(n-1)*a(n-2) +(n-1)*(n-2)*a(n-3))

3. Write a procedure that inputs a positive integer n and outputs the sum of binomial(n,k)^6 from k=0 to n. Call is S6(n). Then write a one-line procedure S6seq(N) that inputs a positive integer N and outputs the first N terms of the sequence S6(n).
Using procedure Findrec in ComboProject4.txt find a linear recurrence operator annihilating it (equivalently a recurrence) and the initial condition, and write procedure S6seqClever(N) that uses procedure SeqFromRec from the same Maple package to do the same thing as S6seq(N).

S6:=proc(n) local i:
option remember:
sum(binomial(n, i)^6, i=1..n)
end proc:
S6(2)
                               65
S6seq:=proc(n) local k:
seq(S6(k), k=1..n)
end proc:


What are

time(S6seq(1000));

and

time(S6seqClever(1000)); ?