Counting: Permutations and Combinations

Table of Contents

1. Counting Without Listing
2. The Rule of Product
3. PINs and Passwords: Counting Strings
4. Factorials: Counting Orderings
5. Permutations: Order Matters
6. Combinations: Order Does Not Matter
7. Why Brute Force Explodes
8. BigInt for Huge Counts
9. Pagination and Batching
10. Recipe: The counting Module
11. Try It Yourself

1. Counting Without Listing

How many different 4-digit PINs exist? You could write them all out: 0000, 0001, 0002, and so on. That works, but it is slow, and for a bigger question ("how many 8-character passwords?") it is impossible. Counting is the math skill of getting the number of possibilities without ever building the list.

Programmers need this more often than you would expect:

• How strong is a password format, and how long would an attacker need?
• How many test cases does a form with five dropdowns really have?
• How many pages does a table need if it shows 10 rows at a time?
• Will a "try every combination" loop finish today, or after the sun burns out?

The last question connects directly to Functions, Growth and Logarithms and Big-O Notation. Counting tells you how big n is. Big-O tells you what that does to your code.

2. The Rule of Product

The one rule behind almost everything in this chapter is the rule of product: if you make several choices one after another, the total number of outcomes is the number of options for each choice, multiplied.

A small cafe offers a lunch set:

• 3 mains (fried rice, noodles, amok)
• 2 drinks (iced tea, coffee)
• 4 desserts

const mains = 3;
const drinks = 2;
const desserts = 4;

console.log(mains * drinks * desserts); // 24

There are 24 different lunch sets. Why multiply and not add? Pick fried rice first: it can go with 2 drinks, and each of those with 4 desserts, so that is 8 sets for fried rice alone. Noodles gives 8 more, amok 8 more: 8 + 8 + 8 = 24. Multiplying is just a shortcut for that repeated adding.

Use addition when the choices are alternatives ("a main or a drink"), and multiplication when you do one thing and then another.

The same idea counts a form. A signup page with a country dropdown (200 options), a language dropdown (10 options), and a plan radio button (3 options) has 200 * 10 * 3 = 6,000 combinations of inputs. Nobody tests all of them by hand, but now you know the size of the problem.

3. PINs and Passwords: Counting Strings

A string of a fixed length, where every position is filled independently from the same set of symbols, is the rule of product in its simplest form. If there are s symbols to choose from and L positions, the count is:

s * s * s * ... (L times)  =  s ^ L

The ^ here means "to the power of", which JavaScript writes as **. Here s ** L means "multiply s by itself L times". A 4-digit PIN has 10 symbols (0-9) and 4 positions:

console.log(10 ** 4); // 10000
console.log(10 ** 6); // 1000000

So there are 10,000 four-digit PINs and 1,000,000 six-digit PINs. Adding two digits made the space 100 times bigger, because each new position multiplies the count by 10.

Here are common password alphabets:

An 8-character password made of letters and digits has 62 ** 8 possibilities. Let's calculate it:

console.log(62 ** 8); // 218340105584896
console.log(26 ** 8); // 208827064576

That is about 218 trillion versus 209 billion. Allowing uppercase letters and digits made the space roughly 1,000 times bigger. In general, adding length helps more than adding symbols, because length is the exponent.

4. Factorials: Counting Orderings

Now a different question. You have 3 friends, Dara, Sophea, and Vireak, and you want to line them up for a photo. How many orders are there?

• 3 choices for who stands first.
• Then 2 people are left for the second spot.
• Then 1 person is left for the last spot.

Rule of product: 3 * 2 * 1 = 6. The six orders are DSV, DVS, SDV, SVD, VDS, VSD.

Multiplying a number by every whole number below it down to 1 is called the factorial, written n! and read "n factorial":

Notice how fast it grows. Ten people can stand in line in over 3.6 million different orders. We will write factorial in the recipe at the end of this chapter.

5. Permutations: Order Matters

A race has 8 runners, and the top 3 get gold, silver, and bronze. How many different podiums are possible?

• 8 choices for gold.
• 7 left for silver.
• 6 left for bronze.

console.log(8 * 7 * 6); // 336

This is a permutation: choosing k items from n where the order matters (gold, silver, bronze is different from bronze, silver, gold). You multiply just the first k terms of the factorial:

P(n, k) = n * (n-1) * ... * (n-k+1)   =   n! / (n-k)!

P(8, 3) = 8! / 5! = 336. The / (n-k)! simply cancels the tail of the long multiplication you do not need.

When k equals n (arrange everyone), you get the plain factorial: P(5, 5) = 5! = 120.

