Applied Graph Theory

Number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations

A. V. Zharkova

Saratov State University, Saratov, Russia

Abstract: Finite dynamic systems of binary vectors associated with palms orientations are considered. A palm is a tree which is a union of paths having a common end vertex and all these paths, except perhaps one, have the length 1. States of a dynamic system ($P_{s+c}$, $\gamma$), $s>0$, $c>1$, are all possible orientations of a palm with trunk length $s$ and leafs number $c$, and evolutionary function $\gamma$ transforms the given palm orientations by reversing all arcs that enter into sinks. The following formula for the number of inaccessible states in the considered dynamic systems is proved: $2^{s+c}-2^s-2^{s-3}+\Omega(-1)-2\Omega(1)+\Omega(3)$, where $\Omega(x)=\sum_{i = 1}^{\left[(s - x)/4\right]}(-1)^{i+1}\cdot2^{s-x-4i}\cdot C^i_{s-x-3i}$. As a corollary, the number of accessible states equals $2^s+2^{s-3}-\Omega(-1)+2\Omega(1)-\Omega(3)$. The corresponding statistical tables for systems with different parameters $s$ and $c$ are given.

Keywords: finite dynamic system, inaccessible state, palm, starlike tree.

UDC: 519.1

DOI: 10.17223/20710410/29/5

Bibliographic databases:

•