blob: fa034e46fbadd5a80da5716567b08f460b5ff15f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
%This commands provides the text for the definitions on the first
%page.
%This command has one parameter:
% 1) The width of the text
\newcommand\TOneDef[1]{%
\def\LineOfArray##1##2{%
{\ensuremath{##1}}&%
\begin{DisplayFormulae}{0}{0pt}{2ex plus .5ex minus .5ex}%
{\BigChar}{\StyleWithoutNumber}%
{\raggedright##2\par\vspace{\TOneInterlineDef}}%
\end{DisplayFormulae}\\
}
\begingroup
\def\LongestExpr{f(n) = \Omega(g(n))}%
\settowidth{\TmpLengthA}{$\LongestExpr$}
\parbox[t]{#1}{%
\setlength{\HSpace}{#1-\TmpLengthA}%
\begin{tabular}{@{}l@{\hspace{.2em}}|%
p{\HSpace}}
%Line 1
\LineOfArray{f(n) = O(g(n))}%
{iff \Fm[true]{\exists} positive \Fm[true]{c, n_0} such that
\Fm[true]{0 \leq f(n) \leq cg(n)}
\Fm[true]{\MathRemark[\relax]{\forall n \geq n_0}.}}
%Line 2
\LineOfArray{\LongestExpr}%
{iff $\exists$ positive \Fm[true]{c, n_0} such that
\Fm[true]{f(n) \geq cg(n) \geq 0}
\Fm[true]{\MathRemark[\relax]{\forall n \geq n_0}}.}
%Line 3
\LineOfArray{f(n) = \Theta(g(n))}%
{iff \Fm[true]{f(n) = O(g(n))} and \Fm[true]{f(n) = \Omega(g(n))}. }
%Line 4
\LineOfArray{f(n) = o(g(n))}%
{iff \Fm[true]{\lim_{n \to \infty} f(n)/g(n) = 0}.}
%Line 5
\LineOfArray{\lim_{n \to \infty} a_n = a}%
{iff \Fm[true]{\forall \epsilon > 0}, \Fm[true]{\exists n_0} such that
\Fm[true]{\vert a_n - a\vert < \epsilon\MathRemark{\forall n \geq n_0}}.}
%Line 6
\LineOfArray{\sup S}%
{least \Fm[true]{b \in \Real} such that \Fm[true]{b \geq s\MathRemark{\forall s \in S}}.}
%Line 7
\LineOfArray{\inf S}%
{greatest \Fm[true]{b \in \Real} such that \Fm[true]{b \leq s\MathRemark{\forall s \in S}}.}
%Line 8
\LineOfArray{\liminf_{n \to \infty} a_n}%
{\def\FirstPart{\lim_{n\to\infty} \inf \{\mbox{}}%
\Fm[true]{\FirstPart a_i \mid i \geq n,}%
\FmPartB{\FirstPart}{\MathRemark[\relax]{i \in \Natural}}\}
}
%Line 9
\LineOfArray{\limsup_{n \to \infty} a_n}%
{\def\FirstPart{\lim_{n\to\infty} \sup \{\mbox{}}%
\Fm[true]{\FirstPart a_i \mid i\geq n,}%
\FmPartB{\FirstPart}{\MathRemark[\relax]{i \in \Natural}}\}
}
%Line 10
\LineOfArray{\binom{n}{k}}{Combinations: Size $k$ subsets of a size $n$ set.}
%Line 11
\LineOfArray{\cycle{n}{k}}%
{Stirling numbers (1\textsuperscript{st} kind):
Arrangements of an $n$ element set into $k$ cycles.}
%Line 12
\LineOfArray{\SousEnsemble{n}{k}}%
{Stirling numbers (2\textsuperscript{nd} kind):
Partitions of an $n$ element set into $k$ non-empty sets.}
%Line 13
\LineOfArray{\eul{n}{k}}%
{1\textsuperscript{st} order Eulerian numbers:
Permutations \Fm[true]{\pi_1\pi_2\ldots\pi_n} on \Fm[true]{\{1,2, \ldots, n\}} with $k$ ascents.}
%Line 14
\LineOfArray{\euls{n}{k}}{2\textsuperscript{nd} order \mbox{Eulerian} numbers.}
%Line 15
\LineOfArray{C_n}{Catalan Numbers: Binary trees with \Fm[true]{n + 1} vertices.}
\end{tabular}
}%
\endgroup
}
|