Why Count Candidate Models?
Subset selection begins with a set of eligible predictors and considers models formed from those predictors. Before comparing model fit or choosing a model, it is useful to know how many possible predictor combinations there are. The count grows quickly: adding one predictor can double the number of subsets, even though it adds only one new variable.
Here, a candidate predictor is one selectable term in the model. For example, if a categorical variable has been represented by several indicator terms, each term may be counted separately when it is eligible for selection. The count depends on how the candidate terms are defined.
The standard counts below assume that every subset is allowed: no predictor is required or forbidden, and there are no restrictions such as requiring an interaction to appear only when its associated main effects are included. If such restrictions apply, the unrestricted subset counts do not directly give the number of admissible models.
Counting Models of a Fixed Size
To form a model of size \(k\), choose \(k\) distinct predictors from the \(p\) eligible predictors. The order of selection does not matter: choosing predictors 2, 5, and 7 gives the same model regardless of the order in which they are listed. The number of size-\(k\) models is the binomial coefficient \(\binom{p}{k}\).
The boundary cases are useful checks. There is exactly one model of size zero, the empty subset, and exactly one model of size \(p\), containing every predictor. Thus \(\binom{p}{0}=\binom{p}{p}=1\). If \(k>p\), selecting \(k\) distinct predictors is impossible, so the count is zero.
Worked Example: Four Terms From Nine Candidate Predictors
A hypothetical insurer is considering nine candidate terms for a regression model of monthly claim counts. The intercept is retained in every model. How many models contain exactly four candidate terms, and how many predictor subsets are there overall?
Method. Count the size-four models with a combination, then count every subset for the overall total. This distinguishes the number at one size from the number across all sizes.
For a model with exactly four terms, \(p=9\) and \(k=4\):
There are therefore 126 models with exactly four selected terms. For the overall number, each of the nine predictors can either be included or excluded, so the total is \(2^9=512\) subsets. As a check, the other model sizes together account for \(512-126=386\) subsets.
Check. The size-four count is less than the overall count, as it must be. The common mistake avoided here is reporting 126 as the total number of candidate models; it counts only the models with four terms.
Counting Every Predictor Subset
For each predictor, there are two independent membership choices: include it in the subset or leave it out. Applying these two choices to all \(p\) predictors gives \(2\cdot2\cdots2\), with \(p\) factors. Thus there are \(2^p\) subsets overall, including the empty subset.
The same result follows by adding the counts for each possible size. Every subset has one and only one size, from zero through \(p\), so these size groups partition the full collection of subsets. Therefore:
This is also the binomial theorem applied to \((1+1)^p\). Each term \(\binom{p}{k}\) counts subsets with \(k\) selected predictors; summing those terms counts every subset once.
For example, with \(p=4\), the counts by size are \(1,4,6,4,1\), corresponding to sizes zero through four. Their sum is \(1+4+6+4+1=16=2^4\). This provides a useful arithmetic check: if the size-by-size counts do not add to \(2^p\), at least one count has been omitted or miscalculated.
Worked Example: Symmetric Model Sizes Among Twelve Terms
A hypothetical health insurer has twelve eligible predictor terms for a model of policyholder service calls. Determine the number of models with exactly two terms, the number with exactly ten terms, and the number of subsets that have neither of those sizes.
Method. Use the combination formula for each specified size, then subtract the two disjoint size groups from the overall subset count. The intercept is fixed and does not affect these counts.
For size two:
For size ten:
The equal counts are expected: choosing ten predictors to include is equivalent to choosing the two predictors to leave out. The total number of subsets is \(2^{12}=4096\). A subset cannot have both size two and size ten, so the number with neither size is
Check. The two specified size groups contain \(132\) subsets, and \(132+3964=4096\), the overall count. The common mistake avoided is adding the size-two and size-ten counts and treating that sum as the total number of models.
What the Counts Say About Search Growth
The total \(2^p\) is an exact count of distinct predictor subsets under the stated assumptions. It also makes the growth from adding predictors easy to quantify:
Each additional eligible predictor doubles the number of candidate subsets. This is exponential growth, not a growth of just one additional model per predictor. The following totals illustrate the scale:
| Number of eligible predictors \(p\) | Number of subsets \(2^p\) |
|---|---|
| 10 | 1,024 |
| 15 | 32,768 |
| 20 | 1,048,576 |
| 30 | 1,073,741,824 |
These figures count candidate subsets; they do not by themselves specify how long fitting or evaluating each model will take. But if a procedure evaluates every candidate, the number of evaluations can become very large as \(p\) increases. Counting the candidates is therefore a first step in assessing whether an exhaustive approach is practical.
Worked Example: Comparing Candidate-Set Sizes
A hypothetical pricing team can consider either 15 or 20 eligible predictor terms when constructing a model. By what factor does the total number of predictor subsets increase when the five additional terms are available, and how many additional subsets does that create?
Method. Calculate each total using \(2^p\), then divide for the factor and subtract for the increase. This compares candidate counts without assuming anything about the result of fitting any model.
With 15 predictors, the number of subsets is
With 20 predictors, it is
The factor increase is
The number of additional subsets is
Check. Five added predictors produce five doublings, hence a factor of \(32\). Multiplying \(32,768\) by \(32\) gives \(1,048,576\), confirming the larger total. The common mistake avoided is treating five extra predictors as only five extra candidate models.
Assumptions and Common Counting Traps
The simple formulas answer a precise question: how many subsets can be formed from \(p\) distinct, independently selectable terms? Check that this matches the model specification before using the counts.
- Counting the intercept as selectable. If the intercept is fixed in every candidate model, it is not among the \(p\) predictors and does not create an additional include-or-exclude choice. If a problem explicitly makes the intercept selectable, the candidate set has a different definition.
- Counting ordered choices. The expression \(p(p-1)\cdots(p-k+1)\) counts ordered selections, not distinct models. Divide by \(k!\) to remove the repeated orderings.
- Counting only one size when asked for all subsets. \(\binom{p}{k}\) is the count at size \(k\); \(2^p\) is the count across all sizes, from zero through \(p\).
- Ignoring model restrictions. If some terms must appear together, or some combinations are prohibited, not every subset is admissible. The unrestricted count \(2^p\) then overstates the allowed set.
- Changing what counts as one predictor. A categorical variable encoded with several indicator terms can contribute several selectable terms. State whether the count is based on original variables or on candidate terms.
Check Your Understanding
For each question, count predictor subsets under the conditions stated. Assume the intercept is fixed unless the question says otherwise.
- A model has five eligible terms. How many models contain exactly two terms, and how many subsets are there overall? (Answer: 10 models of size two; 32 subsets overall.)
- There are ten eligible terms. How many models have exactly three terms, and how many subsets do not have size three? (Answer: 120 models of size three; 904 subsets do not have size three.)
- A set contains fourteen eligible terms. How many subsets have size one or size thirteen, and how many subsets are there overall? (Answer: 28 subsets of the two specified sizes; 16,384 subsets overall.)
- A candidate set grows from eighteen to twenty-one eligible terms. By what factor does the total number of subsets increase, and what are the two totals? (Answer: factor of 8; 262,144 subsets at eighteen terms and 2,097,152 at twenty-one.)
- With eight eligible terms, how many subsets have any size other than four? (Answer: 186 subsets.)