Journal of Integer Sequences, Vol. 19 (2016), Article 16.4.7 |

Département de Mathématiques et de Statistique

Université Laval

Qué bec

Canada

Patrick Desrosiers

Centre de Recherche de L'Institut

Universitaire en Santé Mentale de Québec

and

Département de Physique, de Génie Physique et d'Optique

Université Laval

Québec

Canada

Simon Hardy

Centre de Recherche de L'Institut

Universitaire en Santé Mentale de Québec

and

Département de Biochimie, Microbiologie et Bio-Informatique

and

Département d'Informatique et de Génie Logiciel

Université Laval

Québec

Canada

Nicolas Doyon

Département de Mathématiques et de Statistique

Université Laval

and

Centre de Recherche de L'Institut Universitaire en Santé
Mentale de Québec

Québec

Canada

**Abstract:**

We apply combinatorial tools, including Pólya's theorem, to
enumerate all possible networks for which (1) the network contains
distinguishable input and output nodes as well as partially
distinguishable intermediate nodes; (2) all connections are directed
and for each pair of nodes, there are at most two connections, that is,
at most one connection per direction; (3) input nodes send connections
but don't receive any, while output nodes receive connections but don't
send any; (4) every intermediate node receives a path from an input
node and sends a path to at least one output node; and (5) input nodes don't
send direct connections to output nodes. We first obtain the generating
function for the number of such networks, and then use it to obtain
precise estimates for the number of networks. Finally, we develop a
computer algorithm that allows us to generate these networks. This work
could become useful in the field of neuroscience, in which the problem of
deciphering the structure of hidden networks is of the utmost
importance, since there are several instances in which the activity of
input and output neurons can be directly measured, while no direct
access to the intermediate network is possible. Our results can also be
used to count the number of finite automata in which each cell plays a
relevant role.

Received
December 8 2015; revised versions received March 3 2016; April 8 2016.
Published in *Journal of Integer Sequences*, May 10 2016.

Return to