***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * 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: St001365 ----------------------------------------------------------------------------- Collection: Binary words ----------------------------------------------------------------------------- Description: The number of lattice paths of the same length weakly above the path given by a binary word. In particular, there are $2^n$ lattice paths weakly above the the length $n$ binary word $0\dots 0$, there is a unique path weakly above $1\dots 1$, and there are $\binom{2n}{n}$ paths weakly above the length $2n$ binary word $10\dots 10$. ----------------------------------------------------------------------------- References: ----------------------------------------------------------------------------- Code: @cached_function def all_paths_above(L, i=0): if i < 0: return [] elif len(L) == 0: return [tuple()] else: steps = [] if L[0] == 1: steps.append((1,i)) steps.append((0,i-1)) if L[0] == 0: steps.append((1,i+1)) steps.append((0,i)) return [ tuple([a]) + path for a,i in steps for path in all_paths_above(L[1:],i)] def statistic(D): return len(all_paths_above(tuple(D))) ----------------------------------------------------------------------------- Statistic values: 0 => 2 1 => 1 00 => 4 01 => 3 10 => 2 11 => 1 000 => 8 001 => 7 010 => 6 011 => 4 100 => 4 101 => 3 110 => 2 111 => 1 0000 => 16 0001 => 15 0010 => 14 0011 => 11 0100 => 12 0101 => 10 0110 => 8 0111 => 5 1000 => 8 1001 => 7 1010 => 6 1011 => 4 1100 => 4 1101 => 3 1110 => 2 1111 => 1 00000 => 32 00001 => 31 00010 => 30 00011 => 26 00100 => 28 00101 => 25 00110 => 22 00111 => 16 01000 => 24 01001 => 22 01010 => 20 01011 => 15 01100 => 16 01101 => 13 01110 => 10 01111 => 6 10000 => 16 10001 => 15 10010 => 14 10011 => 11 10100 => 12 10101 => 10 10110 => 8 10111 => 5 11000 => 8 11001 => 7 11010 => 6 11011 => 4 11100 => 4 11101 => 3 11110 => 2 11111 => 1 000000 => 64 000001 => 63 000010 => 62 000011 => 57 000100 => 60 000101 => 56 000110 => 52 000111 => 42 001000 => 56 001001 => 53 001010 => 50 001011 => 41 001100 => 44 001101 => 38 001110 => 32 001111 => 22 010000 => 48 010001 => 46 010010 => 44 010011 => 37 010100 => 40 010101 => 35 010110 => 30 010111 => 21 011000 => 32 011001 => 29 011010 => 26 011011 => 19 011100 => 20 011101 => 16 011110 => 12 011111 => 7 100000 => 32 100001 => 31 100010 => 30 100011 => 26 100100 => 28 100101 => 25 100110 => 22 100111 => 16 101000 => 24 101001 => 22 101010 => 20 101011 => 15 101100 => 16 101101 => 13 101110 => 10 101111 => 6 110000 => 16 110001 => 15 110010 => 14 110011 => 11 110100 => 12 110101 => 10 110110 => 8 110111 => 5 111000 => 8 111001 => 7 111010 => 6 111011 => 4 111100 => 4 111101 => 3 111110 => 2 111111 => 1 0000000 => 128 0000001 => 127 0000010 => 126 0000011 => 120 0000100 => 124 0000101 => 119 0000110 => 114 0000111 => 99 0001000 => 120 0001001 => 116 0001010 => 112 0001011 => 98 0001100 => 104 0001101 => 94 0001110 => 84 0001111 => 64 0010000 => 112 0010001 => 109 0010010 => 106 0010011 => 94 0010100 => 100 0010101 => 91 0010110 => 82 0010111 => 63 0011000 => 88 0011001 => 82 0011010 => 76 0011011 => 60 0011100 => 64 0011101 => 54 0011110 => 44 0011111 => 29 0100000 => 96 0100001 => 94 0100010 => 92 0100011 => 83 0100100 => 88 0100101 => 81 0100110 => 74 0100111 => 58 0101000 => 80 0101001 => 75 0101010 => 70 0101011 => 56 0101100 => 60 0101101 => 51 0101110 => 42 0101111 => 28 0110000 => 64 0110001 => 61 0110010 => 58 0110011 => 48 0110100 => 52 0110101 => 45 0110110 => 38 0110111 => 26 0111000 => 40 0111001 => 36 0111010 => 32 0111011 => 23 0111100 => 24 0111101 => 19 0111110 => 14 0111111 => 8 1000000 => 64 1000001 => 63 1000010 => 62 1000011 => 57 1000100 => 60 1000101 => 56 1000110 => 52 1000111 => 42 1001000 => 56 1001001 => 53 1001010 => 50 1001011 => 41 1001100 => 44 1001101 => 38 1001110 => 32 1001111 => 22 1010000 => 48 1010001 => 46 1010010 => 44 1010011 => 37 1010100 => 40 1010101 => 35 1010110 => 30 1010111 => 21 1011000 => 32 1011001 => 29 1011010 => 26 1011011 => 19 1011100 => 20 1011101 => 16 1011110 => 12 1011111 => 7 1100000 => 32 1100001 => 31 1100010 => 30 1100011 => 26 1100100 => 28 1100101 => 25 1100110 => 22 1100111 => 16 1101000 => 24 1101001 => 22 1101010 => 20 1101011 => 15 1101100 => 16 1101101 => 13 1101110 => 10 1101111 => 6 1110000 => 16 1110001 => 15 1110010 => 14 1110011 => 11 1110100 => 12 1110101 => 10 1110110 => 8 1110111 => 5 1111000 => 8 1111001 => 7 1111010 => 6 1111011 => 4 1111100 => 4 1111101 => 3 1111110 => 2 1111111 => 1 00000000 => 256 00000001 => 255 00000010 => 254 00000011 => 247 00000100 => 252 00000101 => 246 00000110 => 240 00000111 => 219 00001000 => 248 00001001 => 243 00001010 => 238 00001011 => 218 00001100 => 228 00001101 => 213 00001110 => 198 00001111 => 163 00010000 => 240 00010001 => 236 00010010 => 232 00010011 => 214 00010100 => 224 00010101 => 210 00010110 => 196 00010111 => 162 00011000 => 208 00011001 => 198 00011010 => 188 00011011 => 158 00011100 => 168 00011101 => 148 00011110 => 128 00011111 => 93 00100000 => 224 00100001 => 221 00100010 => 218 00100011 => 203 00100100 => 212 00100101 => 200 00100110 => 188 00100111 => 157 00101000 => 200 00101001 => 191 00101010 => 182 00101011 => 154 00101100 => 164 00101101 => 145 00101110 => 126 00101111 => 92 00110000 => 176 00110001 => 170 00110010 => 164 00110011 => 142 00110100 => 152 00110101 => 136 00110110 => 120 00110111 => 89 00111000 => 128 00111001 => 118 00111010 => 108 00111011 => 83 00111100 => 88 00111101 => 73 00111110 => 58 00111111 => 37 01000000 => 192 01000001 => 190 01000010 => 188 01000011 => 177 01000100 => 184 01000101 => 175 01000110 => 166 01000111 => 141 01001000 => 176 01001001 => 169 01001010 => 162 01001011 => 139 01001100 => 148 01001101 => 132 01001110 => 116 01001111 => 86 01010000 => 160 01010001 => 155 01010010 => 150 01010011 => 131 01010100 => 140 01010101 => 126 01010110 => 112 01010111 => 84 01011000 => 120 01011001 => 111 01011010 => 102 01011011 => 79 01011100 => 84 01011101 => 70 01011110 => 56 01011111 => 36 01100000 => 128 01100001 => 125 01100010 => 122 01100011 => 109 01100100 => 116 01100101 => 106 01100110 => 96 01100111 => 74 01101000 => 104 01101001 => 97 01101010 => 90 01101011 => 71 01101100 => 76 01101101 => 64 01101110 => 52 01101111 => 34 01110000 => 80 01110001 => 76 01110010 => 72 01110011 => 59 01110100 => 64 01110101 => 55 01110110 => 46 01110111 => 31 01111000 => 48 01111001 => 43 01111010 => 38 01111011 => 27 01111100 => 28 01111101 => 22 01111110 => 16 01111111 => 9 10000000 => 128 10000001 => 127 10000010 => 126 10000011 => 120 10000100 => 124 10000101 => 119 10000110 => 114 10000111 => 99 10001000 => 120 10001001 => 116 10001010 => 112 10001011 => 98 10001100 => 104 10001101 => 94 10001110 => 84 10001111 => 64 10010000 => 112 10010001 => 109 10010010 => 106 10010011 => 94 10010100 => 100 10010101 => 91 10010110 => 82 10010111 => 63 10011000 => 88 10011001 => 82 10011010 => 76 10011011 => 60 10011100 => 64 10011101 => 54 10011110 => 44 10011111 => 29 10100000 => 96 10100001 => 94 10100010 => 92 10100011 => 83 10100100 => 88 10100101 => 81 10100110 => 74 10100111 => 58 10101000 => 80 10101001 => 75 10101010 => 70 10101011 => 56 10101100 => 60 10101101 => 51 10101110 => 42 10101111 => 28 10110000 => 64 10110001 => 61 10110010 => 58 10110011 => 48 10110100 => 52 10110101 => 45 10110110 => 38 10110111 => 26 10111000 => 40 10111001 => 36 10111010 => 32 10111011 => 23 10111100 => 24 10111101 => 19 10111110 => 14 10111111 => 8 11000000 => 64 11000001 => 63 11000010 => 62 11000011 => 57 11000100 => 60 11000101 => 56 11000110 => 52 11000111 => 42 11001000 => 56 11001001 => 53 11001010 => 50 11001011 => 41 11001100 => 44 11001101 => 38 11001110 => 32 11001111 => 22 11010000 => 48 11010001 => 46 11010010 => 44 11010011 => 37 11010100 => 40 11010101 => 35 11010110 => 30 11010111 => 21 11011000 => 32 11011001 => 29 11011010 => 26 11011011 => 19 11011100 => 20 11011101 => 16 11011110 => 12 11011111 => 7 11100000 => 32 11100001 => 31 11100010 => 30 11100011 => 26 11100100 => 28 11100101 => 25 11100110 => 22 11100111 => 16 11101000 => 24 11101001 => 22 11101010 => 20 11101011 => 15 11101100 => 16 11101101 => 13 11101110 => 10 11101111 => 6 11110000 => 16 11110001 => 15 11110010 => 14 11110011 => 11 11110100 => 12 11110101 => 10 11110110 => 8 11110111 => 5 11111000 => 8 11111001 => 7 11111010 => 6 11111011 => 4 11111100 => 4 11111101 => 3 11111110 => 2 11111111 => 1 000000000 => 512 000000001 => 511 000000010 => 510 000000011 => 502 000000100 => 508 000000101 => 501 000000110 => 494 000000111 => 466 000001000 => 504 000001001 => 498 000001010 => 492 000001011 => 465 000001100 => 480 000001101 => 459 000001110 => 438 000001111 => 382 000010000 => 496 000010001 => 491 000010010 => 486 000010011 => 461 000010100 => 476 000010101 => 456 000010110 => 436 000010111 => 381 000011000 => 456 000011001 => 441 000011010 => 426 000011011 => 376 000011100 => 396 000011101 => 361 000011110 => 326 000011111 => 256 000100000 => 480 000100001 => 476 000100010 => 472 000100011 => 450 000100100 => 464 000100101 => 446 000100110 => 428 000100111 => 376 000101000 => 448 000101001 => 434 000101010 => 420 000101011 => 372 000101100 => 392 000101101 => 358 000101110 => 324 000101111 => 255 000110000 => 416 000110001 => 406 000110010 => 396 000110011 => 356 000110100 => 376 000110101 => 346 000110110 => 316 000110111 => 251 000111000 => 336 000111001 => 316 000111010 => 296 000111011 => 241 000111100 => 256 000111101 => 221 000111110 => 186 000111111 => 130 001000000 => 448 001000001 => 445 001000010 => 442 001000011 => 424 001000100 => 436 001000101 => 421 001000110 => 406 001000111 => 360 001001000 => 424 001001001 => 412 001001010 => 400 001001011 => 357 001001100 => 376 001001101 => 345 001001110 => 314 001001111 => 249 001010000 => 400 001010001 => 391 001010010 => 382 001010011 => 345 001010100 => 364 001010101 => 336 001010110 => 308 001010111 => 246 001011000 => 328 001011001 => 309 001011010 => 290 001011011 => 237 001011100 => 252 001011101 => 218 001011110 => 184 001011111 => 129 001100000 => 352 001100001 => 346 001100010 => 340 001100011 => 312 001100100 => 328 001100101 => 306 001100110 => 284 001100111 => 231 001101000 => 304 001101001 => 288 001101010 => 272 001101011 => 225 001101100 => 240 001101101 => 209 001101110 => 178 001101111 => 126 001110000 => 256 001110001 => 246 001110010 => 236 001110011 => 201 001110100 => 216 001110101 => 191 001110110 => 166 001110111 => 120 001111000 => 176 001111001 => 161 001111010 => 146 001111011 => 110 001111100 => 116 001111101 => 95 001111110 => 74 001111111 => 46 010000000 => 384 010000001 => 382 010000010 => 380 010000011 => 367 010000100 => 376 010000101 => 365 010000110 => 354 010000111 => 318 010001000 => 368 010001001 => 359 010001010 => 350 010001011 => 316 010001100 => 332 010001101 => 307 010001110 => 282 010001111 => 227 010010000 => 352 010010001 => 345 010010010 => 338 010010011 => 308 010010100 => 324 010010101 => 301 010010110 => 278 010010111 => 225 010011000 => 296 010011001 => 280 010011010 => 264 010011011 => 218 010011100 => 232 010011101 => 202 010011110 => 172 010011111 => 122 010100000 => 320 010100001 => 315 010100010 => 310 010100011 => 286 010100100 => 300 010100101 => 281 010100110 => 262 010100111 => 215 010101000 => 280 010101001 => 266 010101010 => 252 010101011 => 210 010101100 => 224 010101101 => 196 010101110 => 168 010101111 => 120 010110000 => 240 010110001 => 231 010110010 => 222 010110011 => 190 010110100 => 204 010110101 => 181 010110110 => 158 010110111 => 115 010111000 => 168 010111001 => 154 010111010 => 140 010111011 => 106 010111100 => 112 010111101 => 92 010111110 => 72 010111111 => 45 011000000 => 256 011000001 => 253 011000010 => 250 011000011 => 234 011000100 => 244 011000101 => 231 011000110 => 218 011000111 => 183 011001000 => 232 011001001 => 222 011001010 => 212 011001011 => 180 011001100 => 192 011001101 => 170 011001110 => 148 011001111 => 108 011010000 => 208 011010001 => 201 011010010 => 194 011010011 => 168 011010100 => 180 011010101 => 161 011010110 => 142 011010111 => 105 011011000 => 152 011011001 => 140 011011010 => 128 011011011 => 98 011011100 => 104 011011101 => 86 011011110 => 68 011011111 => 43 011100000 => 160 011100001 => 156 011100010 => 152 011100011 => 135 011100100 => 144 011100101 => 131 011100110 => 118 011100111 => 90 011101000 => 128 011101001 => 119 011101010 => 110 011101011 => 86 011101100 => 92 011101101 => 77 011101110 => 62 011101111 => 40 011110000 => 96 011110001 => 91 011110010 => 86 011110011 => 70 011110100 => 76 011110101 => 65 011110110 => 54 011110111 => 36 011111000 => 56 011111001 => 50 011111010 => 44 011111011 => 31 011111100 => 32 011111101 => 25 011111110 => 18 011111111 => 10 100000000 => 256 100000001 => 255 100000010 => 254 100000011 => 247 100000100 => 252 100000101 => 246 100000110 => 240 100000111 => 219 100001000 => 248 100001001 => 243 100001010 => 238 100001011 => 218 100001100 => 228 100001101 => 213 100001110 => 198 100001111 => 163 100010000 => 240 100010001 => 236 100010010 => 232 100010011 => 214 100010100 => 224 100010101 => 210 100010110 => 196 100010111 => 162 100011000 => 208 100011001 => 198 100011010 => 188 100011011 => 158 100011100 => 168 100011101 => 148 100011110 => 128 100011111 => 93 100100000 => 224 100100001 => 221 100100010 => 218 100100011 => 203 100100100 => 212 100100101 => 200 100100110 => 188 100100111 => 157 100101000 => 200 100101001 => 191 100101010 => 182 100101011 => 154 100101100 => 164 100101101 => 145 100101110 => 126 100101111 => 92 100110000 => 176 100110001 => 170 100110010 => 164 100110011 => 142 100110100 => 152 100110101 => 136 100110110 => 120 100110111 => 89 100111000 => 128 100111001 => 118 100111010 => 108 100111011 => 83 100111100 => 88 100111101 => 73 100111110 => 58 100111111 => 37 101000000 => 192 101000001 => 190 101000010 => 188 101000011 => 177 101000100 => 184 101000101 => 175 101000110 => 166 101000111 => 141 101001000 => 176 101001001 => 169 101001010 => 162 101001011 => 139 101001100 => 148 101001101 => 132 101001110 => 116 101001111 => 86 101010000 => 160 101010001 => 155 101010010 => 150 101010011 => 131 101010100 => 140 101010101 => 126 101010110 => 112 101010111 => 84 101011000 => 120 101011001 => 111 101011010 => 102 101011011 => 79 101011100 => 84 101011101 => 70 101011110 => 56 101011111 => 36 101100000 => 128 101100001 => 125 101100010 => 122 101100011 => 109 101100100 => 116 101100101 => 106 101100110 => 96 101100111 => 74 101101000 => 104 101101001 => 97 101101010 => 90 101101011 => 71 101101100 => 76 101101101 => 64 101101110 => 52 101101111 => 34 101110000 => 80 101110001 => 76 101110010 => 72 101110011 => 59 101110100 => 64 101110101 => 55 101110110 => 46 101110111 => 31 101111000 => 48 101111001 => 43 101111010 => 38 101111011 => 27 101111100 => 28 101111101 => 22 101111110 => 16 101111111 => 9 110000000 => 128 110000001 => 127 110000010 => 126 110000011 => 120 110000100 => 124 110000101 => 119 110000110 => 114 110000111 => 99 110001000 => 120 110001001 => 116 110001010 => 112 110001011 => 98 110001100 => 104 110001101 => 94 110001110 => 84 110001111 => 64 110010000 => 112 110010001 => 109 110010010 => 106 110010011 => 94 110010100 => 100 110010101 => 91 110010110 => 82 110010111 => 63 110011000 => 88 110011001 => 82 110011010 => 76 110011011 => 60 110011100 => 64 110011101 => 54 110011110 => 44 110011111 => 29 110100000 => 96 110100001 => 94 110100010 => 92 110100011 => 83 110100100 => 88 110100101 => 81 110100110 => 74 110100111 => 58 110101000 => 80 110101001 => 75 110101010 => 70 110101011 => 56 110101100 => 60 110101101 => 51 110101110 => 42 110101111 => 28 110110000 => 64 110110001 => 61 110110010 => 58 110110011 => 48 110110100 => 52 110110101 => 45 110110110 => 38 110110111 => 26 110111000 => 40 110111001 => 36 110111010 => 32 110111011 => 23 110111100 => 24 110111101 => 19 110111110 => 14 110111111 => 8 111000000 => 64 111000001 => 63 111000010 => 62 111000011 => 57 111000100 => 60 111000101 => 56 111000110 => 52 111000111 => 42 111001000 => 56 111001001 => 53 111001010 => 50 111001011 => 41 111001100 => 44 111001101 => 38 111001110 => 32 111001111 => 22 111010000 => 48 111010001 => 46 111010010 => 44 111010011 => 37 111010100 => 40 111010101 => 35 111010110 => 30 111010111 => 21 111011000 => 32 111011001 => 29 111011010 => 26 111011011 => 19 111011100 => 20 111011101 => 16 111011110 => 12 111011111 => 7 111100000 => 32 111100001 => 31 111100010 => 30 111100011 => 26 111100100 => 28 111100101 => 25 111100110 => 22 111100111 => 16 111101000 => 24 111101001 => 22 111101010 => 20 111101011 => 15 111101100 => 16 111101101 => 13 111101110 => 10 111101111 => 6 111110000 => 16 111110001 => 15 111110010 => 14 111110011 => 11 111110100 => 12 111110101 => 10 111110110 => 8 111110111 => 5 111111000 => 8 111111001 => 7 111111010 => 6 111111011 => 4 111111100 => 4 111111101 => 3 111111110 => 2 111111111 => 1 ----------------------------------------------------------------------------- Created: Mar 16, 2019 at 14:35 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Mar 16, 2019 at 14:35 by Martin Rubey