#OK to post homework 
#Zhizhang Deng, 10/22/2020, Assignment 11

1. 
    There is Snk(11, 5) = 246730 ways to assemble 11 dolls into 5 different towers. 
    In general there are Snk(11, n) ways to assemble 11 dolls into n number of towers. The idea is that each tower can be viewed as a set of numbers. Because in each set, number can be sorted, so we can treat smaller number as smaller doll, and larger number as larger doll. So the problem becomes how many ways can we partition a set with 1->11 into n different subsets. which will be Snk(11, n)

2. 
    xn := proc(x, n) option remember; if n = 0 then: return x * (x + 1); end if; if n = 1 then: return x; end if; return (x - (n - 1)) * xn(x, n - 1); end; 

    Axn := proc(x, n) local k; option remember;add(Snk(n, k) * xn(x, k), k=0..n);end;

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

    Formula of Axn(x, n) for any non-negative integer n should be x 

3. 
    cycle notation of a general permutation p only contain 1 -> n - 1: {cycle1, cycle2, cycle3, ...}

    The idea th get c(n, k) from the current point is that after inserting n in the permutation now we look how can we insert n

    There are two cases, 
        case 1. we insert n such that it increases cycle amount by one
            in this case, the amount of of permutation is c(n - 1, k - 1). reason is that we can add n into it's separate cycle and can increase the cycle amount by 1. 
            some might argue that you can break existing cycle into two parts without creating a new cycle that only containing n thus can still achieve the goal of increasing cycle amount by 1. However, this is invalid in this case. As that would mean to insert n into one of the cycles while keeping n as the edge of the cycle. Which is accounted for in the second case, it didn't increase the amount of cycles at all, it's just puting k into another permutation that didn't change cycle amount at all. 

        case 2. we insert n such that it doesn't change the cycle amount  
            in this case, we need to insert k such that it doesn't change the cycle amount. this can be done by changing a cycle such as a-b-c-a into a-k-b-c-a. there are only n - 1 valid insertion  point for k as the head and the tail insertion point are the same. so we will have (n - 1) * c(n - 1, k)

    summing up these two cases, we have c(n, k) = c(n - 1, k - 1) + (n - 1) * c(n - 1, k)

4. 
    cnk := proc(n, k)
    option remember; 
        if n <= 0 then
            return FAIL;
        end if;
        if n = 1 then
            if k = 1 then
                return 1; 
            else
                return 0; 
            end if;
        end if;

        return 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 .. 5)
    = 
    x, x*(x + 1), x*(x + 2)*(x + 1), x*(x + 3)*(x + 2)*(x + 1), x*(x + 4)*(x + 3)*(x + 2)*(x + 1)

    my guess is this is like the reverse of xn where 
    formular should be x * (x + 1) * (x + 2) * ... (x + (n - 1))