Monday, November 04, 2002

dublab.. infinite wheel. In particular dub selector 8. 4:56:02 PM

N choose M refresher! 11. Ordered with reuse: N^M Equal to number of functions from a particular M-element set to a particular N-element set; or alternatively the number of length-M "strings" built from an N-element "alphabet". Since these two are isomorphic, any length-M "string" can be thought of as a function that maps "positions" to "characters". 10. Ordered, no reuse: N!/(N-M)! Equal to the number of injective (1-1) functions from a particular M-element set to a particular N-element set. Injective functions can be thought of as being an "image" of the domain in the codomain, so this would be the number of different M-sized pictures in an N-element set. Any other real-world interpretations of this? ("Permutations of N elements" is N choose N, ordered without reuse = N!/(N-N)! = N!/0! = N!/1 = N!) 01. Unordered with reuse: ? Equal to the number of "sorted length-M lists" in N; i.e. the the number of equivalence classes in the set of 11 under a total ordering relation on M. Shouldn't be too hard to derive but I got work to do. 00. Unordered, no reuse: N!/(N-M)!M! Equal to number of M-element subsets of N. Note that the powerset of a set S (the set of all subsets of S) has cardinality 2^#S (equal to the number of functions from S to a particular 2-element set e.g. {true, false}). So Sum[M=0..N](N!/(N-M)!M!) = 2^N. Shouldn't be too hard to derive but I got work to do. (Some basics here) 3:56:55 PM

Poset refresher! 1. A powerset 2^S has a partial order <= denoting inclusion, i.e. A <= B if A is a subset of B (with both A and B subsets of S). 2. For a finite set S, you can visualize this as a graph as follows: start with a single node representing S itself. 3. Now draw a node for each of the ways you can "take one away" from S. (So this will be #S nodes.) Draw a line from each of these nodes to S, denoting the fact that they are subsets of S. 4. Now begin the group of "grandchild" nodes by picking a child node and again drawing a node for each of the ways you can "take one away" from it. (So this will be #S - 1 nodes.) 5. Now pick another child node. ... (finish) 3:37:15 PM

Exponentiation refresher! 1a. Cardinality of set S is #S. 1b. Cardinality of set S x T is #S * #T. 1c. Number of functions from A to B is #B ^ #A. 1d. Cardinality of powerset of S (set of subsets of S) is 2 ^ #S (equivalent to the number of functions from S to any 2-element set). 2a. A relation from A to B is a subset of A x B. 2b. So, set of relations from A to B is the powerset of A x B. 2c. So, number of relations from A to B is 2 ^ #(A x B) = 2 ^ (#A * #B). 3a. Intuitively a relation from A to B can be modelled as a function from A to collections of B. 3b. This intuition agrees with reality (at least) in the sense that the number of functions from A to collections of B is equal to the number of relations on A x B : (2 ^ #B) ^ #A = 2 ^ (#B * #A) // by (x^m)^n = x^mn = 2 ^ (#A * #B) // by comm. of products 2:06:36 PM