The number of distinct cubes in a binary word. A factor of a word is a sequence of consecutive letters. This statistic records the number of distinct non-empty words $u$ such that $uuu$ is a factor of the word.

The genus of a graph. This is the smallest genus of an oriented surface on which the graph can be embedded without crossings. One can indeed compute the genus as the sum of the genuses for the connected components.

The number of rises of length at least 3 of a Dyck path. The number of Dyck paths without such rises are counted by the Motzkin numbers [1].

The Grundy value of Welter's game on a binary word. Two players take turns moving a $1$ to the left. The loosing positions are the words $1\dots 10\dots 0$.

The number of ascents in an integer composition. A composition has an ascent, or rise, at position $i$ if $a_i < a_{i+1}$.

The length of the longest staircase fitting into an integer composition. For a given composition $c_1,\dots,c_n$, this is the maximal number $\ell$ such that there are indices $i_1 < \dots < i_\ell$ with $c_{i_k} \geq k$, see [def.3.1, 1]

The number of strong records in an integer composition. A strong record is an element $a_i$ such that $a_i > a_j$ for all $j < i$. In particular, the first part of a composition is a strong record. Theorem 1.1 of [1] provides the generating function for compositions with parts in a given set according to the sum of the parts, the number of parts and the number of strong records.

The logarithmic height of a Dyck path. This is the floor of the binary logarithm of the usual height increased by one: $$ \lfloor\log_2(1+height(D))\rfloor $$

The number of graphs with the same chromatic polynomial.

The number of graphs with the same symmetric edge polytope as the given graph. The symmetric edge polytope of a graph on $n$ vertices is the polytope in $\mathbb R^n$ defined as the convex hull of $e_i - e_j$ and $e_j - e_i$ for each edge $(i, j)$, where $e_1,\dots, e_n$ denotes the standard basis.