login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #42 Aug 15 2018 22:21:51

%S 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,

%T 232,543,252,1,0,1,7,66,485,2092,3543,924,1,0,1,8,91,876,5725,19864,

%U 23823,3432,1,0,1,9,120,1435,12786,71445,195352,163719,12870,1,0

%N 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.

%C 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

%C 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

%H Alois P. Heinz, <a href="/A183135/b183135.txt">Antidiagonals n = 0..140, flattened</a>

%H Jason Bell, Marni Mishna, <a href="https://arxiv.org/abs/1805.08118">On the Complexity of the Cogrowth Sequence</a>, arXiv:1805.08118 [math.CO], 2018.

%H Beth Bjorkman et al., <a href="https://arxiv.org/abs/1710.10616">k-foldability of words</a>, arXiv preprint arXiv:1710.10616 [math.CO], 2017.

%F 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.

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

%F 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.

%e 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.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, ...

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

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

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

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

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

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

%p if n=0 then 1

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

%p fi

%p end:

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

%t 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 *)

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

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

%Y Main diagonal gives A294491.

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

%Y Cf. A007318, A183134, A256116, A256117.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Dec 26 2010