Exam 3 Vocab Flashcards
(49 cards)
recursive definition
Where the value of the function is defined in terms of the output value of the function on smaller input values.
recursion
The process of computing the value of a function using the result of the function on smaller input values.
recursive set
Shows how to construct elements in the set by putting together smaller elements. Defines a set by specifying a starting point and a rule for generating new elements from existing ones.
basis step
Specify the value of the function at zero.
recursive step
Give a rule for finding its value at an integer from its value at smaller integers.
root
Designated vertex of a perfect binary tree; acts as starting point for tree’s structure.
binary tree (perfect or full)
A perfect binary tree has all internal nodes having exactly two children, and all leaf nodes are at the same level (depth). A full binary tree has every node having either zero or two children.
structural induction
A type of induction used to prove theorems about recursively defined sets that follows the structure of the recursive definition.
product rule
Let A1, A2,…,An be finite sets. Then, |A1 x A2 x…….x An| = |A1| dot |A2| dot…….dot |An|.
sum rule
Consider n sets, A1, A2,…,An. If the sets are pairwise disjoint (which means that Ai ∩ Aj = 0 for i != j), then: |A1 ∪ A2……∪ An| = |A1| + |A2| +…..|An|.
permutation
An ordered arrangement of objects from a set where the order of arrangement matters.
r-permutation
A sequence of r items with no repetitions, all taken from the same set.
combination
A selection of items from a set where the order of selection does not matter.
r-combination
A subset of size r is called an r-subset, sometimes referred to as an r-combination.
counting by complement
A technique for counting the number of elements in a set S that have a property by counting the total number of elements in S and subtracting the number of elements in S that do not have the property.
inclusion-exclusion (2 sets)
A technique for determining the cardinality of the union of sets that uses the cardinality of each individual set and the cardinality of the intersections of the sets.
(binary) relation
A binary relation between two sets A and B is a subset R of A x B.
arrow diagram
In an arrow diagram of a relation R on sets A and B, the elements of A are listed on the left, the elements of B are listed on the right, and an arrow points from a ∈ A to b ∈ B if aRb.
(binary) relation on a domain
A binary relation on a set A is a subset of A x A.
reflexive
anti-reflexive
symmetric
anti-symmetric
transitive
