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

A. V. Zharkova

Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 63-73

Résumé

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.

Détail

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