Restricted Combinations

The no. of ways of selecting one or more things from a group of 'n' different things is: 2n – 1

Proof:

Assume each object is to be labeled with either 'yes' or 'no'. 'yes' corresponds to 'selecting' and 'no' corresponds to not selecting.
First object can be labeled in '2' ways, the second one in 2 ways the third one in 2 ways and so on.
From the fundamental theorem of counting total no. of way of labeling 'n' objects
= 2 × 2 × 2 ×......2 = 2n ways.
No object can be selected in one way.
So total no. of ways of selecting at least one from 'n' objects = 2n – 1

The no. of ways of selecting some or all out of (p + q + r) things, where 'p' are alike of one kind, 'q' are alike of second kind and rest 'r' are alike of third kind is:

{(p + 1)(q + 1)(r + 1)} – 1

Proof:

no. of 'A' type objects which can be selected = 0, 1, 2, 3 .... P
no. of ways of selecting any no.of objects
from 'p' similar objects = p + 1,
from 'q' similar objects = q + 1,
from 'r' similar objects = r + 1.
(∵ Selection from 'A' type is independent of selecting from 'B' type and selecting from 'C' type.)

Total no. of ways where at least one object is selected = (p + 1) (q + 1) (r + 1) – 1

Total no. of ways of selecting one or more things from 'p' identical things of one kind, 'q' identical things of second kind, 'r' identical things of third kind from 'n' different things is:

{(p + 1)(q + 1)(r + 1).2n} – 1

Proof:

From counting principle total no.of ways = (p + 1) (q + 1) (r + 1)2n
Removing '1' way in which no object is selected, total no. of ways where at least one object is selected

= (p + 1) (q + 1) (r + 1)2n – 1