

A335725


The number of sigma matrices on the set of all endofunctions as a function of domain size n.


0




OFFSET

1,2


COMMENTS

The number of unique sigma matrices of endofunctions as a function of n where n is the size of the finite domain. The sigma matrix is an n X n preimage data structure in which an arbitrary entry is given by sigma[i,j] = abs(f(x_{i})^{j}). In other words, given an endofunction on X, the sigma matrix captures the size of the jback inverse applied to the ith domain element of X.


REFERENCES

FournierEaton, Bradford M., "A Theory of Preimage Complexity: Datastructures, Complexity Measures and Applications to Endofunctions and Associated Digraphs" (2020). University of New Orleans Theses and Dissertations. 2794.


LINKS

Table of n, a(n) for n=1..7.


EXAMPLE

A two element domain corresponds to n=2. There are 2^2=4 endofunctions on two elements. However the only unique sigma matrices correspond to S1 = [[2,2],[0,0]] and S2 = [[1,1],[1,1]], and thus sigma(2)=2. See the referenced dissertation at the associated link for a full exposition including examples, definitions and theory.


CROSSREFS

Sequence in context: A291242 A097919 A160438 * A240609 A054657 A024576
Adjacent sequences: A335722 A335723 A335724 * A335726 A335727 A335728


KEYWORD

nonn,hard,more


AUTHOR

Bradford M. FournierEaton, Jun 19 2020


STATUS

approved



