Math 640: EXPERIMENTAL MATHEMATICS (Algorithmic Enumerative and Algebraic Combinatorics) (Spring 2026)

http://sites.math.rutgers.edu/~zeilberg/math640_26.html

Last Update: March 9, 2026

Description

Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in that direction. In addition to learning the philosophy and methodology of this budding field, students will become computer-algebra wizards, and that should be very helpful in whatever mathematical specialty they are doing (or will do) research in.

We will first learn Maple, and how to program with it. This semester we will learn, from an experimental mathematics point of view, algorithmic enumerative and algebraic combinatorics, focusing on elegant bijective proofs. The final projects may lead to published papers. People who already took previous editions of this class are welcome to take it again, since except for the basics, there is very little overlap with previous years.

This class is suitable for graduate students in other departments, and the software development skills learned will be useful for doing any quantitative research. Very smart advanced undergraduates are also welcome.

Important Papers

Important Program

Optional (but Highly recommended) Getting Started Homework

Teach yourself the basics of Maple by reading Frank Garvan's golden-oldie part 1, part 2
Note: a few commands are no longer valid in today's Maple. The most important one is that " has been replaced by %.

For more details, see this 2002 masterpiece.

How to submit homework

Programs done on Thurs., Jan. 22, 2026

C1.txt , Contains procedures

Homework for Thurs., Jan. 22, 2026, class (due Sunday Jan. 24, 8:00pm)

Please email ShaloshBEkhad at gmail dot com an email with

