Counting Insights Vol 1.0 K-to-1 Functions

Let us ask ourselves a basic question: How do we count ?
Suppose we have a collection of items. We assign to each item a number from $\mathbb{N}$ in increasing order (of course starting from 1, then 2, then 3 and so on). The last number assigned is the value of the count (final answer).
Notice that we can not assign the same number from $\mathbb{N}$ to two different items. Thus, if we consider our assignment policy as a mapping from the set of items to $\mathbb{N}$, then it is injective in nature. Thus, we can conclude:

When we count the number of elements in a set S, we are essentially establishing an injection from set S to $\mathbb{N}$.

So, when confronted with the questions like: “how many of the students in your class share birthday (day in week) with Ramesh?”, we can be certain that this counting needs an injective map from some set to $\mathbb{N}$. What that set is, how to arrive at this mapping? - before being able to answer these questions, we need to transform the problem into mathematical equations/sets. Let us analyze.

Let D = set of all days in a week and S = set of all students in the class.
Suppose $\exists$ a surjective map $bday: S \to D$.
With these pieces of information, we can now phrase the question as: “How many students $s \in S$ have the same value as bday(Ramesh), where Ramesh $\in S$ is a known student in the class”. More formally,
what is the cardinality of the set
$$A=\{x\in S: bday(x) = bday(Ramesh)\}$$

---

Now let us ask another simple question. Suppose there are in total 112 pieces of footwears visible outside the temple’s main entrance. Assume that no devotee came barefooted, so there are only two possible kinds of devotees: having 2 legs & having just 1 leg (physically disabled). Then what is the minimum possible count of devotees present in the temple (exclude the priest)?
We know that every devotee has either 2 feet or 1 foot, so for minimum count of devotees, we try to assign maximum number of footwears (=2) to each devotee. Notice however, that this assignment policy is not an injective map. Later we can establish an injection from set of devotees to $\mathbb{N}$ to know the total count.
Let S = set of all footwears lying outside the temple entrance, and
let D = set of all devotees present inside the temple, excluding the priest.
The map $f: S \to D$ is many-to-one, not injective. Reason is that we are assigning “a pair of footwears” to a unique devotee in $D$. Further, $f()$ is surjective because no devotee came to the temple without his/her footwear.
$\implies \left|D\right| \le \left|S\right|$ ($\because$ property of surjection), i.e., count of devotees can not exceed 112 (upper-bound).

The mapping to find minimum number of devotees may not match with actual mapping that exists between footwears and devotees, because there may be some physically disabled persons having just one piece of footwear assigned to them.
Suppose $g: S \to D$ be the actual mapping and is known to us. Clearly it is not injective. In $g$, some pairs of footwears might be assigned to unique devotees in $D$, while, some single pieces of footwears might be assigned to unique physically-disabled devotees in $D$. So actual map $g()$, is mixture of both $2$-to-$1$ mapping and one-one mapping.
But there is one important constraint that we have not yet discussed: No devotee can have more than 2 legs, hence no more than 2 footwears can be assigned to the same devotee in $D$, i.e., at most 2 pieces of footwears can be assigned a unique devotee in $D$. This constraint of at most 2 leads us to conceptualizing a class of functions where not more than $k\in\mathbb{N}$ elements of domain can be assigned to an image in the range.

$k$-to-$1$ Functions

Definition 1. Let $f: A \to B$ be a mapping. Let $k\in\mathbb{N}$. Then f is said to be k-to-1 iff for each $b\in B$, $\exists$ at most $k$ distinct pre-images $a$ such that $f(a)=b$.
In other words, cardinality of the set $f^{-1}(b)$ is at most k $\forall b\in B$, i.e.,
$$\left| \{a\in A: f(a)=b\}\right| \le k\ for\ every\ b\in B.$$
Some Remarks:

• From the definition stated above, $f$ is a $k$-to-$1$ functions, iff $k$ is the upper-bound (maximum) of the cardinalities of pre-images of all the elements in co-domain, under the mapping $f$.
• If $k$ elements are mapped to a given element, then the function is not $m$-to-$1$ for any $m < k$. For example, if under $f$, there exists some $b$, such that $\left|f^{-1}(b)\right| = 3$, then $f$ can neither be $2$-to-$1$ nor $1$-to-$1$.
• Setting $k=1$ gives us the injective (one-one) class of functions, where every $b\in B$ can have at most $1$ pre-image. Thus, the concept of $k$-to-$1$ functions is an extension of injective functions to a more generalized setting.
  

Written with StackEdit.