Counting Functions for GATE: One-One, Onto and Bijections, with Every Formula Derived

"How many functions?" questions are straightforward only after you keep the domain and codomain sizes in the correct order. The common error is not difficult arithmetic. It is using n^m for a one-one count or applying a permutation formula to an onto problem.

Set up the function-counting problem

Let A be the domain and B be the codomain:

|A| = m
|B| = n
f: A -> B

A function assigns every one of the m domain elements exactly one image in B. Different domain elements may share an image unless the function is required to be one-one.

Before calculating, write these size tests:

• A one-one function can exist only when m <= n.

• An onto function can exist only when m >= n.

• A bijection between finite sets can exist only when m = n.

These conditions follow from capacity. Distinct images need at least as many codomain elements as domain elements. Covering every codomain element needs at least as many domain elements as codomain elements.

Every count below rests on one rule. When independent choices are made in sequence, multiply the number of options available at each step. What changes from formula to formula is only how many options are still open when each step arrives.

Total functions and one-one functions

For an unrestricted function, each of the m domain elements independently chooses one of n images. Therefore

number of total functions = n^m

For a one-one, or injective, function, the images must remain distinct. The first domain element has n choices, the second has n-1, and so on. If m <= n,

number of one-one functions
= n(n-1)...(n-m+1)
= n!/(n-m)!
= P(n,m)

If m > n, the count is zero.

Take A = {1,2,3} and B = {a,b,c,d}. Here m=3 and n=4.

total = 4^3 = 64
one-one = P(4,3) = 4*3*2 = 24
onto = 0, because 3 inputs cannot cover 4 targets
bijective = 0, because 3 != 4

The difference between 64 and 24 is the difference between allowing repeated images and forbidding them. A mapping such as 1->a, 2->a, 3->b appears among the 64 total functions but not among the 24 injective functions.

Onto functions by inclusion-exclusion

An onto, or surjective, function must use every element of the codomain at least once. Counting direct assignments is awkward because the number of remaining choices depends on which targets have already appeared. Inclusion-exclusion gives a clean count. The same add-subtract pattern, applied to divisibility ranges and derangements, is worked step by step in Pigeonhole Principle and Inclusion-Exclusion for GATE.

Begin with all n^m functions. For each codomain element, define a bad event that the function misses that element. If one specified target is forbidden, all m domain elements map into the remaining n-1 targets, giving (n-1)^m functions.

Subtract the functions missing at least one target, add back those missing at least two because they were subtracted twice, and continue:

onto(m,n) = sum from k=0 to n of
             (-1)^k * C(n,k) * (n-k)^m

This formula applies when m >= n. If m < n, the onto count is zero by the size test.

Take m=4 and n=3:

onto(4,3)
= C(3,0)*3^4 - C(3,1)*2^4 + C(3,2)*1^4 - C(3,3)*0^4
= 1*81 - 3*16 + 3*1 - 1*0
= 81 - 48 + 3
= 36

The four terms have a precise meaning. Start with 81 total functions. Subtract 48 functions that miss a chosen target, with overlaps counted. Add back the 3 constant functions, each of which uses a single target and was therefore subtracted twice in the previous step. The 0^4 term is zero because no element of a non-empty domain can be assigned an image when zero targets remain.

There is an independent check using Stirling numbers of the second kind. S(m,n) partitions the m labelled domain elements into n non-empty unlabeled groups. Assign those groups to the n labelled codomain elements in n! ways:

onto(m,n) = n! * S(m,n)
onto(4,3) = 3! * S(4,3) = 6 * 6 = 36

Both methods give 36.

Bijections and the summary grid

A bijection is both one-one and onto. For finite sets that forces m=n, and once the sizes are equal each property drags the other with it. An injective function on an n-element domain produces n distinct images, and n distinct elements sitting inside an n-element codomain must be the whole codomain, so it is onto. A surjective function has to reach all n targets from n inputs, which leaves no input free to repeat an image, so it is one-one.

Counting them needs no new formula. Put m=n in the injective count. The first domain element has n images available, the second has n-1 once one is used, and the last has exactly one left:

number of bijections
= P(n,n)
= n(n-1)...(2)(1)
= n!/(n-n)! = n!/0!
= n!

For two three-element sets, the count is 3! = 6.

Now compare the two unequal-size examples:

The zeros carry most of the lesson. With four inputs and three targets, distinct images are impossible. With three inputs and four targets, covering every target is impossible. In either unequal-size case, a bijection is impossible.

Traps GATE plants in function counts

Keep the notation line |A|=m, |B|=n visible. Then check for these traps:

• n^m counts all functions, not only one-one functions.

• P(n,m) counts one-one functions, not onto functions.

• Surjections need inclusion-exclusion or n!S(m,n) because every target must be used.

• In the inclusion-exclusion sum, the exponent is the domain size m.

• One-one wants the codomain at least as large; onto wants the domain at least as large.

• When m=n, an injective function, a surjective function and a bijection all have the same count n!.

If the classification itself is still shaky, Functions in Discrete Mathematics sorts injective, surjective and bijective maps with mapping tables before any counting starts, and Set Theory and Relations for GATE separates a relation from a function. About 1,300 Discrete Mathematics questions in the KnowledgeGate question bank put these formulas back into mixed settings.

How GATE tests the formulas

The formulas rarely appear naked. A numerical-answer question hands you two set sizes and one adjective, and the work is deciding which of the four counts that adjective names.

A typical shape: how many onto functions are there from a 5-element set to a 3-element set? The size test comes first, 5 >= 3, so a non-zero answer exists. Then run the sum:

onto(5,3)
= C(3,0)*3^5 - C(3,1)*2^5 + C(3,2)*1^5 - C(3,3)*0^5
= 243 - 3*32 + 3*1 - 0
= 243 - 96 + 3
= 150

Stirling agrees: 3! * S(5,3) = 6 * 25 = 150.

Swap the two sizes and the same sentence becomes a one-line answer. Onto functions from a 3-element set to a 5-element set: 3 < 5 fails the size test, so the count is 0 and there is nothing to compute. Reading the size condition before reaching for a formula is what keeps these questions short.

The other Discrete Mathematics topics that share these counting tools sit in the GATE preparation category, next to the papers they are tested in.

Short version and next step

For |A|=m and |B|=n, total functions are n^m. One-one functions are P(n,m) when m<=n. Onto functions use inclusion-exclusion when m>=n. Bijections are n! when m=n. Otherwise the relevant restricted count is zero.

Practise the size test before touching the arithmetic, then run mixed timed sets in the GATE Test Series until choosing the formula becomes reflexive.