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

Author

Danny Rorabaugh, Mar 02 2015

Keywords

• nonn

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A000110, A000296.

Programs

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 *)

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

Formula

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

Extensions

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.