Skip main navigation

Glossary

Glossary
The sequence of letters A, B, C

Symbols A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Symbols

A comprehensive list of symbols is available here

(exists) :there exists.

(forall): for every

(in): belongs to

(cup): union of sets

(cap): intersection of sets

(setminus): difference of sets

(times): cartesian product of sets

(log(x)): natural logarithm of (x) (to base (e))

(vert Avert): number of elements of a finite set (A)

(log_a(x)): logarithm to basis (a) of (x)

(e): the Euler number 2.71828…

(I_n:=lbrace1,2,dots,nrbrace)

(mathcal P(Omega)): the set of the parts of a set (Omega), that is the family of all the subsets of (Omega). For instance (mathcal P(lbrace0,1rbrace)=lbraceemptyset, lbrace 0rbrace, lbrace 1rbrace, lbrace 0,1rbracerbrace)

(mathbb R): the set of real numbers

(mathbb Q): the set of rational numbers

(mathbb N): the set of natural numbers (0,1,2,3,…)

(mathbb Z): the set of integer numbers (…,-3,-2,-1,0, 1,2,3,…)

(mathbb R[[X]]): the set of formal power series with real coefficients

Combinatorial symbols

(C(n,k)): number of (k)-collections of (I_n) without repetitions

(C((n,k))): number of (k)-collections of (I_n) with possible repetitions, or number of (n)-compositions of (I_k)

(D_n): number of derangements of ((1,2,…,n))

(S(n,k)): number of (k)-sequences of (I_n) without repetitions

(S((n,k))): number of (k)-sequences of (I_n) with possible repetitions, or number of (n)-sharings of (I_k)

(S(n,k;(k_1,…,k_n))): number of (k)-sequences of (I_n) with occupancy sequence ((k_1,…,k_n))

(Biglbracebegin{matrix}k newline nend{matrix}Bigrbrace): Stirling number of II kind (k) over (or subset) (n)

(mathfrak B_k): the (k)-th Bell number

([X^m]A(X)): the coefficient of (X^m) in the formal power series (A(X))

A

Anagram: an anagram of a word is aword obtained via a permutation of the sequence of its letters.

B

Bell number: the (k)-th Bell number, denoted by (mathfrak B_k), is the number of partitions of (I_k).

Bijective: a bijective function is a function which is injective and surjective. Namely a function that never maps distinct elements of its domain to the same element of its codomain and such that any element of the codomain is in the range of the function.

Binomial: the binomial coefficient (n) over (k), denoted by (binom nk), is the number (frac{n!}{k!(n-k)!}). It is the number of possible choices of (k) elements among (n)

C

Characteristic OGF: the characteristic OGF of a subset (E) of the set (mathbb N) of natural numbers is the formal power series [I^{textrm{OGF}}E(X)=sum{kin E}X^k]

Characteristic EGF: the characteristic EGF of a subset (E) of the set (mathbb N) of natural numbers is the formal power series [I^{textrm{EGF}}E(X)=sum{kin E}frac{X^k}{k!}]

Codomain of a function: it is the set into which all of the output of the function is constrained to fall.

Collection a (k)-collection of (I_n) is a non ordered family ([x_1,dots,x_k]) where (x_1,…,x_k) belong to (I_n=lbrace1,dots,nrbrace). The collection is said to be without repetitions if its elements are distinct, in which case it is a set, denoted also by (lbrace x_1,…,x_k rbrace).

Composition: an (n)-composition of (k) is a (n)-sequence ((k_1,…,k_n)) of (mathbb N) such that (k_1+cdots +k_n=k).

D

Decreasing function: a function (f) is called decreasing (also monotonically decreasing, or non-increasing), if for all (xleq y) in the domain of (f) one has (f(x)geq f(y)), so it reverses the order. It is called strictly decreasing if (x< y) implies (f(x)> f(y)).

Derangement: a derangement of a sequence ((b_1,…,b_n)) is a permutation ((a_1,…,a_n)) of ((b_1,…,b_n)) such that (a_1not=b_1,…,a_nnot=b_n).

Domain of a function: the set of “input” or argument values for which the function is defined.

E

Elementary event: an element of a given sample space.

Event: a subset of a sample space.

Exponential function: a function that associates to a real number (x) the number (a^x), for some (a>0).

F

Factorial The factorial of (ninmathbb N) is (n!:=ntimes (n-1)timescdotstimes 1).

Formal power series A formal power series in the indeterminate (X) with real coefficients is an expression of the form [A(X)=a_0+a_1X+a_2X^2+…+a_nX^n+…] where the coefficients (a_n), (ninmathbb N), of the series belong to the set of real numbers

G

H

I

Increasing function: a function (f) is called increasing (also monotonically increasing, or non-decreasing), if for all (xleq y) in the domain of (f) one has (f(x)leq f(y)), so it preserves the order. It is called strictly increasing if (x< y) implies (f(x)< f(y)).

Injective: an injective function, or one-to-one function, is a function that never maps distinct elements of its domain to the same element of its codomain.

J

K

L

Logarithm function: the inverse of an exponential function. Namely if (a>0, anot=1), (x=log_a(y)) means that (y>0) and (y=a^x). The natural logarithm (log_e) in base (e) will be denoted by (log).

M

N

O

Occupancy A (k)-sequence of (I_n) with occupancy sequence ((k_1,…,k_n)) is a sequence with (k_1) repetitions of 1, …, (k_n) repetitions of (n)

P

Partition

Permutation: a permutation of the (k)-sequence ((a_1,…,a_k)) of (I_n) is any (k)-sequence ((b_1,…,b_k)) such that the collection ([b_1,…,b_k]) of its elements coincides with ([a_1,…,a_k]) .

Probability see uniform probability

Q

R

Range of a function: the set of values the function takes on as output.

Reciprocal: it means multiplicative inverse.

S

Sample space: the set of all possible outcomes or results of a probabilistic experiment.

Sequence: a (k)-sequence of (I_n) is an ordered sequence ((x_1,dots,x_k)) where (x_1,…,x_k) belong to (I_n=lbrace1,dots,nrbrace). The sequence is said to be without repetitions if its elements are distinct.

Sharing: an (n)-sharing of (I_k) is a (n)-sequence ((C_1,…,C_n)) of pairwise disjoint – possibile empty – subsets of (I_k), whose union is (I_k).

Stirling formula: (n!sim sqrt{2pi}n^ne^{-n}) as (nto +infty).

Stirling number of II kind: the Stirling number of second kind , denoted by (Biglbracebegin{matrix}k newline nend{matrix}Bigrbrace) (reads (k) over (n), or (n) subset (k)), is the number of (n)-partitions of (I_k).

Surjective function: a function for which codomain and range coincide.

T

U

Uniform probability: the uniform probability on a finite set (Omega) is the function (P:mathcal P(Omega)to [0,1]) defined by (P(A)=dfrac{vert Avert}{vertOmegavert}) for all (AsubseteqOmega).

V

W

X

Y

Z

This article is from the free online

Combinatorics: Strategies and Methods for Counting

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education