Counting with Restrictions

The Central Idea

A restriction changes the set of valid outcomes.

Instead of counting all imaginable outcomes, we count only those that satisfy every stated condition.

The basic workflow is:

Restrictions Can Act in Different Ways

Common restrictions include:

• a forbidden symbol;
• no repetition;
• a required symbol;
• a fixed first or last position;
• a symbol allowed only in certain positions;
• objects that must stay together;
• objects that must stay apart;
• choices that depend on earlier choices;
• upper or lower limits on how often something appears.

Start with the Unrestricted Structure

Before handling the restriction, identify what the count would look like without it.

For example, a four-character code using \(10\) digits with repetition allowed has

unrestricted possibilities.

The restriction then tells us how that structure must be modified.

Direct Restriction Counting

The simplest method is to reduce the number of choices at the stage where the restriction applies.

Suppose a four-digit code may use digits \(0\) through \(9\), but the first digit cannot be \(0\).

The first position has \(9\) choices and each later position has \(10\):

Position Restrictions

A restriction may apply to one particular position.

Suppose a five-character code must begin with a letter and end with a digit.

If the middle positions may contain any letter or digit, then the stage counts are

Therefore,

Forbidden Symbols

If a particular symbol is forbidden everywhere, remove it from the available alphabet.

Suppose strings of length \(6\) are formed from \(8\) symbols, but one designated symbol may not be used.

Each position then has only

choices.

valid strings remain.

No Repetition

If choices cannot be repeated, later stages have fewer options.

Suppose a four-letter string is formed from \(9\) distinct letters without repetition.

The stage counts are

Therefore,

Track What Has Already Been Used

In no-repetition problems, every earlier choice removes an option from later stages.

If \(k\) ordered positions are filled from \(n\) distinct objects without repetition, then the count is

Later lessons will connect this pattern to permutations.

Example: Three-Digit Integers without Repetition

Count three-digit positive integers with no repeated digit.

The first digit cannot be \(0\), so it has

choices.

The second digit may be \(0\), but cannot repeat the first digit, so it also has

choices.

The third digit then has

choices.

Therefore,

Required Symbols

A requirement such as “contains at least one \(A\)” can be difficult to impose directly because the \(A\) might appear in many positions.

In such cases, complementary counting is often more efficient.

Count all strings, subtract those containing no \(A\), and obtain the desired total.

Example: At Least One Required Symbol

A five-character string is formed from \(7\) symbols, and repetition is allowed. How many strings contain at least one \(X\)?

Total strings:

Strings with no \(X\):

Therefore,

Exactly One Required Symbol

“Exactly one” is often easier to count directly.

Suppose a four-character string is formed from

and must contain exactly one \(X\).

Choose the position of \(X\):

Each remaining position has \(4\) non-\(X\) choices:

Therefore,

Exactly \(r\) Special Positions

A general version of the same idea is:

1. choose which positions are special;
2. fill those positions with allowed special choices;
3. fill the remaining positions with allowed nonspecial choices.

This structure appears repeatedly in binomial counting.

Restrictions May Depend on Earlier Choices

A later option may be allowed or forbidden depending on what happened before.

When this occurs, a single constant factor at that stage may not exist.

Split into cases according to the earlier choice or use a decision tree.

Example: Conditional Second Stage

A product has two base models.

• Model \(A\) permits \(5\) upgrades.
• Model \(B\) permits \(3\) upgrades.

The number of valid configurations is

The second-stage choice count depends on the first-stage model.

Adjacency Restrictions

Some arrangements require two objects to be adjacent or forbid them from being adjacent.

These problems often require grouping, complementary counting, or a position-based case split.

Objects That Must Stay Together

Suppose two distinguished objects \(A\) and \(B\) must appear next to each other in a linear arrangement.

Treat the pair as one temporary block.

The internal order of the block may be

or

This block method converts an adjacency restriction into a simpler arrangement count.

Example: Two People Together

Arrange \(5\) distinct people in a row so that Alex and Blair sit together.

Treat Alex and Blair as one block.

Then there are effectively

objects to arrange:

Alex and Blair can switch positions inside the block in

ways.

Therefore,

Objects That Must Stay Apart

“Not adjacent” is often easiest to count by complement.

Count all arrangements, subtract those in which the restricted objects are adjacent.

Example: Two People Not Together

Arrange \(5\) distinct people in a row so that Alex and Blair are not adjacent.

Total arrangements:

Adjacent arrangements:

Therefore,

Separation by Gaps

When several identical or categorized objects must be separated, a gap method can be useful.

First arrange the objects that create the gaps.

Then place restricted objects into those gaps so that forbidden adjacency cannot occur.

A Simple Gap Structure

Suppose three objects

are arranged in a row.

They create four gaps:

If another kind of object must not be adjacent to itself, placing at most one such object in each gap automatically enforces the restriction.

