<jupyter_start><jupyter_text>Lecture 10: Computations in Discrete Mathematics Please note: This lecture will be recorded and made available for viewing online. If you do not wish to be recorded, please adjust your camera settings accordingly.   Reminders/Announcements:- Assignment 3 is due Thursday at 8pm- Grades for Quiz 1, Assignments 1 & 2, and Participation checks for Lectures 4-8 will be available to you by Friday (which is some sort of drop deadline)- This lecture has participation checks again.- Small typo on Assignment 3  Participation UpdateCoCalc allows me to export your "file use times." It gives me a JSON file with entries like this (this is anonymized):![](usetimes.png)It should look familiar! It's a dictionary of dictionaries! The edit times take timestamps on when the file was edited (the unit here is "milliseconds since the epoch"). A Python script then scrapes this file to make sure the files were interacted with.If you missed a few points, don't worry! 5 Participation scores will be dropped for each student.  Combinatorics and The Online Encyclopedia of Integer Sequences (OEIS)Combinatorics is the art of *counting*. - How many ways can you pick k objects out of a set of n objects (the *binomial coefficients*)- How many ways can you order a list of n distinct objects (*the factorial*)- How many ways can you "partition" a group of n people (*the Bell numbers*)- ...Often a general answer is not easy to come by. A *very very very useful* resource is the OEIS: https://oeis.org/ . It is a huge database of integer sequences, together with the things that they count.Sample of how your research project might go:- Step 1: Enumerate the first few cases of your counting problem by hand (or better, with Sage)- Step 2: Plug in your results into OEIS to make a conjecture regarding the general answer- Step 3: Prove your conjecture using insights from OEISExample: For a positive integer $n$, define $[n] = \{1,2,\dots,n\}$. How many subsets of $[n]$ have no *consecutive elements* in them? I.e. how many subsets $S\subset[n]$ such that $\{i,i+1\}\not\subset S$ for all $i$.<jupyter_code>def count(n):
    tally = 0
    subsets = Subsets(n)
    for subset in subsets:
        if any([(i in subset and i+1 in subset) for i in range(1,n+1)]):
            pass
        else:
            tally+=1
    return(tally)
for i in range(0,10):
    print(count(i))
oeis([1,2,3,5,8,13,21,34,55,89])
entry = oeis('A000045')
print(entry.name())
#print(entry.comments())<jupyter_output><empty_output><jupyter_text>Theorem: Let $S_n$ be the number of subsets of $[n]$ with no consecutive elements. Then $S_n$ is a Fibonacci number.Proof: Let $S$ be a subset of $[n]$. If $n$ is not in $S$, then in fact $S$ is a subset of $[n-1]$ with no consecutive elements. If $n$ is in $S$, then $S\setminus\{n\}$ is a subset of $[n-2]$ with no consecutive elements. This establishes a recursion $$S_n = S_{n-1}+S_{n-2}$$for $n\geq 2$. The initial conditions $S_0 = 1$, $S_1=2$ show that we have essentially a "reindexed" Fibonacci sequence.<jupyter_code>S = Subsets(3)
S
for subset in S:
    print(subset, len(subset))<jupyter_output><empty_output><jupyter_text>***** Participation Check ***************************Write a function `evenMinusOdd` which takes a positive integer $n$ as input and returns the difference between the number of even element subsets of $[n]$ and the number of odd element subsets of $[n]$,$$\ \{S:S\subset [n], |S| \text{ is even }\}-\ \{S:S\subset [n], |S| \text{ is odd }\}.$$Make a conjecture for what numbers count this sequence by running your function on $n=1,2,3,4,5,6,7$.<jupyter_code>def evenMinusOdd(n):
    #Your code here



#your code here<jupyter_output><empty_output><jupyter_text>********************************************************* Sage also has nice set constructors, so you can easily play poker with all of your friends:<jupyter_code>suits = ['Diamonds','Clubs','Hearts','Spades']
values = ['Ace','King','Queen','Jack']+[i for i in range(10,1,-1)]
deckOfCards = list(cartesian_product([suits,values]))
deckOfCards[0:13]
shuffle(deckOfCards)
deckOfCards[0:5]
possibleHands = Subsets(deckOfCards, 5)
len(possibleHands)<jupyter_output><empty_output><jupyter_text>Binomial CoefficientsThe binomial coefficient $\binom{n}{k}$ counts the number of ways of choosing a $k$ element subset from an $n$ element set. You may have seen the formula $$\binom{n}{k} = \frac{n!}{k!(n-k)!},$$or the *Binomial Theorem* $$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k.$$<jupyter_code>for i in range(6):
    print(binomial(5,i))
show(expand((1+x)^5))<jupyter_output><empty_output><jupyter_text>The binomial theorem actually gives a proof of your participation check;$$0 = 0^n = (1-1)^n = \sum_{k=0}^n\binom{n}{k}(-1)^k = \left(\sum_{k \text{ even }}\binom{n}{k}\right) - \left(\sum_{k \text{ odd }}\binom{n}{k}\right)$$There are many so called *binomial identities*. For example, the basic recurrence relation$$\binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1},$$or the so called *hockey stick identity*$$\sum_{k=r}^n\binom{k}{r} = \binom{n+1}{r+1}$$<jupyter_code>for n in range(10):
    print([binomial(n,k) for k in range(n+1)])<jupyter_output><empty_output><jupyter_text>You can get subsets of a given size in Sage by adding in a second parameter:<jupyter_code>L = ['Dog','Cat','Cow','Pig','Duck']
for subset in Subsets(L,3):
    print(subset)<jupyter_output><empty_output><jupyter_text>Permutations in SageA *permutation* of length $n$ is a reordering of the list $[1,2,\dots,n]$. We will usually write a permutation as $$\pi = \pi_1\pi_2\dots\pi_n$$Be careful! Combinatorial indexing is different than Python list indexing...<jupyter_code>P = Permutations(4)
for perm in P:
    print(perm)
print(P.cardinality())<jupyter_output><empty_output><jupyter_text>Permutations are counted by the *factorial* $n! = n\cdot(n-1)\dots 3\cdot 2\cdot 1.$<jupyter_code>for i in range(7):
    print(factorial(i))<jupyter_output><empty_output><jupyter_text>Often one applies *statistics* to permutations. For example: an index $k$ is a *descent* if $\pi_k > \pi_{k+1}$. Descents in permutations are closely related to the algebraic and geometric properties of the symmetric group.<jupyter_code>for perm in Permutations(3):
    print(perm,perm.descents())<jupyter_output><empty_output><jupyter_text>Here's a cool fact. Let's count the so called *Grassmanian permutations*, which are those who have a descent set contained in $\{k\}$. I.e. either they have no descents or they have a single descent at a specified index.<jupyter_code>def grass(n,k):
    tally = 0
    for p in Permutations(n):
        if p.descents()==[k] or not p.descents():
            tally+=1
    return(tally)
for n in range(9):
    print([grass(n,k) for k in range(n+1)])<jupyter_output><empty_output><jupyter_text>You can actually use this to give alternative proofs to many binomial identities!There is a *vast* literature on permutation statistics. You may have heard of cycle type, inversions, the Major index, left-right maxima, right-left maxima, peaks, pinnacles, excedances, ..... We will not go into more during this lecture, but may explore some in Assignment 4.   Set PartitionsA *set partition* of a set $S$ is a collection of nonempty blocks $\{B_1,\dots,B_k\}$ with $S = \cup B_i$ and $B_i\cap B_j = \emptyset$.Think of this as a way of assigning $n$ individuals into teams such that:- no team is empty- every player is on exactly one team<jupyter_code>Partitions = SetPartitions(3)
for partition in Partitions:
    print(partition)<jupyter_output><empty_output><jupyter_text>Set partitions are counted by the *Bell numbers*.<jupyter_code>for k in range(0,10):
    print(len(list(SetPartitions(k))))
