A255706 Number of length-n word structures with no consecutive nonrepeated letters.

1, 1, 1, 4, 11, 38, 151, 655, 3112, 16000, 88285, 519592, 3244512, 21400146, 148530179, 1081222613, 8231314455, 65369494593, 540322688516, 4639020151529, 41295634331020, 380514484523095, 3623898600072459, 35622399584611476, 360965731323718242

Offset

0,4

Comments

Consider all free words generated over a countably infinite alphabet. Two words are of the same structure provided there is a permutation of the alphabet that sends one word to the other.

The number a(n) only counts length-n structures that satisfy the following: For every positive i<n, either the i-th letter or the (i+1)-th letter appears at least twice in the structure. That is, for two successive letters, say xy, letter x and letter y cannot both appear only once.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..500

Formula

a(n) = Sum_{j=0..(n+1)/2} A000296(n-j)*C(n+1-j,j). - Alois P. Heinz, Mar 03 2015

Example

For n = 2 the a(2) = 1 structure is: aa.
For n = 3 the a(3) = 4 structures are: aaa, aab, aba, abb.
For n = 4 the a(4) = 11 structures are: aaaa, aaab, aaba, aabb, abaa, abab, abac, abba, abbb, abbc, abcb. The structure aabc, for example, is not counted because the word aabc contains bc and the letters b and c each only appear once in aabc.

Maple

with(combinat):
g:= proc(n) option remember; `if`(n=0, 1, bell(n-1)-g(n-1)) end:
a:= n-> add(g(n-j)*binomial(n+1-j, j), j=0..(n+1)/2):
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 03 2015

Mathematica

g[n_] := g[n] = If[n==0, 1, BellB[n-1] - g[n-1]]; a[n_] := Sum[g[n-j] * Binomial[n+1-j, j], {j, 0, (n+1)/2}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 26 2017, after Alois P. Heinz *)

Prog

(Sage)
def a(n):
    words = SetPartitions(range(n))
    count = len(words)
    for word in words:
        singles = []
        for letter in word:
        if len(letter)==1:
            singles.append(letter[0])
        singles.sort()
        for i in range(len(singles) - 1):
            if (singles[i] + 1)==singles[i + 1]:
                count -= 1
                break
    return count

Crossrefs

Cf. A000110, A000296.

Sequence in context: A149255 A149256 A149257 * A355888 A203161 A050987

Adjacent sequences: A255703 A255704 A255705 * A255707 A255708 A255709

Keyword

nonn

Author

Danny Rorabaugh, Mar 02 2015

Extensions

a(11)-a(24) from Alois P. Heinz, Mar 03 2015

Status

approved