2021

Sept. 5

  • How many anagrams of the word ERROR are there? (An anagram, is an arbitrary shuffle of the letters of a word, – an early tool to establish priority in scientific research; nowadays replaced by hashes).
    • If the letters are all different, there are \(n!=n\cdot(n-1)\cdot\ldots\cdot3\cdot2\cdot 1\) ways to shuffle them (that’s the number of permutations).
    • If some of the letters are the same, one has symmetries: for each group of \(k\) letters, there are \(k!\) shuffles of those letters, so one has to divide \(n!\) by these symmetries.
    • So, the number of anagrams of the word ERRORE is
      \[
      \frac{6!}{3!2!1!}=60
      \]
      (here \(3!\) is the symmetries of \(3\) Rs etc…
  • If there are just two letters (as in LOLOLOLOL), then the number of anagrams is just the ways of choosing \(k\) positions out of \(n\), – here  \(k\) is the number of the positions where one of the letters is present (say, L), and \(n\) is the total number of letters. Of course, this is just the familiar binomial coefficient
    \[
    {n\choose k}
    \]
  • If the word has \(m\) different letters, one can also interpret the number of anagrams as the number of placing the \(n\) objects into \(m\) boxes: the letter at the position \(l\) is \(a\) if that’s the number of the box where \(l\) is going…
  • So, there are
    \[
    \frac{4!}{2!2!}=6
    \]
    ways to allocate 4 numbers into 2 boxes (2 numbers each), or, equivalently, 6 anagrams of LOLO.
  • How many ways are there to couple 4 elements into 2 pairs? Just 3… What is going on?

Homework:

Sept. 12

  • How to count number of ways to pair \(2n\) objects:
    • One way: place the object into \(n\) different boxes (total number to do so, as we know, is
      \[
      \frac{(2n)!}{2!\cdot2!\cdots 2!}
      \]
      (in the denominator, \(n\) factors). Then we notice that we don’t care about the identities of the boxes,and so can divide that number by \(n!\).
    • or we can say: take the smallest element (initially, just\(1\)) and pair it with any other object, – that can be done in \((2n-1)\) ways. The iterate, – the result will be
      \[
      (2n-1)!!:=(2n-1)\cdot(2n-3)\cdots 5\cdot 3\cdot \cdot 1.
      \]
    • these two results are, of course, the same!
  • Inclusion-exclusion formula.
homework

In the class, there are three clubs, with 10, 8, 7 members in them. There are 17 people who are members of at least one club; 6 people who are members of at least 2 clubs, – how many are members of all three?

Sept. 19

  • Solve the homework problem(s)
  • Ways to choose \(n\) objects of \(k\) different types.

Game: HYPE?

Sept. 26

Game

Oct. 3

  • Properties of binomial coefficients:\[\sum_k (-1)^k{n \choose k}=0\]
  • Generating functions for binomial coefficients.
  • Proofs by bijection: does it work for infinite sets? Can we define the size of a set, by identifying what it is equipotent to?
  • Some interesting bijections: brackets, binary trees and triangulations

Game

Oct. 17

  • More properties of binomial coefficients: number of facets of different dimension in \(d\)-dimensional cubes…
  • and \(d\)-dimensional triangles.

Game: Claim Your Gain

Oct. 31

  • Bijections: integers and natural numbers? rational numbers and natural numbers?
  • Interlude: how many solutions does the equation \(x^2=x\) have? Just \(x=0\) and \(x=1\), right? But what about \[…9918212890625^2=…9918212890625 \mbox{ and } …740081787109376^2=…740081787109376?\]What’s going on here?
  • Interlude: coin sliding and coin rolling

Minority game: with open discussion

Nov. 7

  • Infinities: how to compare them
  • Integers and rationals, – same size…
  • But some infinities are different! Cantor’s diagonal trick

Game: Socialism

Nov. 14

  • More about infinities: can one always compare them?
  • Coin problem…
  • Some interesting bijections: brackets, binary trees and triangulations

Game: Minority with Open Moves

Nov 21

  • More interesting bijections: brackets and paths not touching the floor
  • Pascal triangles with annihilation
  • Given graphs of a few polynomial functions, can you add one more not intersection any of the previous one?

Game: Classic Minority

Nov. 28

  • More about infinities: can one always compare them?
  • More generating functions, – for sequences…
  • Solving \(x^2=x\), again…

Dec 5

  • Infinities! Proof of Cantor-Bernstein
  • Ripples on the water: pond and river
  • Tightening the rope: can one have zero slack?
  • Approximate computations:\(\sqrt{a^2+b}\approx a+\frac{a}{2b}\)

Game: guess the number

Dec 12

Last circle of the year!

  • Funny numbers: \(x^2=x\), finally
  • Funny numbers: find \[1+\frac{2}{1+\frac{2}{1+\frac{2}{1+\ldots}}}\]
  • Can one find a multiple of \(1237\) consisting only of \(1\)’s and \(0\)s?
  • Loose ends: very very skinny polynomials

Games: guess the number; hide on a graph; hide on a line