oeis([1,1,2,5,15,52,203,877,4140,21147])<jupyter_output><empty_output><jupyter_text>You may have seen the Bell numbers from the power series expansion below:$$e^{e^{x}-1} = \sum_{n=0}^\infty \frac{B_n}{n!}x^n.$$<jupyter_code>f(x) = exp(exp(x)-1)
f
show(f.series(x,10))
bellNums = [1,1,2,5,15,52,203,877,4140,21147]
show([bellNums[i]/factorial(i) for i in range(10)])<jupyter_output><empty_output><jupyter_text>From this one can derive *Dobinski's formula*, which gives the explicit black magic$$B_n = \frac{1}{e}\sum_{k = 0}^\infty \frac{k^n}{k!}.$$<jupyter_code>var('k')
for i in range(1,10):
    print(bell_number(i))
    print(float(sum(k^i / factorial(k), k, 1, 15)/e))
    print('*****************')<jupyter_output><empty_output><jupyter_text>You *do not* have to memorize or really care about Dobinski's formula for this class, but it is way cool! Combinatorial identities like these give us the power to actually compute something like the 50th Bell number, without actually listing things out and keeping a running tally. It takes *forever* to simply count all of the set partitions of even something like $\{1,2,3,\dots,12\}$...<jupyter_code>tally = 0
S = SetPartitions(12)
for partition in S:
    tally+=1
print(tally)
bell_number(12,'dobinski')
bell_number(35,'dobinski')
bell_number(35,'dobinski').ndigits()<jupyter_output><empty_output><jupyter_text>The number we just computed is on the order of $10^{30}$...For comparison...the universe is ~$14$ billion years old, which as we all know is a hair over $10^{17}$ seconds...modern processors are operating at the level of gigahertz, which is about $10^9$ clock ticks a second...so if you parallelized a cluster of computers and had them running since the big bang, you *might* have finished the calculation by now. But $B_{35}$ is only the beginning...<jupyter_code>bell_number(5000,'dobinski')
bell_number(5000,'dobinski').ndigits()  
bell_number??<jupyter_output><empty_output><jupyter_text>You can gain many beautiful combinatorial identities by restricting the number of blocks in your set partition; this leads to the *Stirling numbers of the second kind*. We will not go into them too much here, other than the following: ***** Participation Check ***************************In the code cell below, use Sage to compute the number of set partitions of $\{1,2,\dots,n\}$ which have $n-1$ blocks. Do this for $n=2,3,\dots,8$. In the second code cell, feed the sequence into OEIS to make a conjecture about the number of such partitions in general.<jupyter_code>#Your code here
#Your OEIS call here<jupyter_output><empty_output><jupyter_text>*********************************************************  Integer PartitionsGiven a positive integer $n$, an *integer partition* of $n$ is a weakly decreasing sequence of positive integers $\lambda_1\geq \lambda_2\geq \dots \geq \lambda_k$ with $$n=\lambda_1+\dots+\lambda_k.$$Partitions are of great interest in both combinatorics *and* number theory *and* representation theory *and* probably other stuff!<jupyter_code>P = Partitions(5)
for p in P:
    print(p)
for i in range(10):
    print(len(list(Partitions(i))))
oeis([1,1,2,3,5,7,11,15,22,30])<jupyter_output><empty_output><jupyter_text>There is a wealth of topics we could study regarding integer partitions, and we don't have time to get to all of them. Here's an example of the "odd equals distinct" phenomenon. The `parts_in` tag restricts the size of the numbers you are allowed to use in the partition (remember this for your next homework!) and the `max_slope` parameter tells you how big $\lambda_{i+1}$ can be compared to $\lambda_i$:<jupyter_code>for partition in Partitions(9,parts_in=[1,3,5,7,9]):  #This gives partitions using only odd numbers
    print(partition)
for partition in Partitions(9,max_slope=-1):  #This gives partitions with no repetitions allowed (all the parts are distinct)
    print(partition)<jupyter_output><empty_output><jupyter_text>There is a beautiful proof of this dating back to Euler (because of course it was him), which we don't have time to get into. Finally, here is an example of the "restricted part size equals restricted number of parts" phenomenon:<jupyter_code>for partition in Partitions(7,max_part = 4):  #This gives partitions using parts <= 4
    print(partition)
for partition in Partitions(7,max_length = 4):  #This gives partitions using at most 4 parts
    print(partition)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup