Explain Pairwise Testing

In pairwise testing, all pairs of values have to be exercised during testing. If there are n parameters, each with m values, then between each two parameter we have m*m pairs. The total number of pairs is m* m* n * (n − 1)/2.
The objective of pairwise testing is to have a set of test cases that cover all the pairs. As there are n parameters, a test case is a combination of values of these parameters and will cover (n−1)+(n−2)+... = n(n−1)/2 pairs. In the best case when each pair is covered exactly once by one test case, m2 different test cases will be needed to cover all the pairs.
For example, if there is a software product being developed for multiple platforms that use the browser as an interface. Suppose the software is being designed to work for three different operating systems and three different browsers. In addition, as the product is memory intensive there is a desire to test its performance under different levels of memory. So, we have the following three parameters with their different values:
Operating System: Windows, Mac, Linux
Memory Size: 128M, 256M, 512M
Browser: IE, Safari, Mozilla
For discussion, we can say that the system has three parameters: A (operating system), B (memory size), and C (browser). Each of them can have three values

which we will refer to as a1, a2, a3, b1, b2, b3, and c1, c2, c3. The total number of pairwise combinations is 9 * 3 = 27. The number of test cases, however, to cover all the pairs is much less. A test case consisting of values of the three parameters covers three combinations (of A-B, B-C, and A-C).
Hence, in the best case, we can cover all 27 combinations by 27/3=9 test cases.
Test cases for pairwise testing:
A        B              C                        Pairs
a1       b1           c1                        (a1,b1)(a1,c1)(b1,c1)
a1       b2           c2                        (a1,b2)(a1,c2)(b2,c2)
a1       b3           c3                        (a1,b3)(a1,c3)(b3,c3)
a2       b1           c2                        (a2,b1)(a2,c2)(b1,c2)
a2       b2           c3                        (a2,b2)(a2,c3)(b2,c3)
a2       b3           c1                        (a2,b3)(a2,c1)(b3,c1)
a3       b1           c3                        (a3,b1)(a3,c3)(b1,c3)
a3       b2           c1                        (a3,b2)(a3,c1)(b2,c1)
a3       b3           c2                        (a3,b3)(a3,c2)(b3,c2)
Often, it will not be possible to generate the minimum set of test cases,
particularly when the number of values for different parameters is different.


For more on this see:
A Concise Introduction to Software Engineering by Pankaj Jalote