#its ok to post
#TaerimKim,10/31/2020,Assignment 16

#1.So we will use similar strategie used in the lecture
#
#so for permutation of cycle length up to 3 means that 
#p_3(0)=p_3(1)=1
#p_3(2)=2
#p_3(3)=6 #full number of perm till n=3
#
#so lets say we have p_3(n) having to permute {1,...,n} with given condition
#here we have 3 options
#
#(i). if number (n -> n) itself : this is same as p_3(n-1) #1
#
#(ii). if number (n -> i) where option i is (n-1) numbers to form cycle of length 2: 
#this is same as having (n-1) ways of getting p_3(n-2) -> (n-1)p_3(n-2)  #2
#
#(iii). if number n forms cycle of length 3 with two different numbers(i,j):
#this is equivalent to having to choose (n-1)(n-2)/2 for respective i and j from n-2 pool(=Binomial(n-1,2))
#and the numbers left(n-3) forms another p_3(n-3) -> 1/2(n-1)(n-2)p_3(n-3) #3
#
#so to sum this up we have linear recurrence of
#
#p_3(n) = p_3(n-1) + (n-1)p_3(n-2) + 1/2(n-1)(n-2)p_3(n-3) with p_3(0)=p_3(1)=1; p_3(2)=2; p_3(3)=6
#             #1          #2                #3
#changing the form,
#
#p_3(n+3) = p_3(n+2) + (n+2)p_3(n+1) + 1/2(n+2)(n+1)p_3(n)
#
#This is order 3 recurrence
#
#p_3(n+3) - p_3(n+2) - (n+2)p_3(n+1) - 1/2(n+2)(n+1)p_3(n) = 0
#(p_3(3) - p_3(2) - (n+2)p_3(1) - 1/2(n+2)(n+1)) * p_3(n) = 0
#The above form of the equation shows us that
#
#ope(n,N) = N^3-N^2-(n+2)N-1/2(n+2)(n+1)
#
#
p_3:=proc(n) option remember:
if n=0 or n=1 then
1;
elif n=2 then
2;
elif n=3 then
6;
else
p_3(n-1)+(n-1)p_3(n-2)+(1/2)*(n-1)*(n-2)*p_3(n-3):
fi;
end; 
p_3(200);
2432415200190689165233382840931892080312201385627385655818436131\

  37579792090588497053116945264059273840933007671403377788980974\

  03489664202430946619697321767963440557986942771476663679453564\

  9215561313909524477839349720966491767052640571826896896

#to find this using SeqfromRec

op(200, SeqFromRec(N^3 - N^2 - (n + 2)*N - (1/2)(n + 2)(n + 1), n, N, [1, 2, 6], 200))
243241520019068916523338284093189208031220138562738565581843613137579792090588497053116945264059273840933007671403377788980974034896642024309466196973217679634405579869427714766636794535649215561313909524477839349720966491767052640571826896896

################################################################################


#2. if we see the involutiona permutation as p_2(n) and #1 as p_3(n)
#we can find out what p_k(n) would look like

#p_2(n+2) = p_2(n+1) + (n+1)p_k(n) = p_2(n+1) + Binomial(n+1,1) * p_2(n) (order 2)
#
#p_3(n+3) = p_3(n+2) + (n+2)p_3(n+1) + 1/2(n+2)(n+1)p_3(n) = p_3(n+2) + Binomial(n+2,1)*p_3(n+1) + Binomial(n+2,2) * p_3(n) (order 3)
#
#we see how the terms are adding here 
#So by same logic
#
#p_k(n+k) = p_k(n+k-1) + Binomial(n+k-1,1)*p_k(n+k-2) + Binomial(n+k-1,2)*p_k(n+k-3) + ... + Binomial(n+k-1,k-1) * p_k(n) (order k)
#
#
#then by same method in #1 of getting ope(N,n), we get
#
#ope(N,n) = N^k - N^(k-1) - Binomial(n+k-1,1)*N^(k-2) - ... - Binomial(n+k-1,k-1)

###################################################################################

#3. 
Sum4:=proc(n) local k;
add(binomial(n,k)^6,k=0..n);
end;

S6seq:=proc(N) local n;
seq(Sum4(n),n=1..N);
end;

S6seq(30);
2, 66, 1460, 54850, 2031252, 86874564, 3848298792, 180295263810, 

  8709958973540, 433617084579316, 22071658807720392, 

  1145600816547477316, 60423221241495866600, 

  3231675487858598367240, 174928470621208572186960, 

  9568929614185118483080770, 528312173436681791506408260, 

  29410084375652468835825953700, 1649306291835755062635565266600, 

  93107634141997907386222914746100, 

  5287775212638388029439405881544200, 

  301944474035722816022868015938874600, 

  17327711158778580532167569829987114000, 

  998929514277820066081170252714511090500, 

  57829472148026421958694874354754572343752, 

  3360809774288550795907078936398005597675304, 

  196017195540724827646832723407084478623676432, 

  11470664176644488834345211155033799406490746120, 

  673328935324550345110207022300994902764916840400, 

  39638798311949179528552779569115309835946403522064

#this looks good as same as in the OEIS (A069865)

time(S6seq(1000));
                             13.400