Restrictions on the First or Last Position

Leading and trailing restrictions should usually be handled first.

For example, if a code cannot begin with \(0\) and cannot end with \(5\), then those two positions should be counted using their restricted option sets before treating the unrestricted middle positions.

Example: First and Last Restrictions

Count four-digit codes using digits \(0\) through \(9\) such that the first digit is nonzero and the last digit is not \(5\).

First digit:

choices.

Two middle digits:

choices.

Last digit:

choices.

Therefore,

Overlapping Restrictions

Two restrictions may interact.

For example:

• the first digit cannot be \(0\);
• digits cannot repeat.

The first restriction changes the first-stage count, while the second changes every later stage.

Both must be incorporated together.

Example: Four-Digit Integers without Repetition

Count four-digit positive integers with no repeated digits.

First digit:

nonzero choices.

Second digit:

remaining choices, including \(0\).

Third digit:

Fourth digit:

Therefore,

When Direct Counting Becomes Awkward

A restriction may be easier to express as an unwanted condition.

In that situation, complementary counting can be more efficient:

Example: At Least One Repeated Digit

Count three-digit codes using digits \(0\) through \(9\) that contain at least one repeated digit.

Total codes:

Codes with all digits distinct:

Therefore,

Multiple Forbidden Conditions

If several invalid conditions overlap, simply subtracting each invalid set may remove some outcomes more than once.

In such cases, inclusion–exclusion may be required.

The structure becomes

Example: Two Forbidden Properties

Suppose a collection has \(500\) possible outcomes.

Let \(A\) be the \(120\) outcomes violating rule \(A\), and \(B\) the \(90\) outcomes violating rule \(B\).

Suppose \(30\) outcomes violate both.

Invalid outcomes:

Valid outcomes:

Restrictions Can Suggest Casework

Sometimes a restriction behaves differently depending on an early structural choice.

Split into cases according to that choice, count each case, and add.

This is often cleaner than forcing one formula to handle all branches at once.

Example: First Digit Determines the Rule

Suppose a three-digit code follows these rules:

• if the first digit is even, the second digit has \(4\) allowed choices;
• if the first digit is odd, the second digit has \(7\) allowed choices;
• the third digit always has \(10\) choices.

There are \(5\) even first digits and \(5\) odd first digits.

Even-first case:

Odd-first case:

Therefore,

Restrictions and Decision Trees

A decision tree is useful when available options depend heavily on earlier choices.

Invalid branches can simply be omitted.

Different branch totals can then be added at the end.

Restrictions and State Tracking

More advanced restricted counting problems can be solved by tracking only the information needed to determine what choices remain legal.

Examples of useful state information include:

• which symbols have already been used;
• whether a required symbol has appeared;
• how many special objects have been placed;
• what the previous symbol was;
• which capacities remain available.

This idea leads naturally to recursive counting and dynamic methods.

Restrictions involving Capacities

A category may have a maximum capacity.

Once that capacity is reached, later choices cannot use that category.

Capacity restrictions often require casework, recursion, or generating functions in more advanced settings.

Restrictions involving Minimum Requirements

A condition may require at least one or at least \(r\) occurrences of a particular feature.

These problems may be handled by:

• direct casework by the exact number of occurrences;
• complementary counting;
• inclusion–exclusion if several requirements overlap.

Choose the Method That Simplifies the Restriction

There is no single universal technique for every restriction.

A practical decision sequence is:

1. Can I adjust the stage counts directly?
2. Would the complement be simpler?
3. Would splitting into cases make the rule uniform?
4. Do several bad conditions overlap?
5. Would a decision tree or recursive description help?

Example: Exactly Two Even Digits

Count four-digit codes containing exactly two even digits.

Assume leading zero is allowed and repetition is allowed.

Choose the two positions that will contain even digits:

Each even position has \(5\) choices:

Each odd position has \(5\) choices:

Therefore,

Example: At Most One Repeated Choice

Restrictions involving repetition patterns can quickly become more complex.

Before writing a formula, clarify exactly what the phrase means.

For example, “at most one repeated choice” could mean:

• at most one pair of equal symbols;
• at most one symbol is allowed to repeat;
• no symbol appears more than twice.

Precise definitions are essential before counting.

Restrictions Must Be Interpreted Literally

Small wording differences can change the count substantially.

Compare:

• at least one \(A\);
• exactly one \(A\);
• at most one \(A\);
• no \(A\);
• not all \(A\).

Each describes a different valid set.

Common Error: Applying the Restriction Too Late

Suppose repetition is forbidden.

Writing

and then trying to “remove repeats somehow” may create unnecessary work.

If the no-repetition rule can be built directly into the stages, use

Common Error: Forgetting a Restriction after the First Stage

In a no-repetition problem, the choice count continues to decrease.

After choosing one object, it remains unavailable at every later stage.

