#OK to post
# Soham Palande, Assignment 11, 10/18/2020




#PART 1

#This is equivalent to number of partitions of the set {1,2,3,4,5,6,7,8,9,10,11} containing exactly 5 
#elements

Snk(11,5)
	246730



#As the number of Russian dolls, n approaches infinity, lim Snk(n,k) as n-> infinity = infinity




#PART 2

xn:=proc(x,n) local res:
if n<0 then
  RETURN("FAIL"):
fi:
res:=product((x-i),i=1..(n-1)):
res:
end:


#EXAMPLE
xn(x,15)

(x-1)*(x-2)*(x-3)*(x-4)*(x-5)*(x-6)*(x-7)*(x-8)*(x-9)*(x-10)*(x-11)*(x-12)*(x-13)*(x-14)

#sum function was not giving the correct output so I added the terms manually using a for #loop


Axn:=proc(x,n) local res,res2,i:
res:=0:
res2:=0:
res:=seq(xn(x,k)*Snk(n,k),k=1..n):
for i in res do
 res2:=res2+i:
od:
res2:
end:

seq(Axn(x,i),i=1..20)


#PART 3

#c(n,k)=c(n-1,k-1)+ (n-1)*c(n-1,k)

#Where c(n,k) is the number of permutations of {1,...n} containing exactly k cycles.

# Proof:
# Let S be the set of permutations of {1,..n} containing exactly k cycles
# Then, for any permutation s in S, n 
# Case 1: Does not belong to any cycle and removing n leaves us with the set c(n-1,k-1)
# Case 2: Belongs to a cycle and then removing it results in a permutation of {1,...n-1} still 
#	  containing k cycles c(n-1,k)
# Then, in case 2, n can be inserted in (n-1) distinct positions (in all the cycles combined) to get  
# different permutations
# So, c(n,k)= c(n-1,k-1)+ (n-1)*c(n-1,k)

# Example for Case 2:
# In the permutation 5 2 4 3 1 represented in cycle notation as (1 5)(2)(3 4) removing 5 gives
# 1 2 4 3  or (1)(2)(3 4). Thus 5 can be inserted in (5-1)=4 distinct positions to get a 
# permutation of {1,2,3,4,5} having 3 cycles.


#PART 4

#The number of permutations of {1,..n} containing exactly k cycles
cnk:=proc(n,k) 
option remember:
if n=1 then
 if k=1 then
 RETURN(1):
 else
 RETURN(0):
 fi:
fi:

cnk(n-1,k-1)+(n-1)*cnk(n-1,k):

end:




#PART 5 and PART 6

# Explicit expression for
Sum(c(n,k)*x^k,k=1..n)
Initial Condition: c(n,0)=0, 

Let f(n):=sum(cnk(n,k)*x^k,k=1..n)

#f(n):= cnk(n,1)*x + cnk(n,2)*x^2 + cnk(n,3)*x^3 + ... + cnk(n,n)*x^n
#.    = [cnk(n-1,0)+(n-1)cnk(n-1,1)]*x + [cnk(n-1,1)+(n-1)cnk(n-1,2)]*x^2 + 
  	[cnk(n-1,2)+(n-1)cnk(n-1,3)]*x^3 + ... + [cnk(n-1,n-1)+(n-1)cnk(n-1,n)]*x^n


      = cnk(n-1,0)x+(n-1)cnk(n-1,1)x + cnk(n-1,1)x^2+(n-1)cnk(n-1,2)x^2 +
        cnk(n-1,2)x^3+(n-1)cnk(n-1,3)x^3 + ... + cnk(n-1,n-1)x^n+(n-1)cnk(n-1,n)x^n
      
      = (n-1)[cnk(n-1,1)x + cnk(n-1,2)x^2 + cnk(n-1,3)x^3 + ... + cnk(n-1,n)x^n] + 
        cnk(n-1,0)x + cnk(n-1,1)x^2 +  cnk(n-1,2)x^3 +...+ cnk(n-1,n-1)x^n 
    
      = (n-1)[f(n-1)] + cnk(n-1,0)x + cnk(n-1,1)x^2 +  cnk(n-1,2)x^3 +...+ cnk(n-1,n-1)x^n

      =