#header-inner {background-position: right !important; width: 100% !important;}

8/15/14

Counting & Probablitity.

Sets can be expressed as Sum(-s) of Disjoint Sets or as Cartesian Products.


Sum.

Amount of possibilities of selecting element from one of two disjoint Sets equals sum of Cardinalities of these Sets.

Cardinality of a Set is number of elements in that Set.

|A ∪ B| = |A| + |B|.


Product.

Amount of possibilities of selecting ordered pair equals to amount of possibilities of selecting first element multiplied by amount of possibilities of selecting second element.

|A × B| = |A| · |B|.


Words.

An n-length word over finite set (alphabet) S is a sequence of n S-set elements, with or without elements repetition.

for example:

we have S = { 0, 1 }, n = 3.

there are 8 binary words of length 3:

000, 001, 010, 011, 100, 101, 110, 111.


Permutations.

Permutation of a finite set S is ordered sequence of all S-set elements, with each of elements occuring only once.

for example:

for S = { a, b, c }

we have 6 permutations: abc, acb, bac, bca, cab, cba.

amount of pemutations of n-element set Sn equals n! .

perm_count(Sn) = |Sn|! = n! .



Combinations.

k-combination of n-element set S is a k-element subset of set S.

for example: if we have S = { a, b, c, d }, k = 2, then we have six 2-combinations of S:

{ a, b }, { a, c }, { a, d } , { b, c }, { b, d }, { c, d }.



number of k-combinations of n-element set S equals:

comb_count(Sn)
 =  (
n
k
)  = 
n!
--------------- 
k!·(n - k)!



Probability.

def. Event Space S is a Set with Elementary Events.

def. Possible Outcome H, of experiment, H ⊂ S, 0 ≤ |H| ≤ |S|.

def. Elementary Event E is possible outcome of an experiment, E ⊂ S, 0 ≤ |E| ≤ 1.

def. Probability P(H, S) = |H| / |S|.


See also: [4], [7].

No comments:

Post a Comment