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

1, 2, 5, 13, 35, 93, 260

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 j-back inverse applied to the i-th domain element of X.

Links

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

Bradford M. Fournier-Eaton, A Theory of Preimage Complexity: Data-structures, Complexity Measures and Applications to Endofunctions and Associated Digraphs, (2020), University of New Orleans Theses and Dissertations.

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 * A367656 A240609 A054657

Adjacent sequences: A335722 A335723 A335724 * A335726 A335727 A335728

Keyword

nonn,hard,more

Author

Bradford M. Fournier-Eaton, Jun 19 2020

Status

approved