A190526 Number of words of length n on alphabet {1,2,...,n} with no adjacent 1's.

1, 1, 3, 22, 216, 2704, 41125, 736344, 15171919, 353603584, 9197472240, 264121100000, 8299793401537, 283296166612992, 10437388463753355, 412833263709870976, 17448273126337500000, 784766322909932158976, 37424980125359271911917, 1886309447532093698360832

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Formula

a(n) = Sum_{i=0...ceiling(n/2)} (n-1)^(n-i)*binomial(n-1+1,i). Each term in the summation enumerates the number of such words containing exactly i 1's where 0<=i<=ceiling(n/2). Write down n-i letters that are not 1's leaving a space before and after every letter. Choose i of the n - i + 1 spaces in which to insert a 1.

a(n) ~ n^n. - Vaclav Kotesovec, Dec 21 2012

Example

a(3) = 22 because there are 27  3-letter words on {1,2,3} but 5 of these are "bad": 111, 112, 113, 211, 311.

Maple

b:= proc(n, k, w) option remember; `if`(n=0, 1,
      `if`(w, 0, b(n-1, k, true))+ (k-1)*b(n-1, k, false))
    end:
a:= n-> b(n, n, false):
seq (a(n), n=0..30);  # Alois P. Heinz, Dec 20 2012

Mathematica

ReplacePart[Table[Sum[Binomial[n-i+1, i] (n-1)^(n-i), {i, 0, Ceiling[n/2]}], {n, 0, 20}], 2->1]

Crossrefs

Sequence in context: A260154 A340474 A079489 * A141152 A066573 A341476

Adjacent sequences: A190523 A190524 A190525 * A190527 A190528 A190529

Keyword

nonn

Author

Geoffrey Critzer, Dec 19 2012

Status

approved