Subject: HomeWork#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.

  1. [People who took this class before, or already know Maple, are excempt from this] 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 .

  2. [For novices] Go over today's Maple code and try to understand it.

  3. [For everyone!] Do a preliminary reading of Dr. Z.'s summary of Enumeartive and Algebraic combinatorics

  4. [Optional (and very challenging) for novices, mandatory for experts] Write a procedure

    NuFP(pi)

    that inputs a permutation pi of {1,...,n}, where n:=nops(pi) and outputs the number of places i from 1 to n, where pi[i]=i. For example
    NuFP([2,1,3,5,4])=1

  5. Write a procedure

    WtE(n,x)

    that inputs a non-negative integer and a variable x and outputs the sum of xNuFP(pi) summed over all permutations of length n.

    For which k , 0 ≤ k ≤ 5, are the following sequences in the OEIS, and what are their A number? (if thye exist)

    [seq(coeff(WtE(i,x),x,k),i=0..8)]

  6. [Optional Challenge, $5 dollars to be divided] Fix procedure MyPermL(n) so that it gives the same output (in that order) as Maple's built-in permute(n)

    Added Jan. 25, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

    Programs done Monday, Jan. 26, 2026

    Due to the snow storm, today's class was remote. Here is the recording

    We did the following Maple code:

    C2.txt , Contains procedures

    Homework for Monday, Jan. 26, 2026, class (due Sunday Feb. 1, 8:00pm)

    Please email ShaloshBEkhad at gmail dot com an email with

    Subject: HomeWork#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.

    1. [People who took this class before, or already know Maple, are excempt from this] 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 .

    2. Go over today's Maple code and try to understand it.

    3. [Optional but a recommended challenge for novices, mandatory for experts]

      Part I: Write a procedure

      Bij(pi)

      that inputs a permutation pi of {1,...n}, where n:=nops(pi), and outputs the pair [i,pi'], where i is the location of n, and pi' is the permutation of {1, ..., n-1} obtained from deleting n. For example

      Bij([3,1,4,6,2,5])=[4,[3,1,4,2,5]]

      Part II: Write a procedure

      InvBij(Pair)

      that inputs a pair Pair of the form [i,pi'], such that pi' is a permutation of {1,...,n-1} where n:=nops(pi')+1, and i is an integer between 1 and n inclusive, and outputs the permutation pi of {1, ...,n} obtained from pi' by inserting n right befire the i-th place (and if i=n, at the end. For example

      invBij([4,[3,1,4,2,5]]=[3,1,4,6,2,5]

    4. [For everyone] Convince yourself that Bij and InvBij are inverses of each other and hence the sets permute(n) and {1, ...,n} x permute(n-1) are in bijection and hence we have a rigorous proof that if a(n) is the number of permutations of {1, ...,n} we have the recurrence

      a(n)=n*a(n-1)

    5. [Optional for Novices, but try your best]

      Part I: Using procedure, Contain3(pi,sig), write a procedure

      Contain3S(pi,S) that inputs a set of patterns, all of length 3 and outputs true if and only of pi contains at least one of the patterns in S. Note that for any pattern sig of length 3, Contain3S(pi,{sig}) is the same as Contain3(pi,sig). For example

      Contain3([1,2,4,3],{[1,2,3],[3,2,1]}) is true but Contain3([4,3,2,1],{[1,2,3],[2,3,1]}) is false.

      Part II: Using Contain3S(pi,S) write a procedure

      AvoidPer(n,S): inputs a pos. integer n and a set of patterns of length 3, S, outputs the subset of permute(n) that avoids all the patterns in S.

      Part III: Conjecture an explicit formula for the number of permutations of {1, ...,n} avoding both the patterns 123 and 132, in other words, nops(AvoidPer(n,{[1,2,3],[1,3,2]})), by entering

      seq(AvoidPer(n,{[1,2,3],[1,3,2]}),n=1..8)

    6. [Optional challenge, for everyone, $10 to be divided, please no peeking] Prove that conjecture.
      [Solved by Aurora Hiveley (see here), Austin DeCicco, (see here), Jike Liu, (see here), ]

      Added Feb. 1, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

      Programs done Thurs, Jan. 29, 2026

      Due to the arctic weather, today's class was again remote. recording
      [Please ignore the last 30 minutes, I forgot to press "stop recording", and I am too lazy to edit it out]

      We did the following Maple code:

      C3.txt , Contains procedures

      • FP(pi): The number of fixed points of per. pi

      • Der(n): The set of derangements (i.e. permutations w/o fixed points) of {1, ..., n}

      • d(n): the number of derangements of n elements using the linear (inhomog.) recurrence

        d(n)=n*d(n-1)+(-1)^n

      • ExtractCycle(pi,i): The cycle corresponding to the member i of the permutation pi. For example ExtractCycle([2,1,4,3],1)=[1,2]

      • CycDec(pi): The full cyclic decomposition of pi. For example CycDec([2,1,4,3]); should give {[1,2],[3,4]})

      Homework for Thurs., Jan. 29, 2026, class (due Sunday Feb. 1, 8:00pm)

      Please email ShaloshBEkhad@gmail.com an email with

      Subject: HomeWork#3 (or Homework #2#3 if you use one email message)

      and an attachment (along with possibly hw2)

      hw3FirstNameLastName.txt

      and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

      1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, in pages 61-90 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
        Only record a small sample in hw3YourName.txt .

      2. Read, understand, and try out today's Maple code.

      3. Write a procedure

        Mul(pi,sig)

        that inputs permutations pi, sig of the same length (n) and outputs the product (i.e. composition in the sense of functions) defined by sig[pi[i]], i=1..n. For exmpla

        Mul([3,1,4,2],[4,1,2,3])=[2,4,3,1]

      4. [corrected Jan. 31, 2026, thanks to Carolone Cote]
        Using Mul, write a procedure

        Pow(pi,k)

        that compute pik i.e. pi multiplied by itself k times.

        Then write a procedure, Idemp(n,k) that that finds the set of permutations of {1, ...,n} such that pik is the identity permutation [1,2,...,n]

        Idemp(3,2)={[1,2,3],[1,3,2],[3,2,1],[2,1,3]}

      5. Is the sequence [seq(Idemp(i,2),i=1..8)] in the OEIS? If yes, what is its A number?

        [Idemp is short for "idempotent"]

      6. [Optional Human challenge, 5 dollars to be divided, no peeking] Prove that the number of derangements of {1, ..., n} satisfies the second-order recurrence

        d(n)=(n-1)*d(n-1)+(n-1)*d(n-2)

        [Hint, if you look at the permutation in cycle decomposition, a derangement has no 1-cycles]. Look where n can reside.
        [Solved by Aurora Hiveley (see here), Austin DeCicco, (see here), Jike Liu, (see here), ]

      7. Prove that the above second order recurrence implies the first order (inhomog.) recurrence

        d(n)=n*d(n-1)+(-1)^n

        Hint: It is easier to prove that the latter recurrence implies the former, then use the fact that d(n)-n*d(n-1)=(-1)^n implies

        d(n)-n*d(n-1)=(-1)*(d(n-1)-(n-1)*d(n-2)

      8. [Optional challenge, 2 dollar] prove that d(n)=n*d(n-1)+(-1)^n impies that the limit of d(n)/n! as n goes to infinity is 1/e.
        [Solved by Aurora Hiveley (see here), Austin DeCicco, (see here), Jike Liu, (see here), ]

        Added Feb. 1, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

        Programs done Monday, Feb. 2, 2026

        We did the following Maple code:

        C4.txt , containing procedures:

        • IncSeqs1(n,k,a): The set of increasing sequences of length k of integers that ends with a

        • IncSeqs(n,k): The set of increasing sequences of length k using the integers from 1 to n. For example, IncSeqs(4,2) is {[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]}

        • Contain1(pi,sig): does the permutation pi contain the pattern sig?

        • Contain(pi,S): does the permutation pi contain at least one of the patterns in S?

        • AvoidPer(n,S): the set of permutations of length n that avoid the patterns in the set of patterns S

        • a(n): A sequence that tricks to believe that it is always integers, but starting at n=17 is not

        • b(n): A sequence that does not trick you and was proved to always give integers.

        Homework for Monday Feb. 2, 2026, class (due Sunday Feb. 8, 8:00pm)

        Please email ShaloshBEkhad@gmail.com an email with

        Subject: HomeWork#4 (or Homework #4#5 if you use one email message)

        and an attachment (along with possibly hw5)

        hw4FirstNameLastName.txt

        and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

        1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, in pages 91-end of Frank Garvan's awesome Maple booklet ( part 1, part 2)
          Only record a small sample in hw3YourName.txt .

        2. Read, understand, and try out today's Maple code.

        3. Type the following 10 times, after reading C4.txt ,

          S:={seq(randperm(3),i=1..3)}; [seq(nops(AvoidPer(n,S)),n=1..8)];

          how many of then are in the OEIS?

          For those that are not in the OEIS, can you conjecture a formula?

        4. Type the following 10 times, after reading C4.txt , S:={seq(randperm(3),i=1..2), seq(randperm(4),i=1..4)}; [seq(nops(AvoidPer(n,S)),n=1..7)];

          how many of then are in the OEIS?

          For those that are not in the OEIS, can you conjecture a formula?

        5. [Optional challenge, OK to cheat, 5 dollars]. Find out the name of the sequence b(n) in C4.txt, and search the internet for a proof that, unlike a(n), b(n) is always an integer. Write it in your own words, and be able to present it to the class.

        6. [Challenge, I have no clue] Why are a(n) integers for n up n=16

        7. [Optional Challenge, 5 dollars]. By glancing at AvoidPer(n,{[1,3,2]}) for small n, and looking at the location of n and what comes before and what comes after, prove that if a(n) is the number of permutations of length n avoiding the pattern 132, it satisfies the recurrence the non-linear recurrence

          a(n)=Sum(a(k)*a(n-1-k),k=0..n-1)

          Use this recurrence (with option remember) to crank-out many terms, and conjecture an explicit formula.

          Added Feb. 8, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

          Programs done Thurs., Feb. 5, 2026

          We did the following Maple code:

          C5.txt , Contains the following procedures (in addition to those of C3.txt, see above)

          • maj(pi): The major index : The sum of the places where pi[i]>pi[i+1]. For example if pi=[2,1,5,2,3], maj(pi)=1+3 (since pi[1]>pi[2] amd pi[3]>pi[4])

          • inv(pi): The number of inversions of the permutation pi, i.e. number of pairs i, j, with 1<=ipi[j] For example inv([1,2,3])=0, inv([3,2,1])=3

          • LtoR(pi): The list places that are larger than anything to the left, For example LtoR([2,1,4,3])=[1,3]. Note that 1 is always there.

          • WtE(S,f,x): The weight-enumerator of the set S accodring to the weight s->x^f(s), where f is a function on S.

          Homework for Thurs. Feb. 5, 2026, class (due Sunday Feb. 8, 8:00pm)

          Please email ShaloshBEkhad@gmail.com an email with

          Subject: HomeWork#5 (or Homework #4#5 if you use one email message)

          and an attachment (along with possibly hw4)

          hw5FirstNameLastName.txt

          and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

          1. Read, understand, and experiment with today's Maple code.

          2. Conjecture an expression for the following quantity, once you have read C5.txt:

            factor(WtE(powerset(n),S->nops(S),x));

            by doing it for n=1,n=2,n=3,n=4, .... Note that this is the weight-enumerator of the set of substes of {1, ...,n} according to the weight S-> xNumberOfElementsOfS

            Can you prove it?

          3. Write a procedure

            NumPat3(pi,sig)

            that inputs a permutation pi of any length and a permutation sig of length 3 (if it is not the procedure should return FAIL) and by using redu (of C4.txt), a variable co that starts as 0, and a triple do-loop that adds 1 to co each time it finds a triple that reduces to sig, and outputs the number of occurrences of the pattern sig in pi. For example

            NumPat3([2,1,3,4],[1,2,3]);

            should output 2, since [pi[1],pi[3],pi[4]]=[2,3,4] and [pi[2],pi[3],pi[4]]=[1,3,4] reduce to 123, and none of the other triplets do.

          4. Define

            L:=[seq(WtE(permute(n),pi->NumPat3(pi,[1,2,3]),x),n=1..7)];

            (if you have patience, try to do instead L:=[seq(WtE(permute(n),pi->NumPat3(pi,[1,2,3]),x),n=1..8)];) For Which j=0,1,2,3,... are the following sequences are in the OEIS? What are they A numbers? (if they exist)

            [seq(coeff(L[i],x,j),i=1..nops(L))];

          5. Repeat the above problem with the other five patterns of length 3, i.e. by replacing [1,2,3] by each of the following {[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}

          6. [Optional challenge (5 dollars, no peeking)]

            Prove that for every positive integer n,

            WtE(permute(n),inv,x)=(1)(1+x)*(1+x+x^2)*...*(1+x+...+x^(n-1))

            [Hint: Construct the permutations of length n from those of length n-1 and inserting n in every-which-way, and depending on the location see how it increases the number of inversions)

          7. Optional Challenge (5 dollars, no peeking). Prove that for every positive inteter

            factor(WtE(permute(n),pi->nops(CycDec(pi)),x))=x(x+1)(x+2)...(x+n-1)

            [Hint: Construct the permutations of length n from those of length n-1, given in cycle structure. Where can you stick the n w/o creating a new cycle?, adding the singleton cycle (n) increases the number by 1]

          8. Optional Challenge (5 dollars, no peeking). Prove that for every positive inteter

            factor(WtE(permute(n),pi->nops(LtoR(pi)),x))=x(x+1)(x+2)...(x+n-1)

            [Hint: Construct the permutations of length n from those of length n-1, by adding 1 to all the entries, and sticking 1 in every-which place. In most places it does not change the number of Left-To-Right maxima, but in one place it does. Which one?

          9. [Optional challenge, 25 dollars w/o "peeking", 10 dollars, by looking it up, understanding the proof, and being able to present it to the class]

            Prove, that for every pos. integer n,

            WtE(permute(n),maj,x)=(1)(1+x)*(1+x+x^2)*...*(1+x+...+x^(n-1))

          Added Feb. 8, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

          Programs done Monday, Feb. 9, 2026

          We did the following Maple code:

          C6.txt , Contains the following procedures

          • Games(S,a,b): Inputs a finite set of POSITIVE integers and non-negative integers a and b. Outputs the SET of game histories, where Home team scored a points and the Visiting team scored b points where the "atomic" scoring events belong to S. In Soccer: S={1}; Basketball ={1,2,3}; American football={3,6,7,8} Games:=proc(S,a,b) local G,s,G1,g1: option remember:

          • NuGames(S,a,b): Inputs a finite set of POSITIVE integers and non-negative integers a and b. Outputs the NUMBER of game histories, where Home team scored a points and the Visiting team scored b points where the "atomic" scoring events belong to S. In Soccer: S={1}; Basketball ={1,2,3}; American football={3,6,7,8}

          • CFC(C): inputs a list of numbers coming from a cycle and outputs the equivalent cycle where the largest entry is the first. For example, CFC([4,2,6,1,5])=[6,1,5,4,2].

          • added after class: CycToPer(C): The reverse of CycDec(pi). Given a permutation in cycle structure, outputs it in 1-line notation. For example
            CycToPer({[1,2],[3,4]})=[2,1,4,3]

          Homework for Monday Feb. 9, 2026, class (due Sunday Feb. 15, 8:00pm)

          Please email ShaloshBEkhad@gmail.com an email with

          Subject: HomeWork#6 (or Homework #6#7 if you use one email message)

          and an attachment (along with possibly hw7)

          hw6FirstNameLastName.txt

          1. Read and understand today's Maple code, including procedure CycToPer(C), added after class. Test that CycToPer(CycDec(pi))=pi for every permutation of length 6.

          2. Assuming that team I (the home team) eventually won, so the final score was [a,b] with with a ≥ b ≥ 0, define a boring game if, throughout the history game team II was never ahead (it is OK if it tied). For example (in basketball) the game history
            [[0,0],[2,0],[2,2],[3,2]] is boring, but
            [[0,0],[2,0],[2,2],[3,2],[3,4],[6,4]] is not boring.

            Write proceduers

            BoringGames(S,a,b) and NuBoringGames(S,a,b) that output the sets, respectively, the number boring games.

            [Hint: in addition to the condition that a and b are never negative you also need to tell Maple that BoringGames(S,a,b) is the empty set if a < b]

          3. Check whether the following sequences are in the OEIS, and if there are, give their A numbers.

            Soccer: [seq(NuBoringGames({1},i,i),i=1..20)]:

            Old-Time Basketball: [seq(NuBoringGames({1,2},i,i),i=1..20)]:

            Today's Basketball: [seq(NuBoringGames({1,2,3},i,i),i=1..20)]:

            American football: [seq(NuBoringGames({3,6,7,8},i,i),i=1..20)]:

          4. [ A ltile bit challenging for novices, but try your best]

            The famous Foata bijection, Φ inputs a permutation of {1, ...,n} in one-line notation, and outputs another permutation in one-line notation, as follows.

            • Find the cycle decomposition, and convert each of the cycles to canonical form, using CFC.
            • Arrange these cycles in INCREASING order of their first element (which is their largest).
            • Remove the interior brakcets.
                For example if pi=[4,3,2,1], the cycle decomposition (in canonical form) is {[4,1],[3,2]} . Now make it into a list of lists with the first elements in increasing order [[3,2],[4,1]], and finally, remove the inside brackets and get
                Φ([4,3,2,1])=[3,2,4,1]

          Added Feb. 15, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

          Thursday, Feb. 12, 2026: Guest Lecture by Professor Wadim Zudilin in memory of his first PhD student, Jesus Guillera (1955-2026)

          One of the greatest experimental mathematicians of all time, Jesus Guillera, sadly died three days ago. His PhD advisor, Wadim Zudilin, kindly agreed to give a

          guest lecture

          Here are the slides.

          After class, the following Maple code was written:

          C7.txt , Contains the following procedures

          • RF(a,n): The rising factorial (aka Pochammer symbol) a(a+1)...(a+n-1). Note that RF(1,n)=n!

          • HowManyDigits(f,N) : Inputs a pre-coded procedure, f, for computing Pi via an infinite series, outputs the number of digits that agree with Pi if you truncate it after the term n=N. For example HowManyDigits(JG1,40); should return 123, meaning that if you truncate the series after 40 terms it would agree with Pi to 123 digits

          • JG1(N): Approximting Pi, using the first N terms in the Guillera formula in his homepage using Ramanujan-style, "dot,dot, dot" notation

            (calling the sum a, the output is sqrt(128/a), since the sum is for 128/Pi^2)

          • JG2(N): The first formula in page 6 of Jesus Guillera's thesis (calling the sum a, the output is 27/(4*a), since the sum is for (4/27)*Pi

          Homework for Thurs. Feb. 12, 2026, class (due Sunday Feb. 15, 8:00pm)

          Please email ShaloshBEkhad@gmail.com an email with

          Subject: HomeWork#7 (or Homework #6#7 if you use one email message)

          and an attachment (along with possibly hw6)

          hw7FirstNameLastName.txt

          1. Read, understand, and experiment with the procedures done after class in C7.txt , if you use the formula in Guillera's homepage, coded in JG1, how many terms (i.e. in what place do you need to truncate the series) to compute Pi to 100 decimal digits after the decimal point?

          2. Browse Jesus Guillera's thesis, his papers, and the formulas in Professor Zudilin's talk, pick five series that look promising, hard-code them (similar to JG2, using RF), call them JGyourInitialsX (X=1,2,3,4,5), (e.g. for Lucy Martinez, JGlm1(N), JGlm2(N), etc., and find the number of digits that agree with Pi if you use 101 terms in the series (i.e. you stop at n=100)

            [The person to get the greatest number of digits will get a prize of 5 dollars]

          Added Feb. 15, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

          Composite

          Programs done Monday, Feb. 16, 2026

          We did the following Maple code:

          C8.txt , Contains the following procedures

          • From previous classes (see above): LtoR(pi), ExtractCycle(pi,i), CycDec(pi)

          • xn(n): The solution of the recurrence xn(n)=(1+add(xn(i)^2,i=0..n-1))/n:

          • xnC(n): clever version of xn(n) only having to remember what happened yesterday

          • xnP(n,p): For a prime p, a fast way to compute xn(n) mod p for n

          • (By Austin DeCicco from hw6)
            Foata(pi): the Foata mapping that first converts the permutation pi into cycle decomposition, then makes every cycle into canocial form by putting the largest element on the top, then sorts them in increasing order of the first elements, and at the end removes the interiur brackets.

          Homework for Monday. Feb. 16, 2026, class (due Sunday Feb. 22, 8:00pm)

          Please email ShaloshBEkhad@gmail.com an email with

          Subject: HomeWork#8 (or Homework #8#9 if you use one email message)

          and an attachment (along with possibly hw9)

          hw8FirstNameLastName.txt

          1. Show that for all primes p less than 43, if you compute

            (xnP(p-1,p)+p-1)*xnP(p-1,p) mod p

            you get 0, not enabling you to deduce that it stops producing integers, but for p=43 it breaks down, concluding that xn(43) is NOT an integer (even though it is too big to compute directly)

          2. Read and understand procdure Foata(pi) done by Austin DeCicco (and possibly other students), and verify that for all permutations of size ≤ 7,

            nops(LtoR(Foata(pi))=nops(CycDec(pi))

          3. Convince yourself that the Foata bijection implies that for all integers n and k ≤ n, the number of permutations with k cycles equals the number of permutations with k Left-To-Right maxima

          4. [A little bit challenging]

            Write a procedure

            AntiFoata(pi)

            that is the inverse of Foata(pi)

            That that for every permutation pi of size ≤ 7

            AntiFoata(Foata(pi))=pi and Foata(AntiFoata(pi))=pi

          5. Write procedures

            xnk(n,k), xnkC(n,k), and xnkP(n,k,p) that give the first value (and those mod p) of the sequence defined by the recursion

            xnk(n,k)= (1+xnk(0,k)^k+...+xnk(n-1,k)^k)/n

            [Note that xnk(n,2) equals xn(n)]

            verify that for k=3, and k=4, the first 15 terms are integers.

          6. [Optional challenge, 5 dollars, no peeking, I know the answer]
            Find the smallest n such that xnk(n,3) is NOT an integer (similar to 43 for k=2)

            [Added Feb. 23, 2026: This was nicely solved by Austin DeCicco. See here. The answser is 89]

          7. [Optional challenge, 6 dollars, no peeking, I don't know the answer]
            Find the smallest n such that xnk(n,4) is NOT an integer

            [Added Feb. 23, 2026: This was nicely solved by Austin DeCicco. See here. The answser is 97. For more terms see OEIS sequence A288641 ]

          Added Feb. 22, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

          Programs done Thursday, Feb. 19, 2026

          We did the following Maple code:

          C9.txt , Contains the following procedures

          • RandL(n,k): A random list of subsets of {1, ...,n} of length k

          • PIEd(n,L): What the Principle of Inclusion-Exclusion (PIE) computes, done directly

          • IntL(L): The intersection of the sets in the list-of-sets L

          • PIE(n,L): Inputs a positive integer n, and a list of subsets of {1,...,n}, computes the number of elements in {1, ..., n} that do not belong to any of the sets in L. It uses the (exponetial-time in nops(L)) PIE formula

            |(Not A[1]) Interset (Not A[2]) Interset ... (not A[k])|= n-(|A[1]|+|A[2]|+ ... |A[k]|)+ (|A[1] Intersect A[2]|+ ...+ |A[k-1] Intersect A[k]| - (|A[1] Intersect A[2] Intersect A[3]|+ ....)+ .... +(-1)*|A[1] Intersect ... A[k]|

            (Note that this formula has 2k terms

          • PIEg(n,L,t): TGhe generalized PIE formula: the weight-enumerator of the members of the universal set according to the weight t^#NumberOfProperties

          • dn(n): The number of derangements of {1, ..., n} according to the formula derived using PIE

          • dnt(n,t): The weight-enumerator of permutations of {1, ..., n} according to the number of fixed points

          Homework for Thursday Feb. 19, 2026, class (due Sunday Feb. 22, 8:00pm)

          Please email ShaloshBEkhad@gmail.com an email with

          Subject: HomeWork#9 (or Homework #8#9 if you use one email message)

          and an attachment (along with possibly hw8)

          hw9FirstNameLastName.txt

          1. Write a procedure

            NumberOfProperties(n,L,i)

            that inputs a positive integer n, a list of subsets, L, of {1, ..., n}, and a member of {1, ...,n} and outputs the number of sets in L such that i belongs to them. For example

            NumberOfProperties(4,[{1,3},{2,4},{3,4}],1)=1, NumberOfProperties(4,[{1,3},{2,4},{3,4}],2)=1, NumberOfProperties(4,[{1,3},{2,4},{3,4}],3)=2, mberOfProperties(4,[{1,3},{2,4},{3,4}],4)=2

          2. Using the above, write a procedure

            PIEgD(n,L,t)

            that outputs the sum of tNmberOfProperties(n,L,i) over all i from 1 to n

          3. Test that PIEg(n,L,t)=PIEgD(n,L,t) by doing 5 times

            L:=RanddL(1000,4): evalb(PIEg(n,L,t)=PIEgD(n,L,t));

          4. [Optional Challenge, 5 dollars] Implement the bijective proof in this nice article

            [Added Feb. 22, 2026: This was nicely solved by Jike Liu. See here ]

          Added Feb. 22, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

          Programs done Monday Feb. 23, 2026

          Today's class again was remote (due to the snow storm). Here is the recording.

          We did the following Maple code:

          C10.txt , Contains the following procedures

          Procedures from From hw8:

          • xnk(n,k): The solution of the recurrence xn(n)=(1+add(xn(i)^2,i=0..n-1))/n:

          • xnkC(n,k): clever version of xn(n) only having to remember what happened yesterday

          • xnkP(n,k,p): For a prime p, a fast way to compute xnk(n,k) mod p for n
          • AD(k): Inspired by Austin DeCicco: the first term of the sequence xnk(n,K) that is NOT an integer

          New procedures:

          • Comps(n): The set of compositions of n. For example, Comps(3) is {[3],[1,2],[2,1],[1,1,1]}.

          • CompsG(n,A): The set of compositions of n whose entries are from the set A

          • ParS(n): The set of partitions of n, done stupidly, by first finding Comps(n) and then sorting the members

          • Park(n,k): The set of partitions of n into exactly k parts, done cleverly

          • Par(n): The set of partitions of n, the clever way.

          Homework for Monday Feb. 23, 2026, class (due Sunday March 1, 8:00pm)

          Please email ShaloshBEkhad@gmail.com an email with

          Subject: HomeWork#10 (or Homework #10#11 if you use one email message)

          and an attachment (along with possibly hw11)

          hw10FirstNameLastName.txt

          1. Using procedure

            CompsG(n,A)

            Write a procedure

            CompsMod(n,a,S)

            that inputs a positive integer n, a positive integer a and a subset S of {0,1,..., a-1} and outputs the set of compositions of n whose entries mod a belong to S. For example

            CompsMod(n,1,{0}) is the same as Comps(n), and Comps(n,2,{1}) gives the set of compositions into odd parts.

            [Hint: the set of integers of the form s (mod a) is {seq(a*i+s,i=0..infinity)} but you can safely replace it by {s

            [seq( nops(CompsMod(n,2,{1})),n=1..10)];

            [seq( nops(CompsMod(n,3,{1})),n=1..10)];

            [seq( nops(CompsMod(n,5,{1,4})),n=1..10)];

          2. A partition is odd if all its members are odd. Write a procedure

            OddParStupid(n)

            that looks at all the members of Par(n) and selects those that only have odd parts.

          3. A partition is distinct if all its members are distinct. Write a procedure

            DistinctParStupid(n)

            that looks at all the members of Par(n) and selects those that have distinct parts.

          4. Verify that for n up to 15, nops(DistinctParStupid(n))=nops(OddParStupid(n))

          5. [ Optional Challenge (no peeking), 10 dollars] Prove that, for every positive integer n, the number of partitions of n into odd parts equals the number of partitions of n into distinct parts.

            Added March 2, 2026: This was solved by Austin DeCicco and Jike Liu

          6. [Optional Challenge, 5 dollars (modified 2/26/26)]
            Give a bijective proof that the number of compositions of n equals 2n-1 by constructing a bijection between the set of compositions of n and 0-1 vectors of length n that start with 1. You should implement it in Maple, by coding both directions.

            Added March 2, 2026: This was solved by Austin DeCicco and Jike Liu and Lucy Martinez

          7. [Optional Challenge, 6 dollars (modified 2/26/26)]
            Give a bijective proof that the number of compositions of n into odd parts equals fionacci(n), by constructing a bijection between the set of compositions of n into odd parts and compositions into parts from {1,2} that start with 1. You should implement it in Maple, by coding both directions.

          Added March 1, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

          Programs done Thurs. Feb. 26, 2026

          We did the following Maple code:

          C11.txt ,
          [NOTE: The previous version had a serious error. Thanks to Lucy Martinez (who won 5 dollars) for spotting it. It is now corrected].
          Contains the following procedures

          • CP(A,B): the Cartesian product of A and B, where the nembers of A and B are either integers or lists of integers.

          • WtE(A,x): The sum of x^a in A (if A is a set if integers ) or the sum of x^(sum of entries of a) if A is a set of lists

          • PowA(A,n): The Cartesian product of A with itself n times

          • GenCompsGF(a,b,A,B,x): that inputs
            • positive integers a and b
            • A, subset of {1, ...,a} (NOTE: NOT of {0,1, ...,a-1}, since 0 is not allowed to be part of a composition
            • B, a subset of {0,...,b-1}
            • a variable x
            and outputs

            The rational function whose Taylor series is such that the coeff. of x^n is the EXACT number of compositions whose parts all obey

            • i mod belongs to A
            • number of parts, k, obeys
              k mod b belongs to B

            Homework for Thurs. Feb. 26, 2026, class (due Sunday March 1, 8:00pm)

            Please email ShaloshBEkhad@gmail.com an email with

            Subject: HomeWork#11 (or Homework #10#11 if you use one email message)

            and an attachment (along with possibly hw10)

            hw11FirstNameLastName.txt

            1. Using procedure GenCompsGF(a,b,A,B,x), write a procedure

              CountNuCompsClever(a,b,A,B,N)

              that inputs the positive integers a and b and a subset A of {1, ..., a} and a subset B of {0, ,b-1} and outputs the first N terms of the sequence enumerating compositions all whose parts have the property that i mod a belongs to A and the number of parts mod b belongs to B. In other words, a composition L qualifies if

              member(nops(L) mod b,B) is true

              and {seq(L[i] mod a, i=1..nops(L))} minus A={}

              Hint: To get the first N+1 coefficients, starting at n=0 of the Taylor coefficients around x=0 you use the Maple command

              [seq(coeff( taylor(f,x=0,N+3),x,i),i=0..N)]:

            2. Write a procedure

              CountNuCompsStupid(a,b,A,B,N)

              That does the same thing but as follows:

              First write a procedure CountNuCompsStupid1(a,b,A,B,n), that finds the number of compositions of n that obeys the stated condition, but first using Comps(n) (there are 2n-1 of them, so you can go to n=16 easily), and for each of them, L, checks whether nops(L) mod b belongs to B, and all the members of L mod a belongs to A and collects them into a set and does nops.

              Check that

              CountNuCompsClever(a,b,A,B,15)= CountNuCompsStupid(a,b,A,B,15) for

              a=3, b=4, A={1,2}, B={0,3} ;

              a=2, b=3, A={1}, B={2}

            3. [Optional challenge, 1 dollar for each occurrence in the OEIS, 2 dollars if the description there is not about compositions. Limit: 10 dollars]

              Find as many as possible choices of (a,b,A,B) such that

              CountNuCompsClever(a,b,A,B,20)

              is in the OEIS

              Added March 2, 2026: This was solved by Austin DeCicco

            4. [Optional challenge, 3 dollars] Using CP (that also applies to lists) and WtE, find ways to put pips (possibly with repeitions) into a usual fair die such that the probabilty distribution of their sum is the same as that of the standard die (i.e. prob. of getting a sum of 2 is 1/36, a sum of 3, 2/36, ... a sum of 7 is 6/36, ..., a sum of 12 is 1/36.

              Added March 2, 2026: This was solved by Aurora Hiveley and Jike Liu

            Added March 1, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

            Programs done Monday March 2, 2026

            We did the following Maple code:

            C12.txt ,

            • Park(n,k): The set of partitions of n into exactly k parts

            • Par(n): The set of partitions of n, the clever way.

            • A41s(N): OEIS sequence A41 done stupidly

            • A41ok(N): OEIS sequence A41 done much more efficiently, using Euler's generating function

            • EulerM(N,q): The truncation to q^N of Prod(1-q^k, k=1..infinity)

            • ConjP(N): The conjectured powers of the polynomial in EulerM

            • EPTtest(N): testing Euler's pentagonal numbers (3*j^2+j)/2

            Homework for Monday, March 2, 2026, class (due Sunday March 8, 8:00pm)

            Please email ShaloshBEkhad@gmail.com an email with

            Subject: HomeWork#12 (or Homework #12#13 if you use one email message)

            and an attachment (along with possibly hw13)

            hw12FirstNameLastName.txt

            1. Write a procedure

              A41c(N)

              that inputs and outputs the same things as A41s(N) and AS41ok(N), but using The recurrence

              p(n)= Sum((-1)^(j-1)*p(n-(3*j^2-j)/2,j=1..infinity)+ Sum((-1)^(j-1)*p(n-(3*j^2+j)/2,j=1..infinity)

              with the convention that p(n)=0 if n is negative (so the above sums are only for j such that (3*j^2-j)/2 and (3*j^2+j)/2, respectively, are <=n
              [Hint: first write A41c1(n) to compute p(n), and use option remember)

              How does time(A41c(1000)) compare to time(A41ok(1000))?

            2. Read and understand the proof of the above recurrence (due to Euler, based on the Euler Pentagonal Theorem) given in
              Bressoud-Zeilberger gem
              Programs it in Maple

            3. Write procedures OddToDis(p) and DisToOdd(n) that implement Sylvester's bijection described in this gem

            4. [Optional challenge, 5 dollars, for each pair] Using A41c(N), try to find pairs of integers (A,B) such that for all n

              p(A*n+B) mod A=0

              How far can you verify it?

              [Added March 9, 2026: This was fully solved by Austin DeCicco and JikeLiu, and partially by Aurora Hiveley.]

            Added March 8, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

            Programs done on Thursday March 5, 2026

            We did the following Maple code:

            C13.txt   (Here is Lucy's version (with notes)).

            • ParN(n,k): The set of integer partitions of n whose largest part is k (done stupidly)

            • SYT(L): The SET of Standard Young tableaux of shape L

            • PSYT(Y): prints the Standard Young tableau Y

            Homework for Thurs., March 5, 2026, class (due Sunday March 8, 8:00pm)

            Please email ShaloshBEkhad@gmail.com an email with

            Subject: HomeWork#13 (or Homework #12#13 if you use one email message)

            and an attachment (along with possibly hw12)

            hw13FirstNameLastName.txt

            1. A partition is d-super-distinct if the difference between two consecituve parts is >=d. The usual distinct partitions are 1-distinct.

              Write a procedure

              IsSuperDistinct(L)

              that inputs a partition (a member of Par(n), written in the usual way as weakly decreasing list of integers) and outputs true iff for all i, between 1 and nops(L)-1, L[i]-L[i+1]>=d

              Using this, write a procedure

              SuperDistinctPars(n,d)

              That outputs the subset of Par(n) consisting of d-super-distinct partitions

            2. Write a procedure

              ParMod(n,a,A)

              that inputs a positive integer n, another positive integer a, and a subset, A, of {0,1, .., a-1} and outputs the subset of Par(n) consisting of those partitions all whose entries mod a belong to A.

            3. What OEIS seqeunce is {nops(SuperDistinct(n,2)) }?

              What OEIS seqeunce is {nops(ParMod(n,5,{1,4})) }?

            4. Eventually nops(SYT(L)) will be impractical, since the sets SYT(L) gets very big. Adapt procedure SYT(L) to write a procedure

              NuSYT(L)

              that inputs an integer partition L, and outputs the NUMBER of Standard Young Tableaux of shape L. For example

              NuSYT([2,2]); should output 2, and NuSYT([3,3,3]); should output 42. (REMEMBER TO HAVE option rememeber)

            5. [Optional challenge, 10 dollars to be divided, NO PEEKING]

              Conjecture an explicit expression for NuSYT([a,b]) (alias nops(SYT([a,b])) for all a ≥ b ≥ 0

              [Added March 9, 2026: This was solved by JikeLiu]

            6. [Optional challenge, 15 dollars to be divided, NO PEEKING]

              Conjecture an explicit expression for NuSYT([a,b,c]) (alias nops(SYT([a,b,c])) for all a ≥ b ≥ c ≥ 0

              [Added March 9, 2026: This was solved by JikeLiu]

            Added March 8, 2026: The nice homework solutions of students that kindly agreed to share their homework solutuions can be found in this directory

            Programs done Monday March 9, 2026

            We did the following Maple code: C14.txt

            • RS11(a,i): inputs an INCREASING list of positive integers, a, and another positive integer i outputs a pair a1,j, where (usually a1 is of the same length as a) and i is put where it belongs and j is the entry that it bumped, unless i is larger than all the members of a (i.e. larger than a[-1]) then a1 is [op(a),i], and j is 0

            • NuSYTpairs(n): The nummber of elements in SYTpairs(n)

            • SYTpairs(n): The set of pairs of standard Young tableaux with n boxes of the same shape

            • NuSYT(L): The Number of Standard Young tableaux of shape L

            Reading Homework for Monday March 9, 2026, class (due Thursday, March 12)

            1. Read and understand the Robinson-Schensted correspondence
            Dr. Z.'s teaching page