A027849 -id:A027849 - cp's OEIS frontend

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.

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

Offset: 0

Alois P. Heinz, Dec 26 2010

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

			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,  ...

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.

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.

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);

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

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.

A260260 a(n) = n(16n^2 - 21*n + 7)/2.

Original entry on oeis.org

0, 1, 29, 132, 358, 755, 1371, 2254, 3452, 5013, 6985, 9416, 12354, 15847, 19943, 24690, 30136, 36329, 43317, 51148, 59870, 69531, 80179, 91862, 104628, 118525, 133601, 149904, 167482, 186383, 206655, 228346, 251504, 276177, 302413, 330260, 359766, 390979

Offset: 0

Bruno Berselli, Jul 21 2015

Similar sequences, where P(s, m) = ((s-2)*m^2-(s-4)*m)/2 is the m-th s-gonal number:
A000578: P(3, m)*P( 3, m) - P(3, m-1)*P( 3, m-1);
A213772: P(3, m)*P( 4, m) - P(3, m-1)*P( 4, m-1) for m>0;
A005915: P(3, m)*P( 5, m) - P(3, m-1)*P( 5, m-1)   "    ;
A130748: P(3, m)*P( 6, m) - P(3, m-1)*P( 6, m-1) for m>1;
A027849: P(3, m)*P( 7, m) - P(3, m-1)*P( 7, m-1) for m>0;
A214092: P(3, m)*P( 8, m) - P(3, m-1)*P( 8, m-1)   "    ;
A100162: P(3, m)*P( 9, m) - P(3, m-1)*P( 9, m-1)   "    ;
A260260: P(3, m)*P(10, m) - P(3, m-1)*P(10, m-1), this sequence;
A100165: P(3, m)*P(11, m) - P(3, m-1)*P(11, m-1) for m>0.

Bruno Berselli, Table of n, a(n) for n = 0..1000
OEIS Wiki, Figurate numbers.
Wikipedia, Polygonal numbers: Table of values.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A000217, A000292, A001107.
Subsequence of A047275.
Sequences of the same type (see comment): A000578, A005915, A027849, A100162, A100165, A130748, A213772, A214092.

Magma
```
[n*(16*n^2-21*n+7)/2: n in [0..40]];
```

Table[n (16 n^2 - 21 n + 7)/2, {n, 0, 40}]
LinearRecurrence[{4,-6,4,-1},{0,1,29,132},40] (* Harvey P. Dale, May 08 2025 *)

vector(40, n, n--; n*(16*n^2-21*n+7)/2)

Sage
```
[n*(16*n^2-21*n+7)/2 for n in (0..40)]
```

G.f.: x*(1 + 25*x + 22*x^2)/(1 - x)^4. [corrected by Georg Fischer, May 10 2019]
a(n) = A000217(n)*A001107(n) - A000217(n-1)*A001107(n-1), with A000217(-1) = 0.
a(n) = A000292(n) + 25*A000292(n-1) + 22*A000292(n-2), with A000292(-2) = A000292(-1) = 0.
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n >= 4. - Wesley Ivan Hurt, Dec 18 2020
E.g.f.: exp(x)*x*(2 + 27*x + 16*x^2)/2. - Elmo R. Oliveira, Aug 08 2025

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260260 a(n) = n(16n^2 - 21*n + 7)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260260 a(n) = n*(16*n^2 - 21*n + 7)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A260260 a(n) = n(16n^2 - 21*n + 7)/2.