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
KEYWORD
nonn
AUTHOR
Danny Rorabaugh, Mar 02 2015
EXTENSIONS
a(11)-a(24) from Alois P. Heinz, Mar 03 2015
STATUS
approved