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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A220062 Number A(n,k) of n length words over k-ary alphabet, where neighboring letters are neighbors in the alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals. 13
1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 4, 2, 0, 0, 1, 5, 6, 6, 2, 0, 0, 1, 6, 8, 10, 8, 2, 0, 0, 1, 7, 10, 14, 16, 12, 2, 0, 0, 1, 8, 12, 18, 24, 26, 16, 2, 0, 0, 1, 9, 14, 22, 32, 42, 42, 24, 2, 0, 0, 1, 10, 16, 26, 40, 58, 72, 68, 32, 2, 0, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

Equivalently, the number of walks of length n-1 on the path graph P_k. - Andrew Howroyd, Apr 17 2017

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

EXAMPLE

A(5,3) = 12: there are 12 words of length 5 over 3-ary alphabet {a,b,c}, where neighboring letters are neighbors in the alphabet: ababa, ababc, abcba, abcbc, babab, babcb, bcbab, bcbcb, cbaba, cbabc, cbcba, cbcbc.

Square array A(n,k) begins:

  1,  1,  1,  1,  1,   1,   1,   1, ...

  0,  1,  2,  3,  4,   5,   6,   7, ...

  0,  0,  2,  4,  6,   8,  10,  12, ...

  0,  0,  2,  6, 10,  14,  18,  22, ...

  0,  0,  2,  8, 16,  24,  32,  40, ...

  0,  0,  2, 12, 26,  42,  58,  74, ...

  0,  0,  2, 16, 42,  72, 104, 136, ...

  0,  0,  2, 24, 68, 126, 188, 252, ...

MAPLE

b:= proc(n, i, k) option remember; `if`(n=0, 1,

      `if`(i=0, add(b(n-1, j, k), j=1..k),

      `if`(i>1, b(n-1, i-1, k), 0)+

      `if`(i<k, b(n-1, i+1, k), 0)))

    end:

A:= (n, k)-> b(n, 0, k):

seq(seq(A(n, d-n), n=0..d), d=0..14);

MATHEMATICA

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i == 0, Sum[b[n-1, j, k], {j, 1, k}], If[i>1, b[n-1, i-1, k], 0] + If[i<k, b[n-1, i+1, k], 0]]]; A[n_, k_] := b[n, 0, k]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-Fran├žois Alcover, Jan 19 2015, after Alois P. Heinz *)

PROG

(PARI)

TransferGf(m, u, t, v, z)=vector(m, i, u(i))*matsolve(matid(m)-z*matrix(m, m, i, j, t(i, j)), vectorv(m, i, v(i)));

ColGf(m, z)=1+z*TransferGf(m, i->1, (i, j)->abs(i-j)==1, j->1, z);

a(n, k)=Vec(ColGf(k, x) + O(x^(n+1)))[n+1];

for(n=0, 7, for(k=0, 7, print1( a(n, k), ", ") ); print(); );

\\ Andrew Howroyd, Apr 17 2017

CROSSREFS

Columns k=0, 2-10 give: A000007, A040000, A029744(n+2) for n>0, A006355(n+3) for n>0, A090993(n+1) for n>0, A090995(n-1) for n>2, A129639, A153340, A153362, A153360.

Rows 0-6 give: A000012, A001477, A005843(k-1) for k>0, A016825(k-2) for k>1, A008590(k-2) for k>2, A113770(k-2) for k>3, A063164(k-2) for k>4.

Main diagonal gives: A102699.

Cf. A198632, A188866, A276562, A208727, A208671.

Sequence in context: A292377 A216238 A157608 * A216054 A217257 A217315

Adjacent sequences:  A220059 A220060 A220061 * A220063 A220064 A220065

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Dec 03 2012

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 23 12:43 EDT 2019. Contains 321430 sequences. (Running on oeis4.)