Real uses: the number of ways to rank search results, assign seats, or choose a President, Vice-President, and Treasurer from a group.

6. Combinations: Order Does Not Matter

Now the lottery. You pick 6 numbers from 49 and the order you pick them in does not matter. Picking 3, 17, 22, 30, 41, 48 is the same ticket as 48, 41, 30, 22, 17, 3.

This is a combination: choosing k items from n where the order does not matter. It is written C(n, k) and read "n choose k".

How do we get it? Start with permutations, which count every order separately, then divide by the number of ways to order the k chosen items (k!) because those orderings all count as the same pick:

C(n, k) = P(n, k) / k!  =  n! / (k! * (n-k)!)

A small check: choose 2 people from A, B, C, D.

Permutations: AB BA AC CA AD DA BC CB BD DB CD DC   (12)
Combinations: AB AC AD BC BD CD                      (6)

P(4, 2) = 12, and 12 / 2! = 6. Each pair was counted twice, once per order, so dividing by 2 fixes it.

A simple test: would swapping two picks create a different result? If yes, it is a permutation. If no, it is a combination.

Combinations appear in testing too: if you have 20 features and want to test every pair of them together, you need C(20, 2) = 190 pair tests. It also counts "handshakes": in a meeting of n people where everyone greets everyone, there are C(n, 2) handshakes, which is n * (n - 1) / 2. That is the exact same shape as the nested loop in Big-O Notation, which is why nested loops are called O(n²).

7. Why Brute Force Explodes

Brute force means trying every possibility until one works. Counting tells you whether that is realistic. Suppose a computer can check one billion (1,000,000,000) guesses per second. We use the counts above:

The two growth shapes are worth separating.

• Exponential, like s ** L: every extra character multiplies the work by s. Length is your friend as a defender.
• Factorial, like n!: every extra item multiplies the work by the new n. This grows even faster than exponentials.

This is the real reason the 4-digit PIN on a phone is protected by "wait 30 seconds after too many tries" and not by its size. With only 10,000 possibilities, size alone cannot protect it. The delay does.

Also notice the factorial rows: "try every order" is fine for 10 items and hopeless for 20. Problems like finding the shortest route that visits many cities hit this wall, and that is one reason programmers invent smarter algorithms instead of brute force. You will meet this kind of thinking again in the planned Data Structures & Algorithms series.

8. BigInt for Huge Counts

Now a practical problem. Try the factorial of 25 with ordinary numbers:

let result = 1;
for (let i = 2; i <= 25; i++) {
  result *= i;
}
console.log(result); // 1.5511210043330986e+25

JavaScript prints it in scientific notation and it is no longer exact. As you saw in Integers, Overflow and Precision, a normal number is exact only up to Number.MAX_SAFE_INTEGER, which is 9007199254740991 (about 9 quadrillion). Counting problems blow past that quickly: 18! still fits, but 19! and beyond do not.

The answer is BigInt, a number type that can grow as large as memory allows. You write a BigInt literal with an n after the digits, and you cannot mix it with ordinary numbers:

let result = 1n;
for (let i = 2n; i <= 25n; i++) {
  result *= i;
}
console.log(result); // 15511210043330985984000000n

Rules to remember:

• 5n is a BigInt, 5 is a number. 5n + 5 throws a TypeError. Convert with BigInt(5) or Number(5n).
• / on BigInts drops the remainder: 7n / 2n is 3n.
• ** works: 10n ** 30n is exact.
• console.log prints the trailing n for BigInts, but String(x) and template strings (${x}) do not include it.

Our counting functions will return BigInt so the answers stay exact. If you only want a rough size, use Number(x) and accept some rounding.

9. Pagination and Batching

Counting also covers a very ordinary job: how many pages does a list need? A table shows 10 rows per page and the API returned 95 rows.

console.log(95 / 10);            // 9.5
console.log(Math.ceil(95 / 10)); // 10

Math.ceil rounds up. You need ten pages, because the last page holds the remaining 5 rows. Rounding down would lose those 5 rows, and rounding to the nearest would give 10 here but 9 for 94 rows (9.4), which would be wrong. The rule is simple: pages = ceil(items / pageSize).

Edge cases worth testing:

The same formula splits work into batches. Sending 2,500 emails with a limit of 100 per request takes Math.ceil(2500 / 100) = 25 requests. Inserting 10,001 database rows in groups of 1,000 takes 11 groups, and the last one is nearly empty. Getting ceil wrong is a classic off-by-one bug where the last few items are silently never processed.

Page p (counting from 1) starts at index (p - 1) * pageSize:

const items = Array.from({ length: 95 }, (_, i) => i + 1);
const pageSize = 10;
const page = 10;

