%I #33 Mar 08 2020 11:40:49
%S 1,1,1,4,11,38,151,655,3112,16000,88285,519592,3244512,21400146,
%T 148530179,1081222613,8231314455,65369494593,540322688516,
%U 4639020151529,41295634331020,380514484523095,3623898600072459,35622399584611476,360965731323718242
%N Number of length-n word structures with no consecutive nonrepeated letters.
%C 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.
%C 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.
%H Alois P. Heinz, <a href="/A255706/b255706.txt">Table of n, a(n) for n = 0..500</a>
%F a(n) = Sum_{j=0..(n+1)/2} A000296(n-j)*C(n+1-j,j). - _Alois P. Heinz_, Mar 03 2015
%e For n = 2 the a(2) = 1 structure is: aa.
%e For n = 3 the a(3) = 4 structures are: aaa, aab, aba, abb.
%e 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.
%p with(combinat):
%p g:= proc(n) option remember; `if`(n=0, 1, bell(n-1)-g(n-1)) end:
%p a:= n-> add(g(n-j)*binomial(n+1-j, j), j=0..(n+1)/2):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Mar 03 2015
%t 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_ *)
%o (Sage)
%o def a(n):
%o words = SetPartitions(range(n))
%o count = len(words)
%o for word in words:
%o singles = []
%o for letter in word:
%o if len(letter)==1:
%o singles.append(letter[0])
%o singles.sort()
%o for i in range(len(singles) - 1):
%o if (singles[i] + 1)==singles[i + 1]:
%o count -= 1
%o break
%o return count
%Y Cf. A000110, A000296.
%K nonn
%O 0,4
%A _Danny Rorabaugh_, Mar 02 2015
%E a(11)-a(24) from _Alois P. Heinz_, Mar 03 2015