Foundations‎ > ‎

Discrete Mathematics

The following selected Discrete Math topics are often ingrained into computer science problem.

Permutation

A permutation of a set of objects is an arrangement of those objects into a particular order. The number of permutations of n distinct objects is n!.

Number of k-combinations (n choose k)

"n choose k" is the number of ways one can select k objects out of a larger group of n objects, where, unlike permutation, order does not matter. Most notably, it occurs as a coefficient in the binomial formula and can be used to construct a Pascal's triangle.


Pascal's Triangle

Pascal's triangle is a triangular array of the binomial coefficients. It can be used to calculate coefficients in a binomial expansion.

(x + y)2 = x2 + 2xy + y2 = 1x2y0 + 2x1y1 + 1x0y2.

 
 
 Pascal's triangle
 n-choose-k implementation

Series

A series is the sum of the terms of a sequence of numbers. The series is said to be convergent if it approaches a given number, and divergent otherwise (if the infinite sequence does not have a limit). In computer science most notable divergent series is the sum of all natural numbers 1 + 2 + 3 + 4 + · · · calculated as follows.




Congruence