Counting labeled graphs
1. Labeled graphs Let the number of vertices in a graph be $n$. We have to compute the number $G_n$ of labeled graphs with $n$ […]
Month: July 2021
Balanced bracket sequences
1. Overview A balanced bracket sequence is a string consisting of only brackets, such that this sequence, when inserted certain numbers and mathematical operations, gives a valid […]
Placing Bishops on a Chessboard
Find the number of ways to place $K$ bishops on an $N \times N$ chessboard so that no two bishops attack each other. 1. Algorithm […]
Generating all $K$-combinations
In this article we will discuss the problem of generating all $K$-combinations. Given the natural numbers $N$ and $K$, and considering a set of numbers […]
Stars and bars
Stars and bars is a mathematical technique for solving certain combinatorial problems. It occurs whenever you want to count the number of ways to group […]
Burnside’s lemma / Pólya enumeration theorem
1. Burnside’s lemma Burnside’s lemma was formulated and proven by Burnside in 1897, but historically it was already discovered in 1887 by Frobenius, and even earlier in 1845 by Cauchy. […]
The Inclusion-Exclusion Principle
The inclusion-exclusion principle is an important combinatorial way to compute the size of a set or the probability of complex events. It relates the sizes […]
Catalan Numbers
Catalan numbers is a number sequence, which is found useful in a number of combinatorial problems, often involving recursively-defined objects. This sequence was named after […]
Binomial Coefficients
1. Overview Binomial coefficients $\binom n k$ are the number of ways to select a set of $k$ elements from $n$ different elements without taking […]
Finding Power of Factorial Divisor
You are given two numbers $n$ and $k$. Find the largest power of $k$ $x$ such that $n!$ is divisible by $k^x$. 1. Prime $k$ […]
Finding the rank of a matrix
The rank of a matrix is the largest number of linearly independent rows/columns of the matrix. The rank is not only defined for square matrices. The […]
Calculating the determinant using Kraut method in $O(N^3)$
1. Overview In this article, we’ll describe how to find the determinant of the matrix using Kraut method, which works in $O(N^3)$. The Kraut algorithm […]
Calculating the determinant of a matrix by Gauss
Problem: Given a matrix $A$ of size $N x N$. Compute its determinant. 1. Algorithm We use the ideas of Gauss method for solving systems of […]
Gauss method for solving system of linear equations
Given a system of $n$ linear algebraic equations (SLAE) with $m$ unknowns. You are asked to solve the system: to determine if it has no […]
Finding repetitions
Given a string $s$ of length $n$. A repetition is two occurrences of a string in a row. In other words a repetition can be described by […]
Manacher’s Algorithm – Finding all sub-palindromes in $O(N)$
1. Statement Given string $s$ with length $n$. Find all the pairs $(i, j)$ such that substring $s[i\dots j]$ is a palindrome. String $t$ is […]
Expression parsing
A string containing a mathematical expression containing numbers and various operators is given. We have to compute the value of it in $O(n)$, where $n$ […]
Lyndon factorization
1. Lyndon factorization First let us define the notion of the Lyndon factorization. A string is called simple (or a Lyndon word), if it is strictly smaller than any […]
Suffix Automaton
A suffix automaton is a powerful data structure that allows solving many string-related problems. For example, you can search for all occurrences of one string in another, […]
Suffix Tree. Ukkonen’s Algorithm
1. Overview This article is a stub and doesn’t contain any descriptions. For a description of the algorithm, refer to other sources, such as Algorithms on […]
