summaryrefslogtreecommitdiff
path: root/info/mathtrip/src/definitions.tex
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
}