A183135 - OEIS

%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