Last Update: March 21, 2017.
We will first learn Maple, and how to program with it. This semester we will learn algebraic combinatorics, and the powerful theory of symmetric functions. This is a beautiful subject for its own sake, and approaching it from the standpoint of computer algebra will make it crystal clear.
In addition to the actual, very important content, students will master the methodology of computer-generated and computer-assisted research that is so crucial for their future.
There are no prerequisites (except for mathematical maturity). In particular, no prior knowledge of Maple, or any programming experience, is assumed. Also, no overlap with previous years.
It should be sent to the email address
ShaloshBEkhad at gmail dot com
Subject: HomeWork#X
and then attach a .txt file(s) called
hwXYourFirstNameYourLastName.txt
where X is the number of the assignment
Except for the first assignment, you should have two attached .txt files.
For example, when Anthony Zaleski submits homework assignments 2 and 3, he should email ShaloshBEkhad at gmail dot com, with
Subject: HomeWork#2#3
and attach the text files (the source code plus human comments (such lines must start with #)
hw2AnthonyZaleski.txt and hw3AnthonyZaleski.txt
#Please do not post homework
or
#OK to post homework
Followed by
#Your Name, Date, Assignment X
W(n): Inputs a non-negative integer n, and outputs the set of Lattice walks with n steps in the 2D lattice
with units steps in each direction, where
1:East, -1:West 2:North -2: South
w(n): inputs a non-negative integer n, and outputs the NUMBER of Lattice walks with n steps in the 2D lattice, using a very clever and sophisticated recurrence: w(n)=4w(n-1).
Subject: hw#1
and an attachment
hw1FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Read and do all the examples, plus make up similar ones,
in the first 30 pages of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw1YourName.txt .
Note: a few commands are no longer valid in today's Maple. The
most important one is that " has been replaced by %.
[Optional, but strongly recommended for novices]
Generalize SW(n) to write a procedure
GSW(n,S)
that inputs a positive integer n, and a set of two-dimensional vectors with integer entries, the set of fundamental steps and outputs the set of self-avoiding walks of length n. The output of GSW(n,{[1,0],[-1,0],[0,1],[0,-1]}) should be the same a SW(n).
SeqGSW(N,S)
that outputs the list, of length N, of the cardinalities of GSW(n,S), from n=1 to n=N.
Which of the following are in the OEIS
SeqSWfm(N,d)
that outputs the list, of length N, of the cardinalities of SWfm(n,d), from n=1 to n=N.
Which of the following are in the OEIS
NuC(n,S): inputs a non-neg. integer n, and a finite set of POS. integers, S and outputs the NUMBER of lists whose entries are from S and that add-up to n, in other words, the output is the same as nops(Comp(n,S)), but of course much faster.
Subject: hw#2
and an attachment
hw2FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 2
Read and do all the examples, plus make up similar ones,
in pages 30-60 of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw2YourName.txt .
Note: a few commands are no longer valid in today's Maple. The
most important one is that " has been replaced by %.
Write an analog of CompC(n,C), call it
PartitionsC(n,C)
with the same inputs, a non-neg. integer n, and a function C that inputs a positive integer and outputs a condition (e.g. n-> n mod 2=1) and outputs the set of PARTITIONS of n (weakly-decreasing vectors that add-up to n.
[Hint, you may want to first write a program PartitionsC1(n,m,C) for the set of partitions of n whose largest part is m, and that satisfies the condition C, and then take the union of these for m from 1 to n]
[Optional, but strongly recommended for novices; MANDATORY FOR EXPERTS] Write an enumeration analog of the above, call it
NuPartitionsC(n,C)
SeqNuPartitionsC(N,C)
that outputs the first N+1 terms, starting at n=0.
SeqNuPartitionsC(30,m->m mod 5=2 or m mod 5=3)
SeqNuPartitionsC(30,m->m mod 7=1 or m mod 7=2 or m mod 7=4)
Subject: hw#3
and an attachment
hw3FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 3
Read and do all the examples, plus make up similar ones,
in pages 60-90 of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw2YourName.txt .
Note: a few commands are no longer valid in today's Maple. The
most important one is that " has been replaced by %.
Write a procedure
WtE(m,S,t)
that inputs a positive integer m, a subest S, of {0,...,m-1}, and a variable-name t, and outputs the rational function whose coefficient (in its Maclaurin expansion) of t^n is the number of compositions of n (vectors of positive integers) whose components only belong to the residue classes
s (mod m) for s in S
What are
WtE(5,{1,4},t); WtE(7,{3,7},t);?
Subject: hw#4
and an attachment
hw4FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 4
Read and do all the examples, plus make up similar ones,
in pages 90-end of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Comp([L1,L2],t)
that inputs a list of integers L1 all relatively prime, and another list of integers L2, of the same length, such that
L2[i] is between 0 and L1[i]-1 (inclusive), and outputs the generating functions whose coefficients of t
L2[i] (mod L1[i]), i=1..nops(L1)
Hint: Use chrem (Chinese remaindering) and Inclusion-Exclusion to first find the generating function (weight-enumerator) of the set of integers that belong to that union.
Subject: hw#5
and an attachment
hw5FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 5
GoodWords(A,BadW,n)
that inputs
CheckGJ(A,BadW,N)
that checks that the coefficient of t^n in GJ(A,BadW,n) equals nops(GoodWords(A,BadW,n)) for n from 0 to N.
GJs(A,BadW,t,s)
that inputs the same arguments as GJ, and in addition, a variable s, and outputs the rational function in t and s, whose coefficient of t^n is the polynomial in s that is the weight-enumerator of n-letter words in the alphabet A according to the weight s^{NumberOfBadSubWords}. Of course, when s=0 you should get the old output, and when s=1, you should get 1/(1-t*|A|).
Hint: Instead of the trivial identity 0=1+(-1), use the deep identity s=1+ (s-1). Everything should extend in Clu with -1 replaced by s-1.
Write a procedure
CleanUp(BadW)
that inputs a set of words, and outputs the subset of minimal words. For example
CleanUp({[1,2,1,2],[2,1],[1,2,3,4],[2,3]});
should output {[2,1],[2,3]}
Let a(n) be the number of ways of tossing a coin n times and never getting two consecutive Heads, and let b(n) be the number of ways of tossing a coin n times so that you never get three consecutive Heads and never get three consecutive Tails. Then, for n ≥ 1, we have
b(n)=2a(n-1)
ArielR(A,Pr,BadW,t): [Inspired by pp. 74ff of
Ariel Rubinstein's masterpiece
Economic Fables
(highly recommended), (BTW, Ariel Rubinstein was Dr. Z.'s army buddy)]
Inputs a list of letters, A, the "alpbhabet" (think of a die with any number of faces ) with a prob. dist.
Pr (prob. of the die lending on A[i] os Pr[i]), a set of words in A
and outputs a rational generating function whose coeff. of t^n (in its Maclaurin expansion) is the
Exact prob. of rolling the die n times and getting NO occurrence of BadW (thereby winning 25 dollars)
Subject: hw#6
and an attachment
hw6FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 6
Prove Humanly, that if there is a rational function N(t)/D(t), whose denominator's smallest root (in absolute value) is distinc and positive, let's call that smallest root 1/α, then if a(n) are coefficients of its Taylor expansion
sum(a(n)*t^n, n=0..infinity) = N(t)/D(t) then
a(n) is asymptotic to C*(α)^n, for some constant C. Let's call α the GROWTH CONSTANT. Can you find an expression for C? (in terms of N(t), D(t) and α) .
It follows from the Goulden-Jackson algoritm that for any set of words BadW, in any alphabet, the sequence a_w(n) enumerating the number of words of length n in the alphabet A that avoid w as a cosecutive subword is asymptotic to C*(α_{w})^{n} for some constant α_{w} (< |A|). Let's call that number its growth-constant. Write a program
GC(A,Badw)
that inputs an alphabet A, and a set of words Badw, and outputs the growth constant of the sequence enumerating n-letter words avoiding the members of Badw. The output should be a floating-point number.
Ranker(m,k)
that inputs positive integers m and k, and outputs the list of length m^k that lists all the k-letter words in the alphabet {1,...,m} according to their growth constant, togetger with their respective growth constant.
What are
Ranker(2,2), Ranker(2,3), Ranker(2,4), Ranker(3,3)?
Hint: The alphabet is {-1,1,2,-2} and the "bad words" are [-1,1],[1,-1],[2,-2],[-2,2], and [1,2,-1,-2] and all its images under the group of signed-permutation of order 2.
Subject: hw#7
and an attachment
hw7FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 7
PlotT(T,Rx,Ry,dx,dy,eps), that inputs a complete binary tree T
and write a procedure
PlotTg(T,Rx,Ry,dx,dy,eps)
that inputs any ordered tree (not necessarily a complete binary tree) and plots it.
Plot and save (as a .jpg or .gif file) the picture for
PlotTg( [ [[]$3]$4, [[]$5]$2] ,0,0,10,10,2);
Comp(n,k)
that inputs a positive integer n, and another positive integer k (k ≤ n), and outputs the set of compositions of n into exactly k parts.
For example
Comp(5,3)={[3,1,1],[1,3,1],[3,1,1],[2,2,1],[2,1,2],[1,2,2]} .
Using procedure Comp(n,k) (with various k's) write a procedure
gTreesLeaves(n,S) ,
that inputs a positive integer n, and a set of positive integers S, and outputs the set of ordered trees on n LEAVES where each vertex is either a leaf (has zero children), or its number of children is a member of S. For example
gTreesLeaves(n,{2})=BT(n) .
Hint: You may want to write a procedure (of find out whether Maple has one)
CartProd(ListOfSets)
that inputs a list of sets and outputs their Cartesians product (if ListOfSets=[S1, ..., Sk], the set of lists [s1,..., sk] with s1 in S1, ..., sk in Sk). (the best way is to recurse on the length of ListOfSets).
gTreesVertices(n,S) ,
that inputs a positive integer n, and a set of positive integers S, and outputs the set of ordered trees on n VERTICES where each vertex is either a leaf (has zero children), or its number of children is a member of S.
Pick some random trees in gTreesVertices(10,{1,2,3}) and plot them using PlotTg(T,Rx,Ry,dx,dy,eps) that you have nicely written above.
Added Oct. 4, 2016: See the students' nice solutions.
Today the class was fortunate to have a guest lecture by the great GURU, Neil Sloane the founder and President of the amazing OEIS
Slides for Dr. Sloane's Oct. 3, 2016 Guest Lecture
TseqV(S,N): the first N terms from n=1 to n=N for the number of
ORDERED TREES with n VERTICES, where any vertex can have either zero children
or a number of children in S
(Using the algebraic equation f=x+x*add(f^s, s in S))
Subject: hw#9
and an attachment
hw9FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 9
SeqManyCL(i,N)
that inputs a positive integer i, and a positive integer N, and outputs the first N term of the sequence enumerating ordered trees with n LEAVES, where every vertex either has no children, or at least i children.
Which ones are in the OEIS? (indicate the A numbers, if they are). Are they for this reason, or a different one?
SeqManyCV(i,N)
that inputs a positive integer i, and a positive integer N, and outputs the first N term of the sequence enumerating ordered trees with n VERTICES, where every vertex either has no children, or at least i children.
Which ones are in the OEIS? (indicate the A numbers) SeqManyCV(1,30);SeqManyCV(2,30);SeqManyCV(3,30); SeqManyCV(4,30);
baS(h,d) (where h ≥ d)
Prove it my induction, using the recurrence used to in baS(h,D) to get the numbers in the first place, and checking the initial conditions and boundary condition when d=h+1.
Deduce the fact that baS(n,n)=C(n), the Catalan number.
[Challenge, 4 dollars to be divided, corrected Oct. 7, 2016 (thanks to Jinyoung Park)]
Find a bijection between the set of COMPLETE BINARY TREES on n leaves and the set of ballot sequences with n-1 H's and n-1 D's . Program both directions in Maple.
[Hint: for us humans, it is helpful to visualize a ballot sequence as a walk in the 2D plane, starting with [0,0] and H=[1,1], D=[1,-1]. Note that these walks never venture below the x-axis]
[Challenge, 10 dollars to be divided]
Give a bijective proof of the fact that the number of complete binary trees on n leaves is
a(n):=binomial(2n-2,n-1)/n
By giving a bijective proof of the recurrence
na(n)= 2 (2n-3) a(n-1)
Implement both directions in Maple, and make sure that their composition is the identity (in both directions).
[Very slight Hint: the left side counts complete binary trees with one of the leaves marked (that's the input set). The right side counts the number of elements in the Cartesian product of a two-element set (perhaps {Left, Right}), a "natural" set of cardinality 2n-3, and the set of complete binary trees with n-1 leaves.
Added Oct. 10, 2016: See the students' nice solutions.
Bell1(N): the list consisting of the N first Bell numbers
Subject: hw#10
and an attachment
hw10FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 10
LId(P,G,z,N) and LI(P,G,z,N)
implementing the Generalized Lagrange Inversion Formula as described in the above-mentioned writeup.
[Optional Challenges] Solve, as many problem as you can from American Mathematical Monthly Problems for Oct. 2016
Added Oct. 17, 2016: See the students' nice solutions.
Contains procedures
Subject: hw#11
and an attachment
hw11FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 11
RSPn(n)
that inputs a positive integer n, and outputs a (uniform-at-random) set partition of {1, ..., n}
B(n)=Sum(binomial(n-1,k-1)*B(n-k),k=1..n) ,
(proved by deciding who would be the set-mates of element n), write an alternative procedure
RSPnNew(n)
that outputs a random set-partition.
Hint: you first need to write a subroutine, RSubSetnk(n,k) that picks a uniform-at-random k-subset of an n-element set {1, ..,n} .
RandomBallotSequence(m,n)
that inputs non-neg. integers, m, n, such that m ≥ n, and outputs a (uniformly-at) random ballot sequence with m Hillarys and n Donalds, i.e. where Donald was NEVER ahead of Hillary
Added Oct. 17, 2016: See the students' nice solutions.
Contains procedures
LT(n): inputs a pos. integer n and outputs the set of labeled trees on n vertices
AJ(f): inputs a list of length n, say, consisting of {1,...,n} such that i goes to f[i] (representing a function from {1, ...,n} to {1, ...,n} (n^n of them), outputs the DOUBLY-ROUTED tree given by Joyal's bijection. The format of the output is [LabeledTreeGivenAsASetOfEdges, [FirstRoot, SecondRoot]]
Subject: hw#12
and an attachment
hw12FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 12
Rfun(n)
that inputs a positive integer n, and outputs one of the n^{n} lists of length n with entries from {1, ...,n}, each with the same probability, use procedure AJ(f), to write a (short!) procedure
RLT(n)
that inputs a positive integer n, and outputs one of the n^{n-2} labeled trees, each with the same probability.
( Hint, apply AJ, and then discard the second component [FirstRoot,SecondRoot] )
NuLeaves(T)
that inputs a labeled tree on {1, ...,n}, say, given as a set of n-1 edges, and outputs the number of vertices that are leaves (have degree 1)
AveNuLeaves(n,K)
that inputs a positive integer n, and a fairly large positive integer K, and finds the average number of leaves in a random sample of K labeled trees with n vertices, and hence forms an approximation for the real average.
What did you get for
AveNuLeaves(50,1000)? AveNuLeaves(100,1000)? AveNuLeaves(150,1000)? AveNuLeaves(200,1000)?
Is it reasonable to conjecture, that as n goes to infinity, the average/n tends to a fixed number? Can you guess that number.
[Added Oct. 20, 2016. In fact, there is a nice very closed-form solution for the average number of leaves. You can get it as follows. Let f(s,t) be the exponential generating function for the sequence of Leaf polynomials, let's call is L_n(s), whose coefficient of s^i is the number of ROOTED labeled trees with i leaves. Then instead of the equation
f(1,t)=t*exp(f(1,t))
for straight enumeration, you have
f(s,t)=t*(s-1+exp(f(s,t))
Now use Lagrange inversion to express L_n(s) as (n-1)! times the coefficient of z^(n-1) in ((s-1)+exp(z))^n. From this you should get L_n'(1) and hence the average L_n'(1)/n^(n-1) , that happens to be a nice closed form]
Added Oct. 24, 2016: See the students' nice solutions.
Contains procedures
Subject: hw#13
and an attachment
hw13FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 13
pnkC(n,k,CongrConditions, DifferenceCondition) and pnC(n,CongrConditions, DifferenceCondition)
where the additional inputs, CongrConditions is a set of congruences where "a mod b" is written [a,b], and DiffCondition is a positive integer. The output of pnC(n,CongrConditions, DifferenceCondition) should be the number of partitions of n whose parts satsifies one of the congruences, and the difference between consecutive parts is ≥ d. For example
pn(n)=pnC(n,{[1,1]},0)
pnC(n,{[1,2]},0) is the number of partitions of n into odd parts, and pnC(n,{[1,1]},1) is the number of partitions into distinct parts.
Added Oct. 24, 2016: See the students' nice solutions.
Contains procedures:
Subject: hw#14
and an attachment
hw14FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 14
arctan(x) -arctan(y)=arctan( (x-y)/(1+x*y)) (corrected Oct. 24, 9:26pm, the previous version had a sign error, pointed out by Anthony Zalelski.)
Write a procedure
MakeMonthlyProblem(R,n)
that inputs an expression R in the variable n, computes the simplified version of tan(arctan(R(n))-arctan(R(n-1))), and then poses a problem in the style of Problem 11930 in American Mathematical Monthly Problems for Oct. 2016. It should be written in a style ready to be submitted.
What are
nuSYT:=proc(L): nops(SYT(L)):end )
nuSYT([n,n]) , nuSYT([n,n,n]) , nuSYT([n,n,n,n]) ,
then check them out in the OEIS.
SumSYTpower(n,k) ,
that inputs positive integers n and k, and outputs the integer
a_k(n):=Sum(NuSYT(L)^k, L in P(n)) ,
Can you conjecture an explicit expression, in n, for a_1(n)?, a_2(n)?, a_3(n)? Are any of them in the OEIS?
Added Oct. 31, 2016: See the students' nice solutions.
Contains procedures:
Sym(f,x,n): inputs an expression f in the indexed variables x[1], ..., x[n], a letter x, and a positive integer n, outputs the symmetrizer
Subject: hw#15
and an attachment
hw15FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 15
Conj(L)
that inputs a partition, L, and outputs its conjugate partition. For example, "Conj([3,2]);" should return [2,2,1]
Check17(L,m,n)
that confirms Statement (1.7) on p.3 of Ian Macdonald's book, for a partition L and integers m ≥ L[1], and n ≥ nops(L) (alias L'[1])
eTomMatrix(n)
that inputs a positive integer n, and outputs a nops(P(n)) by nops(P(n)) matrix, represented as a list of lists, let's call it MAT, such that MAT[i][j] is the coefficient of mL[P[j]] in eL(x,P[i],n).
What are: eTomMatrix(n1), n1=1..7 ?
[Warning: Please use the current version of C15.txt that has been modified after class, or else ToM will not run properly]
Added Oct. 31, 2016: See the students' nice solutions.
Contains procedures:
Shape:=proc(T) local i: [seq(nops(T[i]),i=1..nops(T))]: end:
Subject: hw#16
and an attachment
hw16FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 16
SameShapePairs(n)
that inputs a positive integer, n, and outputs the set of all pairs of standard Young Tableaux of the same shape.
Write a one-line procedure
VerifyRSK(n)
that verifies that the range of the Robinson-Schensted Correspondence is indeed SameShapePairs(n). Check it up to n=8.
Invert1(pi)
that inputs a permutation pi and outputs its inverse.
Use this fact to deduce that the number of Standard Young Tableaux with n boxes equals the number of involutions (permutations that are equal to their inverse) of n.
RSK(pi)=[T1,T2] iff RSK(pi^(-1))=[T2,T1]
iRSK(TableuxPair)
tnat inputs a pair of Standard Young Tableaux of the same shape TableuxPair=[T1,T2] and outputs a permutation pi such that iRSK(RSK(pi))=pi
Verify that both RSK(iRSK) and iRSK(RSK) are the identity mappings on their respective domains (i.e. SameShapePairs(n) and permute(n), respectively, for n ≤ 8
Added Nov. 7 2016: See the students' nice solutions.
Contains procedures:
Subject: hw#17
and an attachment
hw17FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 16
Con1G(L,c1,c2,c3)
that inputs a list L of length 6 indicating how many voters vote, respectively for the rankings 123,132,213,231,312,321, and integers c1,c2,c3
and outputs true iff
the number of voters who prefer 1 to 2 exceeds the number of voters who prefer 2 to1 by least c1
the number of voters who prefer 2 to 3 exceeds the number of voters who prefer 3 to 2 by at least c2
the number of voters who prefer 3 to 1 exceeds the number of voters who prefer 1 to 3 by at least c3
(Note that Con1G(L,1,1,1) is Con1(L) we did in class)
RVloaded(p)
that inputs a prob. distribution [p123, ..., p321] and generates [1,0,0,0,0,0] with prob. p123, .... , [0,0,0,0,0,1] with prob. p321.
MCconG(n,N,p) : that Simulates N elections with n voters, where the voters choose one of the six rankings according to p. and outputs the ratio of those elections that ended up with the Condorcet scenario.
Note that MCconG(n,N,[(1/6)$6]) is the same MCcon(n,N).
Play around with different choises of loaded dice. How do they differ from the outcome of the fair die?
Added Nov. 7 2016: See the students' nice solutions.
Contains procedures:
Subject: hw#18
and an attachment
hw18FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 18
hni(n,i,x)
that outputs h_{i} (x_{1},..., x_{n}) with the above definition
Hni(n,i,x)
that implement this definion. Convince yourself that they are the same, first by trying out small values of n and i, and then prove it humanly.
p_{i} (x_{1}, ..., x_{n})= x_{1}^{i} + ... + x_{n}^{i}
Write a "p-analog" of eL(x,L,n), call it pL(x,L,n), then write "p-analogs" of eTom(n) and mToe(n), call them pTom(n) and mTop(n)
TransMatrix(n,base1,base2,m,e,h,p)
where base1, base2, are members of the set {m,e,h,p} , and outputs the transition matrix from the base1 basis to the base2 basis. Of course, if base1=base2 you would get the identity matrix, so for each n, you get 12 non-trivial matrices.
Print out all these 12 matrices for n from 1 to 6 (in an organized manner)
Added Nov. 14 2016: See the students' nice solutions.
contains procedures:
{DO NOT USE, FOR REFERENCE ONLY]
Subject: hw#19
and an attachment
hw19FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 19
Comment: As Justin noticed the attempt in class was flawed.
Added Nov. 14 2016: See the students' nice solutions.
contains procedures:
Subject: hw#20
and an attachment
hw20FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 20
ChecksLd1(n) and ChecksLd2(n) ,
that checks that sLd1(L,x) and sLd2(L,x) coincide with sLcF(L,x) for all the partitions of n. What is the largest n that you could verify it for (in a reasonable amount of time)
maj(4132657)=1+3+5=9 .
Can you conjecture a nice expression for the weight-enumerator of the set of permutations of {1, ...,n} (i.e. the sum of q^{maj(pi)} taken over all permutations pi of {1, ..., n})?
Added Nov. 21 2016: See the students' nice solutions.
contains procedures:
Subject: hw#21
and an attachment
hw21FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 21
GuessAndProveBW4(a,b,c,d)
(it may take a bit longer then GuessAndProveBW3(a,b,c))
F_{k}(a1, ..., ak)
for the number of Young tableaux of shape (a1, ..., ak) (where a1>=...>ak>=0) and program it into a general procedure
Fk(k,a)
in terms of a[1], ..., a[k]
ProveYoungFrobeniousMacMahon(k)
that inputs a positive integer k, and outputs true iff the formula for Fk(k,a) is true (supplying a rigorous proof for this particular k). How high can you get k to be.?
Added Nov. 21 2016: See the students' nice solutions.
contains procedures:
Subject: hw#22
and an attachment
hw22FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 22
Ffast(L)
that has the same input and output as F(L) (i.e. it inputs a shape and outputs the number of standard Young tableaux of that shape) but that uses the Young-Frobenius-MacMahon formula rather than the recurrence., and then use it to write
RYTfast(L)
that does the same thing as RYT(L) (i.e. it inputs a partition and outputs a random SYT of that shape), but using Ffast(L) rather than F(L). What is faster
RYT([20$10]) or
RYTfast([20$10]) .
RandSetnk(n,k)
That inputs positive integers k,n (k<=n), and outputs a subset of {1,...,n} with k elements, each with prob. 1/binomial(n,k) .
RandPar(n) ,
that inputs a positive integer n, and outputs a random (integer) partition of n.
[Hint, let pnk(n,k) be the number of partitions of n with largest part k, use the fact that
p(n)=Sum(pnk(n,k),k=1..n)
and the obvious recurrence for pnk(n,k) in terms of pnk(n-k,s) for s<=k .
RandSetPartition(n)
that inputs a positive integer n, and outputs each of the Bell(n) set-partitions of {1,..,n} with prob. 1/Bell(n)
Hint: You may use the recurrence
Bell(n)=Sum(binomial(n-1,k-1)*Bell(n-k),k=1..n)
and use, as a subroutine RandSetnk(n,k) above (with n replaced by n-1) .
Added Nov. 28 2016: See the students' nice solutions.
contains procedures:
Subject: hw#23
and an attachment
hw23FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 23
AveTimeRYTfast(L,N) , AveTimeGNW(L,N)
that inputs a (rather large) partition L, and a (rather large integer N), runs the procedure RYTfast(L) (from hw22.txt) N times, and finds the average running time (by using the Maple command time()), and ditto for procedures GNW(L).
What did you get for
AveTimeRYTfast([50$50],30) and AveTimeGNW([50$50],30)?
Who won. If these numbers are small, try to make L larger.
Added Nov. 28 2016: See the students' nice solutions.
contains procedures:
Subject: hw#24
and an attachment
hw24FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 24
InnerProd(n)
that inputs a positive integer n, and outputs the nops(P(n)) by nops(P(n)) matrix (expressed as a list of lists) let's call it L, such that L[i][j] is the inner product of m_{P(n)[i]} and m_{P(n)[j]} under the inner product defined by eq.(4.5) (p. 63) of Macdonald's Symmetric Functions Book .
[Note added Dec. 1, 2016: Jinyoung Park and Yonah Biers-Ariel noticed that this matrix already exists in this class. Which one?]
sLA(L,M)
that inputs a partition L and outputs s_{L} expressed in terms of the M's. For small n, check that it coincides with the other definitions of Schur polynomials.
[Note added Dec. 1, 2016: You may want to use the Gram-Schmidt orthogonality algorithm]
Added Dec. 5, 2016: See the students' nice solutions.
contains procedures:
Subject: hw#25
and an attachment
hw25FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 25
Modify procedure TabsBE(L,k) from C20.txt (reproduced in C25.txt) to write a procedure
TabsBEg(L,M,k)
that inputs partitions L and M and a positive integer k, and outputs the set of column-strict tableaux of skew-shape L\M with largest integer k.
There is a trivial 1-1 correspondence between Standard Young Tableaux of shape N=[N1,N2,N3..] and words with N1 1's, N2 2's, N3 3's.. that are "ballot words", i.e. the have the property that for every prefix the number of 1's is always >= the number of 2's >= the number of 3's ...
Write a procedure
SYTtoBallotWord(N)
that implments it.
BW(N)
that inputs a partition N and outputs the set of ballot words with N[1] 1-s., N[2] 2-s, etc.
A Littlewood-Richrardson tableau of shape L\M and weight N is any way if filling-in a member BW(N) into the cells of the skew-shape L\M in "Arabaic" (or Hebrew), i.e. from right-to-left and from top-to-bottom such that the resulting skew-tableau is column-strict. Write a procedure
LR(L,M,N)
that inputs partitions L and M (where M is a sub-partition of L) and a partition N such that |N|=|L|-|M|, and outputs the subset of BW(N) such that if you fill-in L\M as above you get a Littlewood-Richardson skew-tableau of shape L\M.
CheckLRrule(n)
that inputs a positive integer l, and checks that
nops(LR(L,M,N))=LWc(L,M,N)
for every partition L of l, and for all partitions M and N such that |M|+|N|=l
Thereby proving, experimentally, the famous Littlewood-Richardson rule for all partitions L of l.
How far can you go in a reasonable ammount of time?, i.e. what is the largest l? that finishes in less than 10 minutes?
Added Dec. 5, 2016: See the students' nice solutions.
contains procedures:
[Note, right now it is not in order, one of the homework problem is to finish it up]
[Added Dec. 7, 2016: Justin Semonsen noticed (and won a dollar), that it is even more incomplete than what I believed before. It tacitcly assumes that all the eigenvalues of the matrix DaM(a,n) have multiplicity 1. As pointed out by Andrew, this is false for n=6. I beleive that using the renormalization one can "diagonalize" the eigenspaces with dimensions larger than 1, so that's another challenge].
MacM(q,t,n): the p(n) by p(n) matrix whose i-j entry is the coeff. of M[P(n)[j]] of Macdonald_{q,t}[P(n)[i]]:
[Note, right now it is not in order, one of the homework problem is to finish it up]
[Added Dec. 7, 2016: The above phenomenon, noticed by Justin Semonsen does not occur for n=6, but I am not sure whether it starts showing up for larger n].
Subject: hw#26
and an attachment
hw26FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 26
Added Dec. 7, 2016 (as pointed out above, you first have to correct the error we did in class where we tacitly assumed that all the eigenspaces are one-dimensional, so this problem is more challenging than I thought.
Added Dec. 12, 2016: See the students' nice solutions.
contains procedures:
SeqGG(P,N): inputs a set of patterns P, and a positive integer N returns the list of length N whose i-th entry is the NUMBER of permutations of length i NOT containing any of the patterns in P
Subject: hw#27
and an attachment
hw27FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
Also have in the second line
#YourName, Math 640 (Fall 2016) homework assignment 27
HowMany(pi,p)
that inputs a permutation pi and a pattern, p, and outputs the number of occurrences the pattern p occurs in pi. Note that if Howmany(pi,p)=0 then pi avoids p.
GGgen(Pset,n)
that inputs a set of pairs, Pset, where each member is a pair [p,a_p], where a_p is a nonnegative integer, and a positive integer n, and outputs the set of permutations of length n such that for each member [p,a_p] of Pset, the number of occurrences of the patter p is <=a_p. If all the a_p=0 then we are back to pattern-avoidance.
SeqGGgen(P,N), where P is as above, and N is a positive integer, and outputs the list of cardinalities of GGgen(Pset,i) for i from 1 to N.
[i.e. the number of permutations of n with at most one occurence of the pattern 123]. What about SeqGGgen({[[1,2,3],1]},8)-SeqGGgen({[[1,2,3],0]},8), the number of permutations of n with EXACTLY one occurence of the pattern 123].
[i.e. the number of permutations of n with at most two occurence of the pattern 123]. What about SeqGGgen({[[1,2,3],2]},8)-SeqGGgen({[[1,2,3],1]},8), the number of permutations of n with EXACTLY two occurence of the pattern 123].
Added Dec. 12, 2016: See the students' nice solutions.
contains procedures:
Big(i-1) n Small(n-i)
Added March 21, 2017: Here is the joint paper the whole class wrote as a final project.
Every team sent their part of the paper, and their part of the Maple code to the coordinating author, Richard Voepel, who comined them into a coherent paper, and a coherent website.
It is also available from arxiv.org, so it it for ever part of the eternal corpus of mathematical knowledge, and the students whose Erdos number was previously either infinite, or larger than three, has now Erdos number three.
Added Jan. 8, 2017: Read the students' evaluations.