Count number of ways that sequences contain at least one of the given subsequences Peter loves dices and some special numbers. Therefore he thrown dice n times and concatenate the numbers. Compute the probability that if he throws 6 to 27 seven times dice and concatenate the numbers, the sequence contains at least one subsequence of number sequence 

1, 2, 3, 4, 5, 6
1, 1, 2, 2, 3, 3
4, 4, 5, 5, 6, 6
1, 1, 1, 2, 2, 2
3, 3, 3, 4, 4, 4
5, 5, 5, 6, 6, 6
1, 1, 1, 1, 1, 1
2, 2, 2, 2, 2, 2
3, 3, 3, 3, 3, 3
4, 4, 4, 4, 4, 4
5, 5, 5, 5, 5, 5
6, 6, 6, 6, 6, 6


I saw that there is a way to do it by Markov chains. Is there any way to write the code more elegantly, like using inclusion-exclusion principle?

My code that uses Markov chains:

from sets import Set

def matMul(a,b):
    zip_b = zip(*b)
    return [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b)) 
             for col_b in zip_b] for row_a in a]

"""Matrix power for positive integer power"""
def matPow(a, n):
    if n&lt;1: return None
    if n==1: return a

    if n%2==0:
        aToHalfN = matPow(a, n/2)
        return matMul(aToHalfN, aToHalfN)
    else:
        return matMul(matPow(a, n-1), a)



def getProbSomeSeqIsSub(symbols, seqs, n, exactRational=False):

    def cleanSeqs(arr):
        ret = list(arr)
        changed = True
        while changed:
            changed = False
            for x in ret:
                hadADelete = False
                for y in ret:
                    if x!=y and y in x:
                        ret.remove(x)
                        hadADelete = True
                        changed = True
                        break
                if hadADelete:
                    break
        return ret


    seqs = cleanSeqs(seqs)

    symbolsLen = len(symbols)
    prefixes = Set([""]) #first state is '' empty start state

    for seq in seqs:
        for i in xrange(1, len(seq)):
            prefixes.add(seq[0:i])

    prefixes = sorted(list(prefixes))
    M = len(prefixes)+1 #last state (index M-1) is the absorbing one

    def findFallsBackTo(appendedRun):
        for i in xrange(0,len(appendedRun)):
            if appendedRun[i:] in prefixes:
                return appendedRun[i:]
        return ""

    def incrState(stateDict, state):
        if state in stateDict:
            stateDict[state] += 1
        else:
            stateDict[state] = 1

    def someEndInSeqs(s):
        for i in xrange(len(s)):
            if s[i:] in seqs: return True
        return False

    def getToStateVals(stateStr):
        ret = {}
        for i in symbols:
            stPlusI = stateStr+str(i)
            if someEndInSeqs(stPlusI):
                incrState(ret, M-1)
            elif stPlusI in prefixes:
                incrState( ret, prefixes.index(stPlusI) )
            else:
                fallsToPrefix = findFallsBackTo(stPlusI)
                incrState(ret, prefixes.index(fallsToPrefix))
        return ret    


    a = []
    aInts = []
    for i in xrange(M):
        a += [[]]
        aInts += [[]]
        for j in xrange(M):
            a[i] += [0]
            aInts[i] += [0]

    for i in xrange(M-1):
        ps = getToStateVals(prefixes[i])
        for toI in ps:
            a[toI][i] = float(ps[toI])/symbolsLen
            aInts[toI][i] = ps[toI]

    a[M-1][M-1] = 1.0
    aInts[M-1][M-1] = symbolsLen

    if exactRational: return str(matPow(aInts, n)[M-1][0])+" / "+str(symbolsLen**n)
    else: return matPow(a, n)[M-1][0]



for i in range(6,28):
 a = getProbSomeSeqIsSub([1,2,3,4,5,6], ["123456", "112233", "445566",  "111222", "333444", '555666', '111111', '222222', '333333', '444444',  '555555', '666666'], i, True)

 b = a.split("/")
 oso = int(b[0])
 nimi = int(b[1])
 print(str(i)+ " "+str(oso*6**i/nimi))
Use numpy!

Don't roll your own matMul. It's not worth it. numpy will outperform you and will be simpler to use. The same goes for matPow, though (I'm not sure) you may still need to write a thin wrapper around numpy.

Python names

Use snake_case for functions and variables, such as

get_sub_prob

Make a main function

...to pull your last six lines out of global scope.