Cartesian treeIn computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence. Cartesian trees were introduced by in the context of geometric range searching data structures.
Quantization (signal processing)Quantization, in mathematics and digital signal processing, is the process of mapping input values from a large set (often a continuous set) to output values in a (countable) smaller set, often with a finite number of elements. Rounding and truncation are typical examples of quantization processes. Quantization is involved to some degree in nearly all digital signal processing, as the process of representing a signal in digital form ordinarily involves rounding. Quantization also forms the core of essentially all lossy compression algorithms.
Partition function (number theory)In number theory, the partition function p(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4. No closed-form expression for the partition function is known, but it has both asymptotic expansions that accurately approximate it and recurrence relations by which it can be calculated exactly. It grows as an exponential function of the square root of its argument.
TreewidthIn graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.
Truncated normal distributionIn probability and statistics, the truncated normal distribution is the probability distribution derived from that of a normally distributed random variable by bounding the random variable from either below or above (or both). The truncated normal distribution has wide applications in statistics and econometrics. Suppose has a normal distribution with mean and variance and lies within the interval . Then conditional on has a truncated normal distribution. Its probability density function, , for , is given by and by otherwise.
Rank of a partitionIn mathematics, particularly in the fields of number theory and combinatorics, the rank of a partition of a positive integer is a certain integer associated with the partition. In fact at least two different definitions of rank appear in the literature. The first definition, with which most of this article is concerned, is that the rank of a partition is the number obtained by subtracting the number of parts in the partition from the largest part in the partition.
Gibbs measureIn mathematics, the Gibbs measure, named after Josiah Willard Gibbs, is a probability measure frequently seen in many problems of probability theory and statistical mechanics. It is a generalization of the canonical ensemble to infinite systems. The canonical ensemble gives the probability of the system X being in state x (equivalently, of the random variable X having value x) as Here, E is a function from the space of states to the real numbers; in physics applications, E(x) is interpreted as the energy of the configuration x.
