A174247 Number of words of length n composed of the letters a, b, and c with at least as many a's as b's, and at least as many b's as c's, and no a's adjacent.

1, 1, 2, 7, 9, 21, 76, 104, 255, 936, 1321, 3327, 12250, 17682, 45200, 166420, 244431, 630586, 2318863, 3453662, 8964527, 32909250, 49579091, 129250365, 473604092, 720390529, 1884080667, 6890849851, 10567693128, 27706723888, 101151927464, 156225285080, 410396361463

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Formula

a(n) = Sum_{i=floor((n+2)/3)..floor((n+1)/2)} Sum_{j=floor((n-i+1)/2)..min(n-i, i)} binomial(n-i+1, i)*binomial(n-i, j). - Andrew Howroyd, Jan 07 2020, after Maple

Example

For n = 0, there is 1 word (the empty word).
For n = 1, there is 1 word: a.
For n = 2, there are 2 words: ab, ba.
For n = 3, there are 7 words: aba, abc, acb, bac, bca, cab, cba.

Maple

myseq:=n->add(add(binomial(n-na+1, na)*binomial(n-na, nb), nb=floor((n-na+1)/2)..min(n-na, na)), na=floor((n+2)/3)..floor((n+1)/2));

Prog

(PARI) a(n)={sum(i=(n+2)\3, (n+1)\2, sum(j=(n-i+1)\2, min(n-i, i), binomial(n-i+1, i)*binomial(n-i, j)))} \\ Andrew Howroyd, Jan 07 2020

Crossrefs

Sequence in context: A293645 A293646 A020895 * A343963 A321322 A343495

Adjacent sequences: A174244 A174245 A174246 * A174248 A174249 A174250

Keyword

nonn,easy

Author

Amanda Lee (amanda.lee(AT)dpcdsb.org), Mar 13 2010

Extensions

Terms a(11) and beyond from Andrew Howroyd, Jan 07 2020

Status

approved