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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A183135 Square array A(n,k) by antidiagonals. A(n,k) is the number of length 2n k-ary words (n,k>=0) that can be built by repeatedly inserting doublets into the initially empty word. 15
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 15, 20, 1, 0, 1, 5, 28, 87, 70, 1, 0, 1, 6, 45, 232, 543, 252, 1, 0, 1, 7, 66, 485, 2092, 3543, 924, 1, 0, 1, 8, 91, 876, 5725, 19864, 23823, 3432, 1, 0, 1, 9, 120, 1435, 12786, 71445, 195352, 163719, 12870, 1, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

A(n,k) is also the number of rooted closed walks of length 2n on the infinite rooted k-ary tree. - Danny Rorabaugh, Oct 31 2017

A(n,2k) is the number of unreduced words of length 2n that reduce to the empty word in the free group with k generators. - Danny Rorabaugh, Nov 09 2017

LINKS

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

Jason Bell, Marni Mishna, On the Complexity of the Cogrowth Sequence, arXiv:1805.08118 [math.CO], 2018.

Beth Bjorkman et al., k-foldability of words, arXiv preprint arXiv:1710.10616 [math.CO], 2017.

FORMULA

A(n,k) = k/n * Sum_{j=0..n-1} C(2*n,j)*(n-j)*(k-1)^j if n>0, A(0,k) = 1.

A(n,k) = A183134(n,k) if n=0 or k<2, A(n,k) = A183134(n,k)*k otherwise.

G.f. of column k: 1/(1-k*x) if k<2, 2*(k-1)/(k-2+k*sqrt(1-(4*k-4)*x)) otherwise.

EXAMPLE

A(2,2) = 6, because 6 words of length 4 can be built over 2-letter alphabet {a, b} by repeatedly inserting doublets (words with two equal letters) into the initially empty word: aaaa, aabb, abba, baab, bbaa, bbbb.

Square array A(n,k) begins:

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

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

  0,  1,   6,   15,    28,    45,  ...

  0,  1,  20,   87,   232,   485,  ...

  0,  1,  70,  543,  2092,  5725,  ...

  0,  1, 252, 3543, 19864, 71445,  ...

MAPLE

A:= proc(n, k) local j;

      if n=0 then 1

             else k/n *add(binomial(2*n, j) *(n-j) *(k-1)^j, j=0..n-1)

      fi

    end:

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

MATHEMATICA

A[_, 1] = 1; A[n_, k_] := If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*(k - 1)^j, {j, 0, n - 1}]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-Fran├žois Alcover, Dec 27 2013, translated from Maple *)

CROSSREFS

Columns k=0-10 give: A000007, A000012, A000984, A089022, A035610, A130976, A130977, A130978, A130979, A130980, A131521.

Rows n=0-3 give: A000012, A001477, A000384, A027849(k-1) for k>0.

Main diagonal gives A294491.

Coefficients of row polynomials in k, (k-1) are given by A157491, A039599.

Cf. A007318, A183134, A256116, A256117.

Sequence in context: A118345 A292804 A118350 * A294042 A287316 A322280

Adjacent sequences:  A183132 A183133 A183134 * A183136 A183137 A183138

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Dec 26 2010

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 February 15 22:28 EST 2019. Contains 320138 sequences. (Running on oeis4.)