cp's OEIS Frontend

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

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