COMS W3203 Lecture Notes - Lecture 12: Bijection, Symmetric Group, Enumerative Combinatorics

89 views7 pages

Document Summary

Combinatorics: a technique to determine the size of a nite set, (example: sorting by transportations) A partition of a set a is a collection of disjoint subsets of a whose union is a. m. If a is nite and b, , bm is a partition of a, then |a| = Let t be a set whose elements can be described using a procedure with steps. S1, sk such that step 1 can be performed r1 ways regardless of how we did the steps before. n=1 r(i) Domain and image: the 6 permutations are below, analyze the parity and inversions. 1: the number of inversions is equal to 8i < j, a[j] > a[i, for example, in 6, 3 is before 1, 2 is before 1, and 3 is before 2, therefore there are three inversions. 2 = # 1 2 3 inversions = 1. 3 = # 1 2 3 inversions = 1.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents