- FindStat

Identifier

St001722: Binary words ⟶ ℤ

Values

0 => 1

1 => 1

00 => 1

01 => 1

10 => 1

11 => 1

000 => 1

001 => 1

010 => 1

011 => 1

100 => 1

101 => 1

110 => 1

111 => 1

0000 => 1

0001 => 1

0010 => 1

0011 => 1

0100 => 2

0101 => 1

0110 => 2

0111 => 1

1000 => 1

1001 => 1

1010 => 1

1011 => 1

1100 => 1

1101 => 1

1110 => 1

1111 => 1

00000 => 1

00001 => 1

00010 => 1

00011 => 1

00100 => 3

00101 => 1

00110 => 2

00111 => 1

01000 => 3

01001 => 2

01010 => 1

01011 => 1

01100 => 1

01101 => 3

01110 => 3

01111 => 1

10000 => 1

10001 => 1

10010 => 1

10011 => 1

10100 => 2

10101 => 1

10110 => 2

10111 => 1

11000 => 1

11001 => 1

11010 => 1

11011 => 1

11100 => 1

11101 => 1

11110 => 1

11111 => 1

000000 => 1

000001 => 1

000010 => 1

000011 => 1

000100 => 4

000101 => 1

000110 => 2

000111 => 1

001000 => 6

001001 => 3

001010 => 1

001011 => 1

001100 => 1

001101 => 3

001110 => 3

001111 => 1

010000 => 4

010001 => 3

010010 => 2

010011 => 2

010100 => 5

010101 => 1

010110 => 2

010111 => 1

011000 => 3

011001 => 1

011010 => 6

011011 => 4

011100 => 4

011101 => 6

011110 => 4

011111 => 1

100000 => 1

100001 => 1

100010 => 1

100011 => 1

100100 => 3

100101 => 1

100110 => 2

>>> Load all 126 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The number of minimal chains with small intervals between a binary word and the top element.
A valley in a binary word is a subsequence $01$, or a trailing $0$. A peak is a subsequence $10$ or a trailing $1$. Let $P$ be the lattice on binary words of length $n$, where the covering elements of a word are obtained by replacing a valley with a peak. An interval $[w_1, w_2]$ in $P$ is small if $w_2$ is obtained from $w_1$ by replacing some valleys with peaks.
This statistic counts the number of chains $w = w_1 < \dots < w_d = 1\dots 1$ to the top element of minimal length.
For example, there are two such chains for the word $0110$:
$$ 0110 < 1011 < 1101 < 1110 < 1111 $$
and
$$ 0110 < 1010 < 1101 < 1110 < 1111. $$

References

[1] Tasoulas, I., Manes, K., Sapounakis, A., Tsikouras, P. Chains with small intervals in the lattice of binary paths MathSciNet:4054761

Code

def filling(w):
    """
    Return the join of all elements covering w.

    This is obtained by replacing every valley with a peak.
    """
    w = list(w)
    f = list(w)
    for i in range(len(w)-1):
        if w[i:i+2] == [0, 1]:
            f[i:i+2] = [1, 0]
    if w[len(w)-1] == 0:
        f[len(w)-1] = 1
    return Words([0,1])(f)

def degree(w):
    d = 0
    while w.count(0):
        w = filling(w)
        d += 1
    return d

def path_smaller(a, b):
    assert len(a) == len(b)
    return all(sum(a[:i]) <= sum(b[:i]) for i in range(1, len(a)+1))

@cached_function
def path_smaller_poset(n):
    return Poset([Words([0,1], length=n), path_smaller])

def statistic(w):
    """
    See MathSciNet:4054761, Prop. 6.
    """
    n = len(w)
    w = Words([0,1], n)(w)
    P = path_smaller_poset(n)
    I = P.incidence_algebra(QQ)
    mu = I.moebius()
    return abs(ZZ((mu^degree(w))(P(w), P.top())))

Created

May 23, 2021 at 17:08 by Martin Rubey

Updated

Dec 28, 2023 at 17:02 by Martin Rubey