|
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.
Citation:
A. V. Zharkova, “Number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations”, Prikl. Diskr. Mat., 2015, no. 3(29), 63–73
Linking options:
https://www.mathnet.ru/eng/pdm519 https://www.mathnet.ru/eng/pdm/y2015/i3/p63
|
|