Book contents
- Frontmatter
- Contents
- Preface to the second edition
- Preface to the first edition
- 1 Introduction
- 2 Combinatorics
- 3 Sets and measures
- 4 Probability
- 5 Discrete random variables
- 6 Information and entropy
- 7 Communication
- 8 Random variables with probability density functions
- 9 Random vectors
- 10 Markov chains and their entropy
- Exploring further
- Appendix 1 Proof by mathematical induction
- Appendix 2 Lagrange multipliers
- Appendix 3 Integration of exp(−½x2)
- Appendix 4 Table of probabilities associated with the standard normal distribution
- Appendix 5 A rapid review of matrix algebra
- Selected solutions
- Index
2 - Combinatorics
Published online by Cambridge University Press: 06 July 2010
- Frontmatter
- Contents
- Preface to the second edition
- Preface to the first edition
- 1 Introduction
- 2 Combinatorics
- 3 Sets and measures
- 4 Probability
- 5 Discrete random variables
- 6 Information and entropy
- 7 Communication
- 8 Random variables with probability density functions
- 9 Random vectors
- 10 Markov chains and their entropy
- Exploring further
- Appendix 1 Proof by mathematical induction
- Appendix 2 Lagrange multipliers
- Appendix 3 Integration of exp(−½x2)
- Appendix 4 Table of probabilities associated with the standard normal distribution
- Appendix 5 A rapid review of matrix algebra
- Selected solutions
- Index
Summary
Counting
This chapter will be devoted to problems involving counting. Of course, everybody knows how to count, but sometimes this can be quite a tricky business. Consider, for example, the following questions:
(i) In how many different ways can seven identical objects be arranged in a row?
(ii) In how many different ways can a group of three ball bearings be selected from a bag containing eight?
Problems of this type are called combinatorial. If you try to solve them directly by counting all the possible alternatives, you will find this to be a laborious and time-consuming procedure. Fortunately, a number of clever tricks are available which save you from having to do this. The branch of mathematics which develops these is called combinatorics and the purpose of the present chapter is to give a brief introduction to this topic.
A fundamental concept both in this chapter and the subsequent ones on probability theory proper will be that of an ‘experience’ which can result in several possible ‘outcomes’. Examples of such experiences are:
(a) throwing a die where the possible outcomes are the six faces which can appear,
(b) queueing at a bus-stop where the outcomes consist of the nine different buses, serving different routes, which stop there.
If A and B are two separate experiences, we write A ∘ B to denote the combined experience of A followed by B.
- Type
- Chapter
- Information
- Probability and InformationAn Integrated Approach, pp. 10 - 21Publisher: Cambridge University PressPrint publication year: 2008