login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A255706 Number of length-n word structures with no consecutive nonrepeated letters. 2
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 (list; graph; refs; listen; history; text; internal format)
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

Cf. A000110, A000296.

Sequence in context: A149255 A149256 A149257 * A203161 A050987 A137191

Adjacent sequences:  A255703 A255704 A255705 * A255707 A255708 A255709

KEYWORD

nonn

AUTHOR

Danny Rorabaugh, Mar 02 2015

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 12:34 EDT 2018. Contains 316379 sequences. (Running on oeis4.)