I propose below answer.
Answer = 11
What is a bijection from X = {1..5} to Y = {1..5}?
Let's first look at bijections on say (1,2) to (1,2). These are two bijection functions: f1 = {(1,1),(2,2)} and f2 = {(1,2),(2,1)} and Σ = {f1,f2}
Similarly lets look at bijections on say (1,2,3) to (1,2,3). There are six functions:
f1 |
11,22,33 |
f2 |
11,23,32 |
f3 |
12,21,33 |
f4 |
12,23,31 |
f5 |
13,31,22 |
f6 |
13,32,21 |
Here Σ = {f1,f2,f3,f4,f5,f6}
These can be extended to any number of symbols. Bijections from X = {1..n} to Y = {1..n} are n! in number.
So in out case of n=5,
Σ = {f1,f2,f3...f120}
where each f is a set of mappings from {1..5} to {1..5}
What is Σ² ?
It's the cartesian product of sigma and sigma. This means we go from domain for first Σ to range of first sigma, which is the domain of second Σ to the range of the second Σ.
Because domain and range are the same - {1..5}, we note that Σ² is still a set of functions from x ∈ X = {1..5} to some y ∈ Y = {1..5}
What is Σ^n ?
We can extend the above argument for Σ² to any number of compositions.
Because domain and range are still the same - {1..5}, we note that Σ^n is still a composite function from x ∈ {1..5} to some y ∈ {1..5} (with some intermediary domain and ranges (or intermediate states) corresponding to the composing functions)
Questions remaining:
1) What is a string
2) What is the final mapping we are looking for?
What is a string? OR what is actually happening?
Say we understand the above function, how does it relate to a string? The string maps the exact domain and range of the various composing functions.
For instance lets take Σ².
Consider the sample space of Σ² = S
S = {(1,1)->(1,1), (1,1)->(1,2), (1,1)->(1,3), (1,1)->(1,4), (1,1)->(1,5), (1,2)->(2,1), (1,2)->(2,2), (1,2)->(2,3), (1,2)->(2,4), (1,2)->(2,5),(1,3)->(3,1),...(1,5)->(5,1),(1,5)->(5,2),(1,5)->(5,3),(1,5)->(5,4),(1,5)->(5,5)} which can also be written as
S = {(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(1,2,1),(1,2,2),(1,2,3),(1,2,4),(1,2,5),(1,3,1),...(5,5,1),(5,5,2),(5,5,3),(5,5,4),(5,5,5)} respectively
with corresponding strings 111,112,113,114,115,121,122,123,124,125....551,552,553,554,555
Now Σ² corresponds to some subset of all possible functions each of which contain certain number of elements from this sample space. Therefore we can say Σ² is a function that contains some elements from this sample space S.
Moving from functions to finite automata, any DFA we construct is seeing some strings and making transition between states based on string it sees. These strings are composed of the symbols {1..5}. The language accepted by the DFA represents the function.
What is the final mapping we are looking for? OR What is id or identity function?
The identity is some function from X to Y such that x=y where x ∈ X = {1..5} and y ∈ Y = {1..5}.
This means an identity function is eventually composed by any number of intermediary functions such that each element x in the domain maps to the same element y in the range of the aggregate (composed) function.
Say S is a string that represents the above function type. This means that through any number of transitions in between, it has to go from some the initial state x ∈ {1..5} to final state y ∈ {1..5} such that x=y
In other words. S = xabcdef....y
Where:
1) Each of x,a,b,c,d,e,f ...y ∈ {1..5}
2) x = y
What does this mean?
We are looking for strings on {1..5} of any length which start and end with same symbol.
Now, stated this way construction of DFA is much easier.
We have:
one state for start state - call this S
One state for each of the initial transitions call these states A, B, C, D and E
One state for each of the variations - call these A', B', C', D' and E'
So 11 states