- FindStat

Identifier

St001103: Integer partitions ⟶ ℤ

Values

=>
                            Cc0002;cc-rep
                            
                            
                            

                        []=>1
[1]=>1
[2]=>1
[1,1]=>2
[3]=>1
[2,1]=>3
[1,1,1]=>5
[4]=>1
[3,1]=>4
[2,2]=>6
[2,1,1]=>10
[1,1,1,1]=>17
[5]=>1
[4,1]=>5
[3,2]=>10
[3,1,1]=>17
[2,2,1]=>24
[2,1,1,1]=>41
[1,1,1,1,1]=>70
[6]=>1
[5,1]=>6
[4,2]=>15
[4,1,1]=>26
[3,3]=>20
[3,2,1]=>48
[3,1,1,1]=>83
[2,2,2]=>67
[2,2,1,1]=>116
[2,1,1,1,1]=>201
[1,1,1,1,1,1]=>349
[7]=>1
[6,1]=>7
[5,2]=>21
[5,1,1]=>37
[4,3]=>35
[4,2,1]=>85
[4,1,1,1]=>149
[3,3,1]=>110
[3,2,2]=>153
[3,2,1,1]=>268
[3,1,1,1,1]=>470
[2,2,2,1]=>373
[2,2,1,1,1]=>654
[2,1,1,1,1,1]=>1148
[1,1,1,1,1,1,1]=>2017
[8]=>1
[7,1]=>8
[6,2]=>28
[6,1,1]=>50
[5,3]=>56
[5,2,1]=>138
[5,1,1,1]=>245
[4,4]=>70
[4,3,1]=>220
[4,2,2]=>306
[4,2,1,1]=>542
[4,1,1,1,1]=>961
[3,3,2]=>392
[3,3,1,1]=>694
[3,2,2,1]=>966
[3,2,1,1,1]=>1712
[3,1,1,1,1,1]=>3037
[2,2,2,2]=>1345
[2,2,2,1,1]=>2384
[2,2,1,1,1,1]=>4230
[2,1,1,1,1,1,1]=>7513
[1,1,1,1,1,1,1,1]=>13358
[9]=>1
[8,1]=>9
[7,2]=>36
[7,1,1]=>65
[6,3]=>84
[6,2,1]=>210
[6,1,1,1]=>377
[5,4]=>126
[5,3,1]=>399
[5,2,2]=>556
[5,2,1,1]=>995
[5,1,1,1,1]=>1782
[4,4,1]=>490
[4,3,2]=>870
[4,3,1,1]=>1555
[4,2,2,1]=>2168
[4,2,1,1,1]=>3879
[4,1,1,1,1,1]=>6946
[3,3,3]=>1109
[3,3,2,1]=>2763
[3,3,1,1,1]=>4942
[3,2,2,2]=>3853
[3,2,2,1,1]=>6893
[3,2,1,1,1,1]=>12342
[3,1,1,1,1,1,1]=>22117
[2,2,2,2,1]=>9615
[2,2,2,1,1,1]=>17219
[2,2,1,1,1,1,1]=>30862
[2,1,1,1,1,1,1,1]=>55359
[1,1,1,1,1,1,1,1,1]=>99377
                    

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 words with multiplicities of the letters given by the partition, avoiding the consecutive pattern 123.
The total number of words with letter multiplicities given by an integer partition is St000048The multinomial of the parts of a partition.. For example, there are twelve words with letters $0,0,1,2$ corresponding to the partition $[2,1,1]$. Two of these contain an increasing factor of length three: $0012$ and $0120$.
Note that prescribing the multiplicities for different letters yields the same number. For example, there are also two words with letters $0,1,1,2$ containing an increasing factor of length three: $1012$ and $0121$.
The number of words of length $n$ with letters in an alphabet of size $k$ avoiding the consecutive pattern $123$ 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,2,3]])])

Created

Feb 04, 2018 at 00:36 by Martin Rubey

Updated

Feb 05, 2018 at 11:04 by Martin Rubey