Lucas Theorem – Proof and Applications

forthright48 on November 16, 2018

Problem

Given non-negative integers $N$, $K$ and a prime number $P$, find the value of:

$$\binom{N}{K} \mod P$$

Sounds like a simple problem right? There are several ways to solve the problem, depending on the constraints of $N$, $K$, and $P$.

Direct: If $N$, $K$ are really small, less than $12$, then we can calculate $\binom{N}{K}$ directly using formula $\frac{N!}{K! \times (N-K)!}$ and find the mod $P$ value. Not gonna work when the values are around $1000$.
DP: If they are slightly bigger but still around $1000$, then we can use dynamic programming to find the result, using the recurrence: $\binom{N}{K} = \binom{N-1}{K} + \binom{N-1}{K-1}$. Not going to work if values are around $10^5$.
Modular Inverse: If $P$ is a large prime, say $10^9+7$, then using modular inverse and some precalculation we can still calculate $\frac{N!}{K! \times (N-K)!}$. But still, we will need to run $O(N)$ loop to calculate $N!$. Not going to work if $N$ is too large. Also, if $P$ is small then there won’t be any modular inverse since $P$ will not be coprime with denominator anymore.

So what do we do when $N$ and $K$ are large (let’s say around $10^9$) and prime $P$ is small, let’s say $37$. Is it still possible?

Of course. We use Lucas Theorem.

Stars and Bars Theorem

forthright48 on September 23, 2018

Problem

Given K variables, $a_1, a_2, a_3 \dots a_K$ and a value $N$, how many ways can we write $a_1 + a_2 + a_3 \dots a_K = N$, where $a_1, a_2, a_3 \dots a_K$ are non-negative integers?

For example, if $K = 3$ and $N=2$, there are 6 solutions.

Prufer Code: Linear Representation of a Labeled Tree

forthright48 on January 28, 2018

I guess this is going to be my first post (apart from the contest analysis’) which is not about Number Theory! It’s not about graph either, even though the title has “Tree” in it. This post is actually about Combinatorics.

Prufer code, in my opinion, is one of the most underrated algorithms I have learned. It has a wide range of applications, yet, very few people seem to know about it. It’s not even a hard algorithm! It’s very easy and you should understand it intuitively.

In this post, we will be discussing what is Prufer Code and its conversion to and from a tree. On next post, we will look into some of its application.

Prufer Code: What is it?

Every labeled tree of $N$ nodes can be uniquely represented as an array of $N-2$ integers and vice versa

The linear array representation of a labeled tree is called Prufer Code. In case you are wondering what’s a labeled tree, it’s just a tree with distinguishable nodes, i.e, each node is marked such that they can be distinguished from one another.

Okay, before we move on to how to covert a labeled tree into Prufer Code and vice versa, let me tell you how I came to know about Prufer Code. If you are a problem setter, the story will be helpful to you.