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

%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