***************************************************************************** * 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: St001102 ----------------------------------------------------------------------------- Collection: Integer compositions ----------------------------------------------------------------------------- Description: The number of words with multiplicities of the letters given by the composition, avoiding the consecutive pattern 132. The total number of words with letter multiplicities given by an integer partition is [[St000048]]. For example, there are twelve words with letters $0,0,1,2$ corresponding to the partition $[2,1,1]$. Two of these contain the pattern $132$: $0,0,2,1$ and $0,2,1,0$. Note that this statistic is not constant on compositions having the same parts. The number of words of length $n$ with letters in an alphabet of size $k$ avoiding the consecutive pattern $132$ is determined in [1]. ----------------------------------------------------------------------------- References: [1] Burstein, A. Enumeration of words with forbidden patterns [[MathSciNet:2697353]] ----------------------------------------------------------------------------- Code: def avoids(w, pattern): l = [len(p) for p in pattern] l_p = len(pattern) n = len(w) A = sorted(list(set([a for p in pattern for a in p]))) pattern = [[A.index(a) for a in p] for p in pattern] k = 1+max(max(p) for p in pattern) def is_match(s): assignment = [None]*k for i in range(l_p): for j in range(len(pattern[i])): l = w[s[i]+j] p = pattern[i][j] m = assignment[p] if m is None: assignment[p] = l elif m != l: return False return all(assignment[i] < assignment[i+1] for i in range(k-1)) for s in Subsets(list(range(len(w))), l_p)._fast_iterator(): if all(s[i]+l[i] <= s[i+1] for i in range(l_p-1)) and s[-1]+l[-1] <= n: if is_match(s): return False return True def statistic(la): mset = [i for i, p in enumerate(la) for _ in range(p)] return len([w for w in Permutations(mset)if avoids(w, [[1,3,2]])]) ----------------------------------------------------------------------------- Statistic values: [] => 1 [1] => 1 [1,1] => 2 [2] => 1 [1,1,1] => 5 [1,2] => 3 [2,1] => 3 [3] => 1 [1,1,1,1] => 16 [1,1,2] => 10 [1,2,1] => 10 [1,3] => 4 [2,1,1] => 10 [2,2] => 6 [3,1] => 4 [4] => 1 [1,1,1,1,1] => 63 [1,1,1,2] => 40 [1,1,2,1] => 40 [1,1,3] => 17 [1,2,1,1] => 39 [1,2,2] => 24 [1,3,1] => 17 [1,4] => 5 [2,1,1,1] => 39 [2,1,2] => 24 [2,2,1] => 24 [2,3] => 10 [3,1,1] => 17 [3,2] => 10 [4,1] => 5 [5] => 1 [1,1,1,1,1,1] => 296 [1,1,1,1,2] => 188 [1,1,1,2,1] => 188 [1,1,1,3] => 82 [1,1,2,1,1] => 184 [1,1,2,2] => 114 [1,1,3,1] => 82 [1,1,4] => 26 [1,2,1,1,1] => 180 [1,2,1,2] => 112 [1,2,2,1] => 112 [1,2,3] => 48 [1,3,1,1] => 80 [1,3,2] => 48 [1,4,1] => 26 [1,5] => 6 [2,1,1,1,1] => 180 [2,1,1,2] => 112 [2,1,2,1] => 112 [2,1,3] => 48 [2,2,1,1] => 110 [2,2,2] => 67 [2,3,1] => 48 [2,4] => 15 [3,1,1,1] => 80 [3,1,2] => 48 [3,2,1] => 48 [3,3] => 20 [4,1,1] => 26 [4,2] => 15 [5,1] => 6 [6] => 1 [1,1,1,1,1,1,1] => 1623 [1,1,1,1,1,2] => 1023 [1,1,1,1,2,1] => 1023 [1,1,1,1,3] => 450 [1,1,1,2,1,1] => 1006 [1,1,1,2,2] => 622 [1,1,1,3,1] => 450 [1,1,1,4] => 148 [1,1,2,1,1,1] => 984 [1,1,2,1,2] => 611 [1,1,2,2,1] => 611 [1,1,2,3] => 265 [1,1,3,1,1] => 439 [1,1,3,2] => 265 [1,1,4,1] => 148 [1,1,5] => 37 [1,2,1,1,1,1] => 969 [1,2,1,1,2] => 603 [1,2,1,2,1] => 603 [1,2,1,3] => 262 [1,2,2,1,1] => 594 [1,2,2,2] => 363 [1,2,3,1] => 262 [1,2,4] => 85 [1,3,1,1,1] => 427 [1,3,1,2] => 259 [1,3,2,1] => 259 [1,3,3] => 110 [1,4,1,1] => 145 [1,4,2] => 85 [1,5,1] => 37 [1,6] => 7 [2,1,1,1,1,1] => 969 [2,1,1,1,2] => 603 [2,1,1,2,1] => 603 [2,1,1,3] => 262 [2,1,2,1,1] => 594 [2,1,2,2] => 363 [2,1,3,1] => 262 [2,1,4] => 85 [2,2,1,1,1] => 582 [2,2,1,2] => 357 [2,2,2,1] => 357 [2,2,3] => 153 [2,3,1,1] => 256 [2,3,2] => 153 [2,4,1] => 85 [2,5] => 21 [3,1,1,1,1] => 427 [3,1,1,2] => 259 [3,1,2,1] => 259 [3,1,3] => 110 [3,2,1,1] => 256 [3,2,2] => 153 [3,3,1] => 110 [3,4] => 35 [4,1,1,1] => 145 [4,1,2] => 85 [4,2,1] => 85 [4,3] => 35 [5,1,1] => 37 [5,2] => 21 [6,1] => 7 [7] => 1 [1,1,1,1,1,1,1,1] => 10176 [1,1,1,1,1,1,2] => 6344 [1,1,1,1,1,2,1] => 6344 [1,1,1,1,1,3] => 2790 [1,1,1,1,2,1,1] => 6264 [1,1,1,1,2,2] => 3848 [1,1,1,1,3,1] => 2790 [1,1,1,1,4] => 934 [1,1,1,2,1,1,1] => 6148 [1,1,1,2,1,2] => 3790 [1,1,1,2,2,1] => 3790 [1,1,1,2,3] => 1648 [1,1,1,3,1,1] => 2732 [1,1,1,3,2] => 1648 [1,1,1,4,1] => 934 [1,1,1,5] => 244 [1,1,2,1,1,1,1] => 6040 [1,1,2,1,1,2] => 3732 [1,1,2,1,2,1] => 3732 [1,1,2,1,3] => 1626 [1,1,2,2,1,1] => 3688 [1,1,2,2,2] => 2246 [1,1,2,3,1] => 1626 [1,1,2,4] => 538 [1,1,3,1,1,1] => 2652 [1,1,3,1,2] => 1608 [1,1,3,2,1] => 1608 [1,1,3,3] => 688 [1,1,4,1,1] => 912 [1,1,4,2] => 538 [1,1,5,1] => 244 [1,1,6] => 50 [1,2,1,1,1,1,1] => 5976 [1,2,1,1,1,2] => 3696 [1,2,1,1,2,1] => 3696 [1,2,1,1,3] => 1612 [1,2,1,2,1,1] => 3652 [1,2,1,2,2] => 2226 [1,2,1,3,1] => 1612 [1,2,1,4] => 534 [1,2,2,1,1,1] => 3588 [1,2,2,1,2] => 2194 [1,2,2,2,1] => 2194 [1,2,2,3] => 946 [1,2,3,1,1] => 1580 [1,2,3,2] => 946 [1,2,4,1] => 534 [1,2,5] => 138 [1,3,1,1,1,1] => 2592 [1,3,1,1,2] => 1576 [1,3,1,2,1] => 1576 [1,3,1,3] => 676 [1,3,2,1,1] => 1560 [1,3,2,2] => 936 [1,3,3,1] => 676 [1,3,4] => 220 [1,4,1,1,1] => 888 [1,4,1,2] => 526 [1,4,2,1] => 526 [1,4,3] => 220 [1,5,1,1] => 240 [1,5,2] => 138 [1,6,1] => 50 [1,7] => 8 [2,1,1,1,1,1,1] => 5976 [2,1,1,1,1,2] => 3696 [2,1,1,1,2,1] => 3696 [2,1,1,1,3] => 1612 [2,1,1,2,1,1] => 3652 [2,1,1,2,2] => 2226 [2,1,1,3,1] => 1612 [2,1,1,4] => 534 [2,1,2,1,1,1] => 3588 [2,1,2,1,2] => 2194 [2,1,2,2,1] => 2194 [2,1,2,3] => 946 [2,1,3,1,1] => 1580 [2,1,3,2] => 946 [2,1,4,1] => 534 [2,1,5] => 138 [2,2,1,1,1,1] => 3528 [2,2,1,1,2] => 2162 [2,2,1,2,1] => 2162 [2,2,1,3] => 934 [2,2,2,1,1] => 2138 [2,2,2,2] => 1292 [2,2,3,1] => 934 [2,2,4] => 306 [2,3,1,1,1] => 1536 [2,3,1,2] => 924 [2,3,2,1] => 924 [2,3,3] => 392 [2,4,1,1] => 522 [2,4,2] => 306 [2,5,1] => 138 [2,6] => 28 [3,1,1,1,1,1] => 2592 [3,1,1,1,2] => 1576 [3,1,1,2,1] => 1576 [3,1,1,3] => 676 [3,1,2,1,1] => 1560 [3,1,2,2] => 936 [3,1,3,1] => 676 [3,1,4] => 220 [3,2,1,1,1] => 1536 [3,2,1,2] => 924 [3,2,2,1] => 924 [3,2,3] => 392 [3,3,1,1] => 664 [3,3,2] => 392 [3,4,1] => 220 [3,5] => 56 [4,1,1,1,1] => 888 [4,1,1,2] => 526 [4,1,2,1] => 526 [4,1,3] => 220 [4,2,1,1] => 522 [4,2,2] => 306 [4,3,1] => 220 [4,4] => 70 [5,1,1,1] => 240 [5,1,2] => 138 [5,2,1] => 138 [5,3] => 56 [6,1,1] => 50 [6,2] => 28 [7,1] => 8 [8] => 1 ----------------------------------------------------------------------------- Created: Feb 04, 2018 at 00:56 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Feb 04, 2018 at 00:56 by Martin Rubey