const start = (page - 1) * pageSize; // 90
console.log(items.slice(start, start + pageSize)); // [ 91, 92, 93, 94, 95 ]

10. Recipe: The counting Module

Create src/counting.js in your mathlab project. Every function that can produce a big answer returns a BigInt.

// src/counting.js — counting things without listing them.

export function factorial(n) {
  if (!Number.isInteger(n) || n < 0) {
    throw new RangeError("factorial needs a whole number >= 0");
  }
  let result = 1n;
  for (let i = 2n; i <= BigInt(n); i++) {
    result *= i;
  }
  return result;
}

// Ordered picks: n * (n-1) * ... * (n-k+1)
export function permutations(n, k = n) {
  if (k > n) return 0n;
  let result = 1n;
  for (let i = 0; i < k; i++) {
    result *= BigInt(n - i);
  }
  return result;
}

// Unordered picks ("n choose k"). Dividing at every step keeps the
// intermediate value an exact whole number.
export function combinations(n, k) {
  if (k > n) return 0n;
  const small = Math.min(k, n - k);
  let result = 1n;
  for (let i = 1; i <= small; i++) {
    result = (result * BigInt(n - small + i)) / BigInt(i);
  }
  return result;
}

// How many strings of `length` characters from an alphabet of this size.
export function passwordSpace(alphabetSize, length) {
  return BigInt(alphabetSize) ** BigInt(length);
}

// How many pages do you need to show totalItems, pageSize per page?
export function pageCount(totalItems, pageSize) {
  if (pageSize <= 0) throw new RangeError("pageSize must be positive");
  return Math.ceil(totalItems / pageSize);
}

A few notes on the design:

• permutations(n, k = n) multiplies only k terms, so it never computes the whole n! and then divides.
• combinations uses min(k, n - k) because C(49, 6) equals C(49, 43), and doing 6 steps is shorter than 43. At each step the running result is itself a combination count, so the division is always exact.
• pageCount returns an ordinary number: page counts are small.

Now add the export to src/index.js:

export * from "./counting.js";

Then add this to demo.js (or a new file) and run node demo.js:

import {
  factorial, permutations, combinations, passwordSpace, pageCount,
} from "./src/index.js";

console.log(factorial(5));            // 120n
console.log(factorial(25));           // 15511210043330985984000000n
console.log(permutations(8, 3));      // 336n
console.log(combinations(5, 2));      // 10n
console.log(combinations(49, 6));     // 13983816n
console.log(passwordSpace(10, 4));    // 10000n
console.log(passwordSpace(62, 8));    // 218340105584896n
console.log(passwordSpace(94, 12));   // 475920314814253376475136n
console.log(pageCount(95, 10));       // 10
console.log(pageCount(101, 10));      // 11

The 12-character answer is far above Number.MAX_SAFE_INTEGER, so a plain number could not show it exactly. That is BigInt earning its place.

You can also estimate how long a brute-force attack takes:

const guessesPerSecond = 1e9;
const seconds = Number(passwordSpace(62, 8)) / guessesPerSecond;
console.log(seconds / 3600 / 24); // about 2.53 (days)

Number(...) converts the BigInt so we can divide by a regular number. The tiny rounding is fine because we only want an estimate.

11. Try It Yourself

1. Lunch sets. The cafe adds a fourth main and a third drink. Using the rule of product, how many lunch sets are there now? Check with code.
2. PIN upgrade. Use passwordSpace to compare 4-digit, 6-digit, and 8-digit PINs. By what factor does each pair of extra digits multiply the space? Then compute how long 8 digits would take at one billion guesses per second.
3. Permutation or combination? For each, say which it is, then compute it with mathlab: (a) choosing 3 of 10 students to form a committee, (b) assigning 3 of 10 students to be captain, vice-captain, and secretary, (c) choosing 5 cards from a 52-card deck. Check that (b) is exactly 3! = 6 times (a).
4. Symmetry. Print combinations(10, 3) and combinations(10, 7). Why are they equal? (Hint: choosing 3 to include is the same as choosing 7 to leave out.)
5. Pagination. Write pageSlice(items, page, pageSize) that returns the items for one page, using pageCount to reject a page number that is too high. Test with 95 items, 10 per page, pages 1, 10, and 11.
6. Where does Number give up? Find the smallest n for which Number(factorial(n)) > Number.MAX_SAFE_INTEGER. Loop n upward and stop when the condition is true. You should find it is 19.

Counting told you how many possibilities there are. The next chapter asks the more interesting question: how likely is each one? Continue with Probability Basics, where randomInt, expected value, and the birthday paradox build on exactly these counts.