# NOT OK to post homework
# Michael Saunders, 9/27/2020, Homework 5
#

# load packages
#
with(combinat):

# include Maple procedures from ...
#

# 1. 
#
# If P(n) denotes the set of permutations of {1, ..., n} and p(n) := |P(n)|,
# then p(n) := n * p(n - 1):
# hence, p(n) := n!:
#
# Find a proof, explaining everything, of p(n) = |P(n)|, by breaking-up P(n)
# into the sets...
# P_j(n) := {All permutations pi in P(n) such that pi[1] = j, for j = 1..n:
#
# Let n = 1. 
# P_1(1) := {1}:
#
# Let n = 2.
# P_1(2) := {12}:
# P_2(2) := {21}:
#
# Let n = 3.
n := 3:
# P_1(3) := {123, 132}:
# P_2(3) := {213, 231}:
# P_3(3) := {312, 321}:
#
# Let n = 4.
# P_1(4) := {1234, 1243. 1324, 1342, 1423, 1432}:
# P_2(4) := {2134, 2143, 2314, 2341, 2413, 2431};
# et cetera...
#
# We can see that |P_j(n)| = |P(n-1)|.
# E.g.	|P_1(2)| = |P(1)| = 1
#		|P_2(2)| = |P(1)| = 1.
#		-->|P(2)| = 2 * |P(1)| = 2 = 2!
#
#		|P_1(3)| = |P(2)| = 2
#		|P_2(3)| = |P(2)| = 2
#		|P_3(3)| = |P(2)| = 2
#	    -->|P(3)| = 3 * |P(2)| = 6 = 3!
#
# and so on... 
#
#		|P_j(4)| = |P(3)| = 

#
# 2.
#
# Let a1,a2,a3 be distinct positive integers and let P(n;a1,a2,a3) be the set of
# words in the alphabet {a1,a2,a3} of any length that add-up to n.
# E.g. P(3; 1,2,3) = {111, 12, 21, 3}.
# Decompose P(n;a1,a2,a3) into smaller sets, and deduce a reccurence relation
# for p(n) = p(n;a1,a2,a3) := |P(n;a1,a2,a3)|