#OK to post homework
#Karnaa Mistry, 10/18/20, Assignment HW #11

with(combinat):

# 1. 

# Snk(11,5) = 246730 ways
# Bell1(11) = 678570 ways




# 2.

xn:=(x,n)->x!/(x-n)!:
Axn:=(x,n)->expand(add(Snk(n,k)*xn(x,k),k=0..n)):

# Using sum gives me 0 every time, so I'll use add instead.
# We find results for Axn(x,i) like: x (i=1), x + (x - 1)*x (i=2), x + 3*(x - 1)*x + (x - 2)*(x - 1)*x (i=3), 
# x + 7*(x - 1)*x + 6*(x - 2)*(x - 1)*x + (x - 3)*(x - 2)*(x - 1)*x (i=4)... But these get really long
# really fast, and so it would be difficult to fit it all here.  Instead, we can simplify Axn for these
# values of i and see if we get anything, and we do:
# seq(simplify(Axn(x,i)),i=1..20) = 
#     x, 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, x^15, x^16, x^17, x^18, x^19, x^20

# So, for n>=1, we could say Axn(x,n) = x^n




# 3.

# We can try to conceptualize c(n,k) by imagining the number of ways we can insert n into the cyclic notation
# of the permutations of size n-1 with k-1 cycles.  This could be the same as finding ways of removing n from
# permutations of 1 to n.  A base case could be n=1, giving the answer of c(0,k) = 0, since there are no 
# possible permutations of {1,..."0"} with k or k-1 cycles.  Also, if k > n, c(n,k) is 0.  We can say that
# c(0,0) = 1, because there is 1 permutation of Nothing such that it has 0 cycles (empty).  For c(1,1), we
# have c(1,1) = c(0,0) + 0 = 1, c(2,1) = c(1,0) + 1*c(1,1) = 1.  We can also see that c(n,0) = 0, n != 0.

# For any arbitrary permutation of size n with k cycles, let's see how we may remove the nth element.

# There are two possibilities, one where the nth element is in its own cycle (of size 1).  It doesn't matter
# "where" this size-1 cycle is, as that concerns visual notation and preference, just as (abc)(de)(n) is the
# same as (n)(de)(abc).  So, we will be left with the number of permutations of {1,...,n-1} with k-1 cycles
# (we subtracted 1 cycle).  This is c(n-1,k-1).  

# The other possibility is that the nth element was not in its own single-size cycle.  So, it can be
# removed from n-1 total positions, and the number of cycles stays the same (k).  This is because
# each cycle has a particular number of elements, and n may be removed from a position immediately after
# each element in each cycle, such as (abcden) -> (abcde), or (abncde) -> (abcde), etc.  We don't count
# positions in front of the cycle, since (abcden) = (nabcde).  Lastly, there were c(n-1,k) possible 
# permutations we could have after removing n, because we have to account for the arrangements of those
# cycles, too.  Multiplying n-1 choices by c(n-1,k) gives (n-1)*c(n-1,k).

# So, c(n,k) = c(n-1,k-1) + (n-1)*c(n-1,k) covers all important possibilities.




# 4.

#cnk(n,k): inputs positive ints n and k (1 <= k <= n) and outputs c(n,k)
cnk:=proc(n,k) option remember:
if n=0 then RETURN(1): fi:
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:




# 5.

# seq(factor(add(cnk(n,k)*x^k,k=1..n)),n=1..4) gives x, x*(1 + x), x*(x + 2)*(1 + x), x*(x + 3)*(x + 2)*(1 + x)

# An explicit expression for add(c(n,k)*x^k,k=1..n)  =  (x + n-1)*(x + n-2)*...*(x + 1)*x  =  (x + n-1)! / (x-1)!