EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 4, 2023, 2751-2762 ISSN 1307-5543 – ejpam.com Published by New York Business Global On the Number of Restricted One-to-One and Onto Functions Having Integral Coordinates Mary Joy R. Latayada Department of Mathematics, Caraga State University, 8600 Butuan City, Philippines Abstract. Let Nm be the set of positive integers 1, 2, , · · · ,m and S ⊆ Nm. In 2000, J. Caumeran and R. Corcino made a thorough investigation on counting restricted functions f|S under each of the following conditions: (a) f(a) ≤ a, ∀a ∈ S; (b) f(a) ≤ g(a), ∀a ∈ S where g is any nonnegative real-valued continuous functions; (c) g1(a) ≤ f(a) ≤ g2(a), ∀a ∈ S, where g1 and g2 are any nonnegative real-valued continuous functions. Several formulae and identities were also obtain by Caumeran using basic concepts in combina- torics. In this paper we count those restricted functions under condition f(a) ≤ a, ∀a ∈ S which is one-to-one and onto and establish some formulas and identities parallel to those obtained by J. Caumeran and R. Corcino. 2020 Mathematics Subject Classifications: 11B34, 11B73, 11B37, 05A10 Key Words and Phrases: Restricted function, one-to-one function, onto function, Stirling num- bers of the second kind, restricted onto function, recurrence relation 1. Introduction Cantor [12] is the first to consider the study of counting functions when he attempted to give meaning to power of cardinal numbers. Cantor obtained that the number of possible functions from an m-set to an n-set is equal to nm in which (n)m = n(n − 1)(n− 2) . . . (n−m+ 1) of these are one-to-one functions.Stirling number of the first and second kind was first introduced by James Stirling published in 1730 in his book Methodes Differentials. The Stirling numbers of the second kind S(n,m) count the number of ways of partitioning a set containing n elements into m nonempty subsets. By making use of the classical Stirling numbers of the second kind S(n, k), it is shown that the number of onto functions is n!S(m,n) (see [3]). The Stirling numbers of the second kind satisfy the following recurrence relations and explicit formula: DOI: https://doi.org/10.29020/nybg.ejpam.v16i4.4901 Email address: mrlatayada@carsu.edu.ph(M. J. Latayada) https://www.ejpam.com 2751 © 2023 EJPAM All rights reserved. M. J. Latayada / Eur. J. Pure Appl. Math, 16 (4) (2023), 2751-2762 2752 (i) S(n, k) = S(n− 1, k − 1) + kS(n− 1, k), n, k ≥ 1. S(n, 0) = S(0, k) = 0 except S(0, 0) = 1.n, k ≥ 1. (ii) S(n, k) = 1 k! k∑ j=0 (−1)j ( k j ) (k − j)n = 1 k! k∑ i=0 (−1)k−i ( k i ) (i)n. Using these identities, we can easily construct the following table of values of S(n, k): @ @ @n k 0 1 2 3 4 5 6 0 0 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 Table 1: Values of S(n, k) for 0 ≤ n ≤ 6 The Stirling numbers of the second kind has been generalized by introducing two parameters r and β. These generalized numbers are referred to as (r, β)− Stirling numbers, denoted by Sr,β(n, k). They were introduced by R. Corcino [6] as coefficient of the explicit formula: Sr,β(n, k) = 1 βk! k∑ j=0 (−1)k−j ( k j ) (βj + r)n. In [2], it was obtained that the number of restricted functions f |S : Nm −→ Nn for all S ⊆ Nm where Nm = {1, 2, . . . ,m} is equal to (n+ 1)m. R. Corcino et al. [7] established some formulas in counting restricted functions f |S : Nm −→ N , S ⊆ Nm under each of the following conditions: (i) f(a) ≤ a, ∀a ∈ S; (ii) f(a) ≤ g(a), ∀a ∈ S where g is any nonnegative real-valued continuous functions; (iii) g1(a) ≤ f(a) ≤ g2(a), ∀a ∈ S, where g1 and g2 are any nonnegative real-valued continuous functions. In this paper, we count those restricted functions considered by Caumeran [2] under condition (i) which is one-to-one and also onto. It is known that the number of one-to-one M. J. Latayada / Eur. J. Pure Appl. Math, 16 (4) (2023), 2751-2762 2753 functions that can be formed from A to B where |A| = n and |B| = m is equal to m(m− 1)(m− 2) · · · (m− n+ 1). On the other hand, the number of onto functions f |S : Nn −→ Nm that can be formed is m! ·S(n,m), where Nn = {1, 2, 3, · · · , n} and S(n,m), denotes the Stirling numbers of the second kind satisfying the relation xn = m∑ i=0 S(n, i)(x)i, where (x)i = x(x − 1(x − 2) · · · (x − i + 1). It is observed that the process of counting onto functions makes use of the multiplication principle and the appropriate application of Stirling numbers of the second kind. The process of obtaining one-to-one and onto functions may be applicable in counting restricted one-to-one and onto functions. Recall that, for a finite sets A and B, a function f : A −→ B is said to be onto if f(A) = B. Hence, in order for the function f to be onto, |A| must be greater than or equal to |B|. 2. Number of Restricted One-to-One Functions Let Si be a subset of Nm and |Si| = i. The number of restricted one-to-one functions f |S : Nm −→ Nn for all S ⊆ Nm is n(n− 1)(n− 2) . . . (n− (i− 1)) = (n)i. Let Îm = ⋃m i=0 Îi,m. Then Îm = ⋃ Si⊆Nm {f |Si : f is a one-to-one function}. The number of subsets of Nm containing i elements is ( m i ) and |Îm| = m∑ i=0 ∣∣Î(n)i,m ∣∣ = m∑ i=0 ∣∣∣∣ ⋃ Si⊆Nm {f |Si : f is a one-to-one function} ∣∣∣∣ implying that |Îm| = m∑ i=0 ( m i ) (n)i. To state this result formally, we have the following proposition. Proposition 1. Let f |S : Nm −→ Nn such that m ≤ n. If Îm = ⋃m i=0 Ŷi,m where Îm = {f |Si : Si ⊆ Nm and f is a one-to-one function} , then |Îm| = m∑ i=0 ( m i ) (n)i. M. J. Latayada / Eur. J. Pure Appl. Math, 16 (4) (2023), 2751-2762 2754 Example 1. If m = 3 and n = 4 we have N3 = 1, 2, 3 and N4 = 1, 2, 3, 4. For i = 0, S0 = {} , f |S0 = {} is the only one-to-one function. For i = 1, Si = {1}, {2}, {3}, the one-to-one functions are {(1, 1)} {(1, 2)} {(1, 3)} {(1, 4)} {(2, 1)} {(2, 2)} {(2, 3)} {(2, 4)} {(3, 1)} {(3, 2)} {(3, 3)} {(3, 4)} For i = 2, Si = {1, 2}, {1, 3}, {2, 3}, the one-to-one functions are {(1, 1), (2, 2)} {(1, 2), (2, 1)} {(1, 3), (2, 1)} {(1, 4), (2, 1)} {(1, 1), (2, 3)} {(1, 2), (2, 3)} {(1, 3), (2, 2)} {(1, 4), (2, 2)} {(1, 1), (2, 4)} {(1, 2), (2, 4)} {(1, 3), (2, 4)} {(1, 4), (2, 3)} {(1, 1), (3, 2)} {(1, 2), (3, 1)} {(1, 3), (3, 1)} {(1, 4), (3, 1)} {(1, 1), (3, 3)} {(1, 2), (3, 3)} {(1, 3), (3, 2)} {(1, 4), (3, 2)} {(1, 1), (3, 4)} {(1, 2), (3, 4)} {(1, 3), (3, 4)} {(1, 4), (3, 3)} {(2, 1), (3, 2)} {(2, 2), (3, 1)} {(2, 3), (3, 1)} {(2, 4), (3, 1)} {(2, 1), (3, 3)} {(2, 2), (3, 3)} {(2, 3), (3, 2)} {(2, 4), (3, 2)} {(2, 1), (3, 4)} {(2, 2), (3, 4)} {(3, 3), (3, 4)} {(2, 4), (3, 3)} For i = 3, Si = {1, 2, 3}, {1, 3}, {2, 3}, the one-to-one functions are {(1, 1), (2, 2), (3, 3)} {(1, 2), (2, 1), (3, 3)} {(1, 3), (2, 1), (3, 2)} {(1, 4), (2, 1), (3, 2)} {(1, 1), (2, 2), (3, 4)} {(1, 2), (2, 1), (3, 4)} {(1, 3), (2, 1), (3, 4)} {(1, 4), (2, 1), (3, 3)} {(1, 1), (2, 3), (3, 4)} {(1, 2), (2, 3), (3, 1)} {(1, 3), (2, 2), (3, 1)} {(1, 4), (2, 2), (3, 1)} {(1, 1), (2, 3), (3, 2)} {(1, 2), (2, 3), (3, 4)} {(1, 3), (2, 2), (3, 4)} {(1, 4), (2, 2), (3, 3)} {(1, 1), (2, 4), (3, 2)} {(1, 2), (2, 4), (3, 3)} {(1, 3), (2, 4), (3, 1)} {(1, 4), (2, 3), (3, 1)} {(1, 1), (2, 4), (3, 3)} {(1, 2), (2, 4), (3, 4)} {(1, 3), (2, 4), (3, 2)} {(1, 4), (2, 3), (3, 2)} Thus, the total number of restricted one-to-one function is 73. Using Proposition 1, with m = 3 and n = 4, we have |Î3| = 3∑ i=0 ( 3 i ) (4)i = ( 3 0 ) (4)0 + ( 3 1 ) (4)1 + ( 3 2 ) (4)2 + ( 3 3 ) (4)3 = 1 + 3(4) + 3(4)(3) + 1(4)(3)(2) = 73. The next proposition counts the number of restricted one-to-one functions f with the condition that f(a) ≤ a,∀a ∈ S. Proposition 2. Let f |S : Nm −→ Nn such that m ≤ n and f(a) ≤ a,∀a ∈ S. If Ŷ(i,m) = ∣∣⋃{f |Si : f is one to one and |Si| = i} ∣∣,then |Ŷ (i,m)| = ∑ 1≤j1 m and Ŷ (i,m) = 0 when i > 0. Proof. We know that Ŷ (i,m+1) counts the number of restricted one-to-one functions f |Si overall Si ⊆ Nm+1. Forming such restricted one-to-one functions can also be done by considering the following disjoint cases: Case 1. Forming those functions f |Si overall Si ⊆ Nm+1 such that m+ 1 /∈ Si. Then the number of such restricted one-to-one functions is equal to the number of restricted one- to-one functions f |Si overall Si ⊆ Nm+1. By definition, there are Ŷ (i,m) such functions. Case 2. Forming those functions f |Si overall Si ⊆ Nm+1 such that m + 1 /∈ Si. This event can be decomposed into the following sequence of events: E1 : Event of forming those restricted one-to-one functions f |Si−1 overall Si−1 ⊆ Nm. E2 : Event of inserting m+ 1 to Si−1 so that every Si = Si−1 ∪ {m+ 1} contains m+ 1 and then mapping m+ 1 to Nm+1 so that one-to-oneness of f will be preserved. Note that |E1| = Ŷ (i− 1,m) and |E2| = m+ 1− (i− 1). By Multiplication Principle, the number of such restricted one-to-one functions f |Si = f |Si−1∪{m+1} overall Si ⊆ Nm+1 is equal to |E1||E2| = Ŷ (i− 1,m)(m+ 2− i). Since any of these cases gives the desired restricted one-to-one functions, by Addition Principle, Ŷ (i,m+ 1) = Ŷ (i,m) + (m+ 2− i)Ŷ (i− 1,m). Example 3. From Example 2, Ŷ (2, 3) = 7 and using Proposition 3, Ŷ (1, 3) = 3∑ ji=1 ji = 1 + 2 + 3 = 6. Then, by applying Proposition 3, with i = 2,m = 3, we have Ŷ (2, 4) = Ŷ (2, 3) + (3 + 2− 2)Ŷ (1, 3). = 7 + 3(6) = 25. Using Proposition 2, we have Ŷ (2, 4) = ∑ 1≤j1≤j2≤3 j1(j2 − 1)) = 1(2− 1) + 1(3− 1) + 1(4− 1) + 2(3− 1) + 2(4− 1) + 3(4− 1) = 25. M. J. Latayada / Eur. J. Pure Appl. Math, 16 (4) (2023), 2751-2762 2757 Note that Ŷ (0, 1) = Ŷ (0, 1) + (0 + 2− 0)Ŷ (−1, 0) = 1 Ŷ (1, 1) = Ŷ (1, 0) + (0 + 2− 1)Ŷ (0, 0) = 1 Ŷ (1, 2) = Ŷ (0, 1) + (1 + 2− 0)Ŷ (−1, 1) = 1 Ŷ (1, 2) = Ŷ (0, 1) + (1 + 2− 0)Ŷ (−1, 1) = 1. The following table of values for Ŷ (i,m) can be constructed using Proposition 3. @ @ @m i 0 1 2 3 4 5 6 0 1 1 1 1 2 1 3 1 3 1 6 7 1 4 1 10 25 15 1 5 1 15 65 90 31 1 6 1 21 140 350 301 63 1 Table 2: Values of Ŷ (i,m) for 0 ≤ i ≤ 6, 0 ≤ m ≤ 6 Remark 1. We know from Proposition 1, that the total number of restricted one-to-one functions f |Si : Nm −→ Nn, ∀S ⊆ Nm is |Îm| = m∑ i=0 ( m i ) (n)i (1) and, from Proposition 2, the number of restricted one-to-one functions f |Si : Nm −→ Nn, ∀Si ⊆ Nm, |Si| = i such that f(a) ≤ a,∀a ∈ Nm is Ŷ (i,m) = ∑ 1≤j1