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