小编Jam*_*nch的帖子

我已经绞尽脑汁待了几天,研究出一系列或封闭形式的等式来解决以下问题:

具体来说:给定长度为N的所有字符串,从L字母的字母表中开始(以'A'开头,例如{A,B},{A,B,C},...),这些字符串中有多少包含与模式匹配的子字符串:'A',超过1不 - 'A','A'.该模式的标准正则表达式将是A[^A][^A]+A.

可能的串的数量是很简单的:L ^Ñ.对于N和L的小值,简单地创建所有可能的组合并使用正则表达式来查找与模式匹配的子串也是非常实用的.在R:

all.combinations <- function(N, L) {
    apply(
        expand.grid(rep(list(LETTERS[1:L]), N)),
        1,
        paste,
        collapse = ''
    )
}

matching.pattern <- function(N, L, pattern = 'A[^A][^A]+A') {
    sum(grepl(pattern, all.combinations(N, L)))
}

all.combinations(4, 2)
matching.pattern(4, 2)

我想出了以下内容,适用于N <7:

M <- function(N, L) {
    sum(
        sapply(
            2:(N-2),
            function(g) {
                (N - g - 1) * (L - 1) ** g * L ** (N - g - 2) …