Common Error: Treating a Required Condition as a Fixed Position

“Contains at least one \(A\)” does not mean the first position is \(A\).

The required symbol may appear in any allowed position and may appear more than once unless the problem says otherwise.

Common Error: Subtracting Bad Cases without Checking Overlap

If invalid outcomes can violate more than one rule, subtracting each bad set separately may remove some outcomes multiple times.

Use inclusion–exclusion when needed.

Common Error: Forgetting Leading-Zero Rules

A code may begin with \(0\), but a positive integer usually cannot.

Distinguish carefully between:

and

Common Error: Using a Block without Counting Internal Order

If two distinct objects must stay together, treating them as one block counts their placement but not necessarily their order inside the block.

For two distinct objects, there are usually

internal orders.

A Reliable Procedure

1. State exactly what one valid outcome is.
2. Write every restriction in plain language.
3. Identify where each restriction affects the counting process.
4. Use direct stage adjustment when possible.
5. Use decreasing counts when repetition is forbidden.
6. Use complements when the invalid set is simpler.
7. Use cases when different branches follow different rules.
8. Use inclusion–exclusion when forbidden conditions overlap.
9. Use blocks or gaps for adjacency and separation restrictions.
10. Check that every counted outcome satisfies every restriction.

Example: Full Restricted-Counting Workflow

Count four-digit positive integers with no repeated digits and an even last digit.

The even last digit may be \(0\) or one of

Because \(0\) behaves differently from the nonzero even digits, split into cases.

Case 1: last digit is \(0\).

The first digit has \(9\) nonzero choices, then the two middle positions have \(8\) and \(7\) remaining choices:

Case 2: last digit is one of \(2,4,6,8\).

Choose the last digit:

The first digit must be nonzero and cannot equal the last digit, so it has

choices.

The two middle positions then have \(8\) and \(7\) choices.

Therefore,

Practice 1: Forbidden First Digit

How many four-digit codes can be formed from digits \(0\) through \(9\) if the first digit cannot be \(0\)?

Practice 2: No Repetition

How many five-letter strings can be formed from \(8\) distinct letters if no letter may repeat?

Practice 3: At Least One \(X\)

How many four-character strings formed from \(6\) symbols contain at least one designated symbol \(X\), assuming repetition is allowed?

Practice 4: Exactly One \(X\)

How many four-character strings formed from \(\{X,A,B,C,D\}\) contain exactly one \(X\)?

Practice 5: Two People Together

In how many arrangements of \(6\) distinct people are Alex and Blair adjacent?

Practice 6: Two People Apart

In how many arrangements of \(6\) distinct people are Alex and Blair not adjacent?

Practice 7: Four-Digit Integers without Repetition

How many four-digit positive integers have no repeated digits?

Practice 8: Exactly Two Even Digits

How many three-digit codes contain exactly two even digits if leading zero and repetition are allowed?

Practice 9: At Least One Repeat

How many four-character strings formed from \(7\) symbols contain at least one repeated symbol?

Practice 10: Identify the Error

A student counts five-digit positive integers without repetition as

Explain the error and give the correct expression.

Practice Answers

Practice 1

Practice 2

Practice 3

Total strings:

Strings with no \(X\):

Therefore,

Practice 4

Choose the position of \(X\), then fill the other three positions with one of \(4\) non-\(X\) symbols:

Practice 5

Treat Alex and Blair as one block. There are \(5!\) arrangements of the block and the other four people, and \(2\) internal orders:

Practice 6

Total arrangements:

Adjacent arrangements:

Therefore,

Practice 7

Practice 8

Choose the two even positions:

Each even position has \(5\) choices and the odd position has \(5\) choices:

Practice 9

Total strings:

Strings with all symbols distinct:

Therefore,

Practice 10

A five-digit positive integer cannot begin with \(0\), so the first position has only \(9\) choices.

After choosing a nonzero first digit, the second position has \(9\) remaining choices, including \(0\), followed by \(8\), \(7\), and \(6\).

What to Remember

Restrictions modify the available choices and sometimes the best counting method.

• Apply simple position restrictions directly.
• Reduce later choices when repetition is forbidden.
• Use complementary counting for “at least one” and many forbidden conditions.
• Use casework when the restriction behaves differently in different situations.
• Use inclusion–exclusion when bad conditions overlap.
• Use blocks for required adjacency.
• Use complements or gaps for separation restrictions.
• Track enough state to know what remains legal.
• Check that every counted outcome satisfies every restriction.

The most important habit is to let the restriction shape the counting method, rather than forcing every problem into one formula.

Where We Go Next

Restrictions often make later choices depend on earlier ones. In many counting problems, that dependency can be described by reducing the problem to smaller versions of itself.

The next lesson, Recursive Counting, develops this self-referential structure into recurrence relations and step-by-step counting rules.