# Shared Flashcard Set

## Details

Discrete Mathematics Midterm 2
Cake Cutting, Stirling Numbers, Permutations, Counting Tricks, Methods of Inference, Functions
8
Mathematics
11/12/2009

Term
 Stirling Numbers (1st Kind): Recursion Relation
Definition
 Number of permutations of n elements that consist of exactly k cycles.
Term
 Stirling Numbers (1st Kind): Recursion Relation
Definition
 Number of k partitions on a n set.   S(n, k) = S(n-1, k-1) + k*S(n-1, k) S(n,1) = S(n,n) = 1
Term
 Cake Cutting
Definition
 k cuts on n dimensions:   P(k,n) = P(k-1, n) + P(k-1, n-1)
Term
 n-lists (Enumeration)
Definition
 For lists: order matters, repetition is permissible   k lists from an n set:   k^n w/ no repetition: n!/(n-k)!
Term
 n-multisets (Enumeration)
Definition
 set with repetition:   (n+k-1)!/(n-1)!k!
Term
 P(An) Where set A consists of n items (How many?)
Definition
 2^n
Term
 |An x Bm| Where A, B consist of n,m elements (How many?)
Definition
 n x m
Term
 Map Ax(AxA) to (AxA)xA (how many?)
Definition
 (n^3)^(n^3)
Supporting users have an ad free experience!