Number of Functions

Consider the mapping of elements from the domain set $$A = \{1, 2, 3, 4, 5, 6\}$$ to the codomain set $$B = \{1, 2, 3, 4\}$$. We are required to determine the cardinality of the set of all surjective functions $$f: A \to B$$ subject to the explicit restriction that $$f(1) \neq f(2)$$. Let $$S$$ denote the total set of all surjective functions from $$A$$ to $$B$$, and let $$E$$ denote the subset of these surjections where the condition is violated, namely $$f(1) = f(2)$$. The number of valid functions is given by the difference $$\vert S \vert - \vert E \vert$$.

To evaluate the total number of unconstrained surjective functions $$\vert S \vert$$, we apply the Principle of Inclusion-Exclusion. The total number of unrestricted mappings from a 6-element set to a 4-element set is $$4^6$$. We must subtract the functions that omit at least one element of the codomain, add back those that omit at least two elements, and subtract those that omit three elements. This yields the classical summation:

$$\vert S \vert = 4^6 - \binom{4}{1}3^6 + \binom{4}{2}2^6 - \binom{4}{3}1^6$$

Evaluating each term explicitly gives:

$$\vert S \vert = 4096 - 4(729) + 6(64) - 4(1) = 4096 - 2916 + 384 - 4 = 1560$$

We next determine the number of invalid surjections $$\vert E \vert$$ where $$f(1) = f(2)$$. Because the elements 1 and 2 map to the exact same image in the codomain, they behave as a single entity within the domain. This equivalence collapses the effective size of the domain from 6 elements to 5 elements, transforming the problem into finding the number of onto functions from a 5-element set to a 4-element set. Applying the Principle of Inclusion-Exclusion to this modified configuration yields:

$$\vert E \vert = 4^5 - \binom{4}{1}3^5 + \binom{4}{2}2^5 - \binom{4}{3}1^5$$

Evaluating these terms explicitly gives:

$$\vert E \vert = 1024 - 4(243) + 6(32) - 4(1) = 1024 - 972 + 192 - 4 = 240$$

Finally, by subtracting the number of invalid configurations from the total unconstrained surjections, we isolate the exact number of functions that satisfy the original hypothesis:

$$\text{Valid Functions} = \vert S \vert - \vert E \vert = 1560 - 240 = 1320$$