#OK to post homework
#William Wang, 9/15/2020, Assignment 4


#1.
CP := proc(A, B) local a, b:
{seq(seq([a, b], a in A), b in B)}:
end:

CP({a, b, c}, {b, c, d});
{[a, b], [a, c], [a, d], [b, b], [b, c], [b, d], [c, b], [c, c], 

  [c, d]}



CheckMult := proc(A, B)
evalb(Mynops(CP(A, B)) = Mynops(A)*Mynops(B)):
end:

CheckMult({1, 2}, {3, 4});
                             false



CheckAdd := proc(A, B):
if not type(A, set) then
 print(A, `is not a set `):
 RETURN(FAIL):
fi:
if not type(B, set) then
 print(B, `is not a set `):
 RETURN(FAIL):
fi:
if A intersect B <> {} then
 print(A, B, `have the following common elements `, A intersect B):
 RETURN(FAIL):
fi:
#This checks that if A and B are disjoint finite sets, then
#|A U B| = |A| + |B|
evalb(Mynops(A union B) = Mynops(A) + Mynops(B)):
end:

CheckAdd({1, 2, 3}, {3, 4, 5});
 {1, 2, 3}, {3, 4, 5}, have the following common elements , {3}

                              FAIL



Words := proc(A, n) local W1, w, a:
option remember:
if n = 0 then
 RETURN({[]}):
else
 W1 := Words(A, n - 1):
 RETURN({seq(seq([op(w), a], a in A), w in W1)}):
fi:
end:

member([d, o, r, o, n], Words({d, n, o, r}, 5));
                              true



#2.
#Find the smallest positive integer such that 1,2,3,...,n (in Maple seq(i,i=1..n) only returns one hit, namely A27

seq(i, i = 1 .. 106);
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 

  19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 

  35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 

  51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 

  67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 

  83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 

  99, 100, 101, 102, 103, 104, 105, 106



#3.
#The principe of Inclusion Exclusion for two sets says that given a universal set U, and subsets A1, A2, defining the complement of a subset A of U by Comp(U,A),
#|Comp(U,A1) intersect Comp(U,A2)| = |A| - |A1| - |A2| + |A1 intersect A2|

#Check by hand for U = {1,...,15}, A1 = subset of U that are multiples of 3, A2 = subset of U that are multiples of 5
#A1 = {3,6,9,12,15}
#A2 = {5,10,15}
#A1 intersect A2 = {15}
#|A1| = 5
#|A2| = 3
#|A1 intersect A2| = 1
#|U| - |A1| - |A2| + |A1 intersect A2| = 15 - 5 - 3 + 1 = 8

#Comp(U,A1) = {1,2,4,5,7,8,10,11,13,14}
#Comp(U,A2) = {1,2,3,4,6,7,8,9,11,12,13,14}
#Comp(U,A1) intersect Comp(U,A2) = {1,2,4,7,8,11,13,14}
#|Comp(U,A1) intersect Comp(U,A2)| = 8

#Hence, for U={1,...,15}, A1 = subset of U that are multiples of 3, A2 = subset of U that are multiples of 5, it is true that
#|Comp(U,A1) intersect Comp(U,A2)| = |U| - |A1| - |A2| + |A1 intersect A2|

#Write a Maple procedure PIE2(U,A1,A2) that inputs three sets U, A1, A2. After checking that U, A1, A2 are indeed sets (return FAIL if they are not) and that A1 or A2 are subsets of U (return FAIL if they are not), computes it in two ways. The first by directly flinding |Comp(U,A1) intersect Comp(U,A2)| and the second way by using the above formula, namely |U| - |A1| - |A2| + |A1 intersect A2|

PIE2 := proc(U, A1, A2) local a, b:
if not type(A1, set) then
 print(A1, `is not a set`):
 RETURN(FAIL):
fi:
if not type(A2, set) then
 print(A2, `is not a set`):
 RETURN(FAIL):
fi:
if A1 intersect U = {} then
 print(A1, `is not a subset of `, U):
 RETURN(FAIL):
fi:
if A2 intersect U = {} then
 print(A2, `is not a subset of`, U):
 RETURN(FAIL):
fi:
a := nops((U minus A1) intersect (U minus A2)):
b := nops(U) - nops(A1) - nops(A2) + nops(A1 intersect A2):
[a, b]:
end:

PIE2({1, 2, 3, 4, 5}, {1, 2, 3}, {2, 3, 5});
                             [1, 1]


#4.
#Do the analogous thing for PIE3(U,A1,A2,A3)

PIE3 := proc(U, A1, A2, A3) local a, b:
if not type(A1, set) then
 print(A1, `is not a set`):
 RETURN(FAIL):
fi:
if not type(A2, set) then
 print(A2, `is not a set`):
 RETURN(FAIL):
fi:
if not type(A3, set) then
 print(A3, `is not a set`):
 RETURN(FAIL):
fi:
if A1 intersect U = {} then
 print(A1, `is not a subset of `, U):
 RETURN(FAIL):
fi:
if A2 intersect U = {} then
 print(A2, `is not a subset of `, U):
 RETURN(FAIL):
fi:
if A3 intersect U = {} then
 print(A3, `is not a subset of `, U):
 RETURN(FAIL):
fi:
a := nops(((U minus A1) intersect (U minus A2)) intersect (U minus A3)):
b := nops(U) - nops(A1) - nops(A2) - nops(A3) + nops(A1 intersect A2) + nops(A1 intersect A3) + nops(A2 intersect A3) - nops((A1 intersect A2) intersect A3):
[a, b]:
end:

PIE3({1, 2, 3, 4, 5}, {1, 2, 3}, {2, 3, 5}, {1, 3, 5});
                             [1, 1]


#5.
#Do the analogous thing for PIE4(U,A1,A2,A3,A4)

PIE4 := proc(U, A1, A2, A3, A4) local a, b:
if not type(A1, set) then
 print(A1, `is not a set`):
 RETURN(FAIL):
fi:
if not type(A2, set) then
 print(A2, `is not a set`):
 RETURN(FAIL):
fi:
if not type(A3, set) then
 print(A3, `is not a set`):
 RETURN(FAIL):
fi:
if not type(A4, set) then
 print(A4, `is not a set`):
 RETURN(FAIL):
fi:
if A1 intersect U = {} then
 print(A1, `is not a subset of`, U):
 RETURN(FAIL):
fi:
if A2 intersect U = {} then
 print(A2, `is not a subset of`, U):
 RETURN(FAIL):
fi:
if A3 intersect U = {} then
 print(A3, `is not a subset of`, U):
 RETURN(FAIL):
fi:
if A4 intersect U = {} then
 print(A4, `is not a subset of`, U):
 RETURN(FAIL):
fi:
a := nops((((U minus A1) intersect (U minus A2)) intersect (U minus A3)) intersect (U minus A4)):
b := nops(U) - nops(A1) - nops(A2) - nops(A3) - nops(A4) + nops(A1 intersect A2) + nops(A1 intersect A3) + nops(A1 intersect A4) + nops(A2 intersect A3) + nops(A2 intersect A4) + nops(A3 intersect A4) - nops((A1 intersect A2) intersect A3) - nops((A1 intersect A2) intersect A4) - nops((A1 intersect A3) intersect A4) - nops((A2 intersect A3) intersect A4) + nops(((A1 intersect A2) intersect A3) intersect A4):
[a, b]:
end:

PIE4({1, 2, 3, 4, 5}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {1, 4, 5});
                             [0, 0]