login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A242464 Number A(n,k) of n-length words w over a k-ary alphabet {a_1,...,a_k} such that w contains never more than j consecutive letters a_j (for 1<=j<=k); square array A(n,k), n>=0, k>=0, read by antidiagonals. 11
1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 3, 0, 0, 1, 4, 8, 4, 0, 0, 1, 5, 15, 21, 5, 0, 0, 1, 6, 24, 56, 54, 7, 0, 0, 1, 7, 35, 115, 208, 140, 9, 0, 0, 1, 8, 48, 204, 550, 773, 362, 12, 0, 0, 1, 9, 63, 329, 1188, 2631, 2872, 937, 16, 0, 0, 1, 10, 80, 496, 2254, 6919, 12584, 10672, 2425, 21, 0, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

The sequence of column k satisfies a linear recurrence with constant coefficients of order A015614(k+1) for k>1.

LINKS

Alois P. Heinz, Antidiagonals n = 0..120, flattened

FORMULA

G.f. of column k: 1/(1-Sum_{i=1..k} v(i)/(1+v(i))) with v(i) = (x-x^(i+1))/(1-x).

EXAMPLE

A(0,k) = 1 for all k: the empty word.

A(1,5) = 5: [1], [2], [3], [4], [5].

A(2,4) = 15: [1,2], [1,3], [1,4], [2,1], [2,2], [2,3], [2,4], [3,1], [3,2], [3,3], [3,4], [4,1], [4,2], [4,3], [4,4].

A(3,3) = 21: [1,2,1], [1,2,2], [1,2,3], [1,3,1], [1,3,2], [1,3,3], [2,1,2], [2,1,3], [2,2,1], [2,2,3], [2,3,1], [2,3,2], [2,3,3], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3], [3,3,1], [3,3,2], [3,3,3].

A(4,2) = 5: [1,2,1,2], [1,2,2,1], [2,1,2,1], [2,1,2,2], [2,2,1,2].

A(n,1) = 0 for n>1.

A(n,0) = 0 for n>0.

Square array A(n,k) begins:

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

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

  0, 0,  3,   8,    15,    24,     35,     48, ...

  0, 0,  4,  21,    56,   115,    204,    329, ...

  0, 0,  5,  54,   208,   550,   1188,   2254, ...

  0, 0,  7, 140,   773,  2631,   6919,  15443, ...

  0, 0,  9, 362,  2872, 12584,  40295, 105804, ...

  0, 0, 12, 937, 10672, 60191, 234672, 724892, ...

MAPLE

b:= proc(n, k, c, t) option remember;

      `if`(n=0, 1, add(`if`(c=t and j=c, 0,

       b(n-1, k, j, 1+`if`(j=c, t, 0))), j=1..k))

    end:

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

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

MATHEMATICA

nn=10; Transpose[Map[PadRight[#, nn]&, Table[CoefficientList[Series[1/(1-Sum[v[i]/(1+v[i])/.v[i]->(z-z^(i+1))/(1-z), {i, 1, n}]), {z, 0, nn}], z], {n, 0, nn}]]]//Grid

(* Second program: *)

b[n_, k_, c_, t_] := b[n, k, c, t] = If[n == 0, 1, Sum[If[c == t && j == c, 0, b[n - 1, k, j, 1 + If[j == c, t, 0]]], {j, 1, k}]];

A[n_, k_] := b[n, k, 0, 0];

Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-Fran├žois Alcover, Dec 28 2020, after Maple *)

CROSSREFS

Columns k=0-10 give: A000007, A019590(n+1), A164001(n+1), A242452, A242495, A242509, A242629, A242630, A242631, A242632, A242633.

Rows n=0-2 give: A000012, A001477, A005563(k-1) for k>0.

Main diagonal gives A242635.

Sequence in context: A309021 A307968 A338501 * A273185 A259784 A145224

Adjacent sequences:  A242461 A242462 A242463 * A242465 A242466 A242467

KEYWORD

nonn,tabl

AUTHOR

Geoffrey Critzer and Alois P. Heinz, May 15 2014

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 September 19 19:28 EDT 2021. Contains 347564 sequences. (Running on oeis4.)