# Please do not post homework
# Hari Amoor, 9/20/2020, Assignment 3

# Problem 1

Bnk(10, 5)[20]

# [0, 0, 0, 1, 1, 1, 1, 0, 1, 0]

MyChoose({1,2,3,4,5,6},2)[5]

# {1, 6}

MyPermsL([r,u,t,g,e,r,s])[100]

# [r,u,s,t,e,r,g]

WtoS([1, 0, 0, 0, 1])

# {1, 5}

# Problem 2

NuFP:=proc(L) local i,n,R:
n:=nops(L):
R:={}:

for i from 1 to n do
  if L[i]=L[L[i]] then
    R:=R union {i}:
  fi:
od:

nops(R):
end:

# Problem 3

Der:=proc(n) local X, R, i, l:
X:=MyPerms(n):
l:=nops(X):
R:={}:

for i from 1 to l do
  if NuFP(X[i])=0 then
    R:=R union {X[i]}:
  fi:
od:

R:

:end

# Problem 4

[seq(nops(Der(i)), i=0..8)]

# [1, 0, 1, 2, 9, 44, 265, 1854, 14833]

# You can find these numbers in OEIS. Euler proved the recurrence relation
# a(n) = (n-1)*(a(n-1) + a(n-2)) and a(n) = n*a(n-1) + (-1)^n for this
# sequence, for natural i.

# Problem 5

[seq(nops(Comps(i)), i=1..8)]

# [1, 2, 4, 8, 16, 32, 64, 128]
# We conjecture that the formula is nops(Comps(n))=2^(n-1).

# Problem 6

# Claim: The cardinality of Comps(n), denoted |Comps(n)|, is equal
# to 2^(n-1).

# Proof:
# We prove the claim with mathematical induction.

# Base Case: |Comps(1)| = 1 holds because Comps(1) = [1]. This holds.

# Inductive Step: Suppose the inductive hypothesis holds for some natural
# number n. We use the Maple notation to denote that
# Comps(n + 1)={seq([op(Comps(n)), 1]), seq([1, op(Comps(n))])}. We can
# see that |Comps(n + 1)| = 2 * |Comps(n)| = 2^((n + 1) - 1) = 2^n.
# Thus. the inductive step holds.

# By the principle of mathematical induction, the claim holds.

# QED