Category Archives: Combinatorics

Grading a class

Imagine we had a class with students and each week they hand in a sheet of homework. Now, you choose a set of of them at random and correct only those . At the end, the grade assigned to a … Continue reading

Posted in Asymptotics, Combinatorics, Computation, Probability | Leave a comment

The Fibonacci Word

Let us define by and , and extend it to a homomorphism of by . Let us note that Something very interesting is going on, each seems to be a prefix of . We will see that this is indeed … Continue reading

Posted in Combinatorics | Leave a comment

Partitions and divisors

The number of partitions of a non-negative integer is, roughly speaking, the number of ways in which we can write as a sum of positive integers disregarding the order of the terms, and we denote this number by . Formally … Continue reading

Posted in Combinatorics, Number Theory | Tagged , | Leave a comment

Binary look-and-say sequences

A few days ago, Numberphile released a video on YouTube about the famous Look-And-Say sequence, presented by John Conway himself. Just as a reminder (if you have not watched the video, which I thoroughly recommend you do), this sequence begins … Continue reading

Posted in Combinatorics, Computation, Generating Functions | Leave a comment

Generating a random permutation

It is well-known that any permutation of can be written as a product of transpositions, that is, of permutations of the form with , where we recall that is the permutation satisfying and for . In this post however, we … Continue reading

Posted in Combinatorics, Computation, Probability | 1 Comment

Prefix-free codes

In this post we will talk about optimal prefix codes for a particular distribution, but first, a little bit of background into the topic. We will be given a message consisting of a stream of symbols which we will translate … Continue reading

Posted in Combinatorics | Tagged , | Leave a comment

Irreducible polynomials over Z_P

Okay, today we are going to talk about the number of irreducible polynomials of a given degree over . One of the main results will be the following Proposition 1 Let be a prime number and let be the product … Continue reading

Posted in Algebra, Generating Functions, Number Theory | 1 Comment