*****************************************************************************
*       www.FindStat.org - The Combinatorial Statistic Finder               *
*                                                                           *
*       Copyright (C) 2019 The FindStatCrew <info@findstat.org>             *
*                                                                           *
*    This information is distributed in the hope that it will be useful,    *
*    but WITHOUT ANY WARRANTY; without even the implied warranty of         *
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                   *
*****************************************************************************

-----------------------------------------------------------------------------
Statistic identifier: St001722

-----------------------------------------------------------------------------
Collection: Binary words

-----------------------------------------------------------------------------
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())))


-----------------------------------------------------------------------------
Statistic 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

-----------------------------------------------------------------------------
Created: May 23, 2021 at 17:08 by Martin Rubey

-----------------------------------------------------------------------------
Last Updated: Dec 28, 2023 at 17:02 by Martin Rubey