nondecreasing

Nondecreasing, also known as monotonically nondecreasing, describes a relation in which the value does not decrease as its input increases. It is used to describe sequences, functions, and more generally monotone mappings on partially ordered sets.

For a sequence a1, a2, a3, …, nondecreasing means a_n ≤ a_{n+1} for every n. An example is 1, 1, 3, 4, 4, 8. Any subsequence of a nondecreasing sequence is also nondecreasing.

For a function f defined on an interval I of real numbers, nondecreasing means x ≤ y implies f(x) ≤ f(y) for all x, y in I. On a domain with a partial order, a monotone (nondecreasing) function satisfies f(a) ≤ f(b) whenever a ≤ b.

Nondecreasing is often contrasted with nonincreasing (the opposite property) and with strictly increasing, where the inequality is always strict. A nondecreasing function can be constant on intervals, which distinguishes it from strictly increasing behavior.

Common examples include the sequence of partial sums of a nonnegative sequence, which is nondecreasing, and the function f(x) = log x, which is nondecreasing on (0, ∞). In sorting and combinatorics, data arranged in nondecreasing order is often referred to as sorted in nondecreasing order. The number of nondecreasing sequences of length k from an n-element set equals the binomial coefficient C(n + k − 1, k) (combinations with repetition).