edit this statistic or download as text // json
Identifier
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 100111=>1 101000=>3 101001=>2 101010=>1 101011=>1 101100=>1 101101=>3 101110=>3 101111=>1 110000=>1 110001=>1 110010=>1 110011=>1 110100=>2 110101=>1 110110=>2 110111=>1 111000=>1 111001=>1 111010=>1 111011=>1 111100=>1 111101=>1 111110=>1 111111=>1
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