Combinatorics: nCr, nPr and Stirling Numbers

After reading, you will know how to count combinations, permutations, set partitions and cycles exactly, and which of the four counting rules fits a given problem.

What these counters do

Combinatorics answers "how many ways?" without listing them all. This page computes four related counts exactly, using whole-number arithmetic so the answers stay correct even when they grow to hundreds of digits.

Here is a quick hook. You have 10 distinct books and 4 empty slots on a shelf. If the order of the 4 chosen books matters, there are 5040 arrangements. If order does not matter, there are only 210 selections. Same 10 books, same 4 slots, but the two counts differ by a factor of 24, which is exactly 4!. That factor is the heart of the difference between permutations and combinations.

Stirling and Bell numbers answer a different family of questions: how many ways to split a set into groups, and how many ways to arrange items into cycles. They show up in probability, algebra and the analysis of algorithms.

The four modes and when to use each

Combinations, \binom{n}{k} (nCr): Choose k items from n when order does not matter. Use it for lottery picks, committees, poker hands.
Permutations, P(n,k) (nPr): Arrange k items from n when order matters. Use it for rankings, passwords with distinct characters, race finishes.
Stirling numbers of the second kind, S(n,k): Count the ways to partition n labeled items into exactly k nonempty unlabeled groups. Use it when you split objects into a fixed number of bundles and the bundles have no names.
Stirling numbers of the first kind (unsigned), c(n,k): Count the permutations of n items that have exactly k cycles. Use it when the structure is about cycles, not order.
Bell number, B_n: Count all partitions of n items into any number of groups. It is the sum of S(n,k) over all k.

Do not reach for these when repetition is allowed and unlimited. If a lock uses 4 digits from 0 to 9 with repeats allowed, the count is 10^4 = 10000, a plain power, not a permutation.

The formulas and the intuition

Start with permutations. You fill k ordered slots from n items, using each item at most once.

P(n,k) = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdots (n-k+1)

Here n is the pool size and k is the number of slots. The first slot has n choices, the next n-1, and so on for k factors. With n=10, k=4 that is 10 \cdot 9 \cdot 8 \cdot 7 = 5040.

Combinations remove the ordering. Every unordered selection of k items can be ordered in k! ways, so you divide.

\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!\,(n-k)!}

For n=10, k=4 you get 5040 / 24 = 210. The symmetry \binom{n}{k} = \binom{n}{n-k} holds, so \binom{10}{4} = \binom{10}{6} = 210.

Stirling numbers of the second kind follow a recurrence. To partition n items into k groups, look at the last item. Either it sits alone in its own group (leaving S(n-1,k-1) ways for the rest) or it joins one of the existing k groups (giving k \cdot S(n-1,k) ways).

S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)

The unsigned Stirling numbers of the first kind use a parallel recurrence, where the new item either starts its own cycle or is inserted after any of the previous n-1 items:

c(n,k) = (n-1) \cdot c(n-1,k) + c(n-1,k-1)

Worked example: S(10, 4) from the demo

Load the demo values mode = stirling2, n = 10, k = 4 and press Calculate. The result is 34105. Here is how the recurrence builds it, column by column.

Base cases: S(n,1) = 1 for any n \ge 1, and S(n,n) = 1.
Build small values. S(4,4)=1, S(5,4) = 4 \cdot 1 + 1 = 5.
S(6,4) = 4 \cdot 5 + S(5,3) = 20 + 25 = 65.
S(7,4) = 4 \cdot 65 + S(6,3) = 260 + 90 = 350.
S(8,4) = 4 \cdot 350 + S(7,3) = 1400 + 301 = 1701.
S(9,4) = 4 \cdot 1701 + S(8,3) = 6804 + 966 = 7770.
S(10,4) = 4 \cdot 7770 + S(9,3) = 31080 + 3025 = 34105.

So 10 labeled items split into exactly 4 unlabeled nonempty groups in 34105 ways. The intermediate values S(9,3)=3025 and S(8,3)=966 come from the same recurrence run one column to the left.

Reading the results

Every result here is an exact integer, never a rounded float. Counts grow fast. Permutations P(n,k) and factorials outpace combinations because they do not divide out the k! overcount.

Partitions of 10 items into k groups peak at k = 5 with 42525, and the ten bars total 115975, the Bell number B_10.

For combinations, the row \binom{10}{k} is symmetric and peaks in the middle. The values are 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, and they sum to 2^{10} = 1024.

The row is symmetric about k = 5 (value 252) and sums to 1024.

Common mistakes

Mixing up order. If two answers to the same problem differ by a factor of k!, you have confused a permutation with a combination. For n=10, k=4 the ratio is 5040/210 = 24 = 4!.

Watch the edge cases. By convention \binom{n}{0} = 1 and 0! = 1, so choosing nothing counts as one way (the empty selection). If k \gt n, then \binom{n}{k} = 0 and P(n,k) = 0: you cannot pick 5 distinct items from 3.

For the two kinds of Stirling number, do not swap them. Second-kind counts set partitions (groups have no internal order), first-kind counts cycle structures in permutations. At n=4, k=2 the second kind gives 7 while the unsigned first kind gives 11.

Finally, remember that Stirling groups are unlabeled. If the 4 groups were distinct boxes with names, the count of 10 items into 4 nonempty named boxes would be 4! \cdot S(10,4) = 24 \cdot 34105 = 818520, not 34105.

How the values connect

These four counts are not separate islands. Three identities tie them together and give you a way to check results.

The binomial row sums to a power of two: \sum_{k=0}^{n}\binom{n}{k} = 2^n. For n=10 that is 1024.

The Bell number sums a Stirling row: B_n = \sum_{k=1}^{n} S(n,k). For n=10, adding the ten values in the first chart gives 115975.

The first-kind numbers sum to a factorial, because every permutation has some number of cycles: \sum_{k=1}^{n} c(n,k) = n!. For n=4 the row 6, 11, 6, 1 sums to 24 = 4!.

Related calculators

Combinatorial answers grow past the range of ordinary floating point. When you need the exact digits of a large factorial or a huge binomial, use the Big Number Calculator, which supports fact() and exact powers. To display a count in scientific notation or round it to a few significant figures, see Scientific Notation and Significant Figures. If your problem involves divisibility or modular arithmetic on these counts, the Prime Factorization and Number Theory tool covers GCD, LCM and modular reduction.

Frequently asked questions

What is the difference between nCr and nPr?

Both draw k distinct items from n. nPr counts ordered arrangements, nCr counts unordered selections. They differ by a factor of k!. With n=10, k=4, nPr is 5040 and nCr is 210.

Why is 0! equal to 1?

There is exactly one arrangement of an empty set, the empty arrangement. Defining 0! = 1 keeps formulas like \binom{n}{n} = \frac{n!}{n!\,0!} = 1 correct.

Which Stirling number should I use?

If you are splitting labeled items into unlabeled groups, use the second kind. If you are counting how many permutations have a given number of cycles, use the first kind. They give different answers, for example 7 versus 11 at n=4, k=2.

What is a Bell number in plain terms?

It is the number of ways to partition a set of n items into any number of nonempty groups. B_3 = 5 and B_{10} = 115975. It equals the sum of the second-kind Stirling numbers for that n.

Can these counts handle repetition?

Not directly. The modes here treat items as distinct and used at most once. For selections with repetition allowed the count is \binom{n+k-1}{k}, which you can get by entering n+k-1 and k in combinations mode.

Try it yourself in the tool