Learning How to Count

  • Multiplication: Consider that an experiment consists of a sequence of two procedures say, A and B. Let NA and NB denote the number of ways in which one can execute A and B, respectively. It then follows that there is N=NA*NB ways of executing such an experiment. In general, if the experiment consists of a sequence of k procedures, then one may run it in N=N1*N2*….*Nk different ways.
  • Addition: Suppose now that the experiment involves k procedures in parallel(rather than in sequence). This means that we either execute the procedure 1 or the procedure 2 or….. or procedure k. If Ni denote the number of ways that one may carry out the procedure i={1,2,3….,k}, then there are N=N1+N2+…..+Nk ways of running such an experiment.
  • Permutation: Suppose now that we have a set of N different elements and we wish to know the number of sequences we can construct containing each element once, and only once. Note that the concept of sequence is distinct from that of a set, in that order of appearance matters. For instance, the sample space {a,b,c} allows for the following permutations (abc,acb,bac,bca,cab,cba). In general, there are N! possible permutations out of N elements because there are N options for first element of the sequence, but only N-1 options for the second element, and so on until we have only one option for the last element of the sequence. There is also a more general meaning for permutation in combinatorics for which we form sequences of k different elements from a set of N elements. This means that we have N options for the first element of the sequence, but then N-1 options for the second element and so on until we have only N-k+1 options for the last element of the sequence. It thus follows that we have N!/(N-k)! permutations of k out of N elements in this broader sense.
  • Combination: This is a notion that only differs from permutation in that ordering does not matter. This means that we just wish to know how many subsets of k elements we can construct out of a set of N elements. For instance, it is possible to form the following subsets with two elements of {a,b,c,d}: {a,b};{a,c};{a,d};{b,c};{b,d};{c,d}. Note that {b,a} is not counted because it is exactly the same subset as {a,b}. This suggests that, in general, the number of combinations is inferior to the number of permutations because one must be counted only one of the sequences that employ the same elements but with a different ordering. In view that there are N!/[(N-k)!k!] possible combinations of k out of N elements.

 

Source: Statistics for Business and Economics (Marcelo Fernandes)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s