A208879 -id:A208879 - cp's OEIS frontend

A208673 Number of words A(n,k), either empty or beginning with the first letter of the k-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 5, 10, 1, 1, 1, 1, 9, 37, 35, 1, 1, 1, 1, 15, 163, 309, 126, 1, 1, 1, 1, 25, 640, 3593, 2751, 462, 1, 1, 1, 1, 41, 2503, 36095, 87501, 25493, 1716, 1, 1, 1, 1, 67, 9559, 362617, 2336376, 2266155, 242845, 6435, 1, 1

Offset: 0

Alois P. Heinz, Feb 29 2012

Also the number of (n*k-1)-step walks on k-dimensional cubic lattice from (1,0,...,0) to (n,n,...,n) with positive unit steps in all dimensions such that the absolute difference of the dimension indices used in consecutive steps is <= 1.

All rows are linear recurrences with constant coefficients and for n > 0 the order of the recurrence is bounded by 2*n-1. For n up to at least 20 this upper bound is exact. - Andrew Howroyd, Feb 22 2022

			A(0,0) = A(n,0) = A(0,k) = 1: the empty word.
A(2,3) = 5:
  +------+   +------+   +------+   +------+   +------+
  |aabbcc|   |aabcbc|   |aabccb|   |ababcc|   |abccba|
  +------+   +------+   +------+   +------+   +------+
  |122222|   |122222|   |122222|   |112222|   |111112|
  |001222|   |001122|   |001112|   |011222|   |011122|
  |000012|   |000112|   |000122|   |000012|   |001222|
  +------+   +------+   +------+   +------+   +------+
  |xx    |   |xx    |   |xx    |   |x x   |   |x    x|
  |  xx  |   |  x x |   |  x  x|   | x x  |   | x  x |
  |    xx|   |   x x|   |   xx |   |    xx|   |  xx  |
  +------+   +------+   +------+   +------+   +------+
Square array A(n,k) begins:
  1,  1,    1,     1,       1,         1,           1, ..
  1,  1,    1,     1,       1,         1,           1, ..
  1,  1,    3,     5,       9,        15,          25, ..
  1,  1,   10,    37,     163,       640,        2503, ..
  1,  1,   35,   309,    3593,     36095,      362617, ..
  1,  1,  126,  2751,   87501,   2336376,    62748001, ..
  1,  1,  462, 25493, 2266155, 164478048, 12085125703, ..

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Columns k=0+1, 2-4 give: A000012, A088218, A208675, A212334.
Rows n=0+1, 2-3 give: A000012, A001595, A208674.
Main diagonal gives A351759.
Cf. A208879 (cyclic alphabet), A331562.

b:= proc(t, l) option remember; local n; n:= nops(l);
     `if`(n<2 or {0}={l[]}, 1,
     `if`(l[t]>0, b(t, [seq(l[i]-`if`(i=t, 1, 0), i=1..n)]), 0)+
     `if`(t0,
                  b(t+1, [seq(l[i]-`if`(i=t+1, 1, 0), i=1..n)]), 0)+
     `if`(t>1 and l[t-1]>0,
                  b(t-1, [seq(l[i]-`if`(i=t-1, 1, 0), i=1..n)]), 0))
    end:
A:= (n, k)-> `if`(n=0 or k=0, 1, b(1, [n-1, n$(k-1)])):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[t_, l_List] := b[t, l] = Module[{n = Length[l]}, If[n < 2 || {0} == Union[l], 1, If[l[[t]] > 0, b[t, Table[l[[i]] - If[i == t, 1, 0], {i, 1, n}]], 0] + If[t < n && l[[t + 1]] > 0, b[t + 1, Table[l[[i]] - If[i == t + 1, 1, 0], {i, 1, n}]], 0] + If[t > 1 && l[[t - 1]] > 0, b[t - 1, Table[l[[i]] - If[i == t - 1, 1, 0], {i, 1, n}]], 0]]]; A[n_, k_] := If[n == 0 || k == 0, 1, b[1, Join[{n - 1}, Array[n&, k - 1]]]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

F(u)={my(n=#u); sum(k=1, n,u[k]*binomial(n-1,k-1))}
step(u, c)={my(n=#u); vector(n, k, sum(i=max(0, 2*k-c-n), k-1, sum(j=0, n-2*k+i+c, u[k-i+j]*binomial(n-1, 2*k-1-c-i+j)*binomial(k-1, k-i-1)*binomial(k-i+j-c, j) ))) }
R(n,k)={my(r=vector(n+1), u=vector(k), v=vector(k)); u[1]=v[1]=r[1]=r[2]=1; for(n=3, #r, u=step(u,1); v=step(v,0)+u; r[n]=F(v)); r}
T(n,k)={if(n==0||k==0, 1, R(k,n)[1+k])} \\ Andrew Howroyd, Feb 22 2022

A208881 Number of words either empty or beginning with the first letter of the ternary alphabet, where each letter of the alphabet occurs n times.

Original entry on oeis.org

1, 2, 30, 560, 11550, 252252, 5717712, 133024320, 3155170590, 75957810500, 1850332263780, 45508998487680, 1128243920840400, 28159366024288800, 706857555303576000, 17831659928458210560, 451781821468671694110, 11489952898943726476500, 293206575828601020085500

Offset: 0

Alois P. Heinz, Mar 02 2012

Also the number of (n*k-1)-step walks on k-dimensional cubic lattice from (1,0,...,0) to (n,n,...,n) with positive unit steps in all dimensions.

			a(0) = 1: the empty word.
a(1) = 2 = |{abc, acb}|.
a(2) = 30 = |{aabbcc, aabcbc, aabccb, aacbbc, aacbcb, aaccbb, ababcc, abacbc, abaccb, abbacc, abbcac, abbcca, abcabc, abcacb, abcbac, abcbca, abccab, abccba, acabbc, acabcb, acacbb, acbabc, acbacb, acbbac, acbbca, acbcab, acbcba, accabb, accbab, accbba}|.

Alois P. Heinz, Table of n, a(n) for n = 0..220
J. Draisma, E. Horobet, G. Ottaviani, B. Sturmfels and R. K. Thomas, The Euclidean distance degree of an algebraic variety, arXiv preprint arXiv: 1309.0049, 2013.

Column k=3 of A208879.

Cf. A060542, A253283.

a:= n-> `if`(n=0, 1, (3*n)!/(3*n!^3)):
seq(a(n), n=0..20);

a(n) = (3*n)!/(3 * n!^3) for n>0, a(0) = 1.
a(n) = 2 * A060542(n) for n>0.
a(n) = A253283(2*n,n) for n>=0. - Peter Luschny, Mar 22 2015
n^2*a(n) -3*(3*n-1)*(3*n-2)*a(n-1)=0. - R. J. Mathar, Nov 01 2015

A209183 Number of words, either empty or beginning with the first letter of the cyclic 4-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet.

Original entry on oeis.org

1, 2, 62, 2830, 151686, 8893482, 552309938, 35702836038, 2377145582550, 161906392007554, 11227409430866262, 790011772823243214, 56264746328351077194, 4048156319577916177530, 293797748889879887735802, 21483000387938509658756790, 1581177100760460768472276086

Offset: 0

Alois P. Heinz, Mar 05 2012

The first and the last letters are considered neighbors in a cyclic alphabet. The words are not considered cyclic here.

a(n) is also the number of (4*n-1)-step walks on 4-dimensional cubic lattice from (1,0,0,0) to (n,n,n,n) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by less than 2 or are in the set {1,4}.

Column k=4 of A208879.

A208880 Number of words either empty or beginning with the first letter of the cyclic n-ary alphabet, where each letter of the alphabet occurs twice and letters of neighboring word positions are equal or neighbors in the alphabet.

Original entry on oeis.org

1, 1, 3, 30, 62, 114, 202, 346, 582, 966, 1590, 2602, 4242, 6898, 11198, 18158, 29422, 47650, 77146, 124874, 202102, 327062, 529254, 856410, 1385762, 2242274, 3628142, 5870526, 9498782, 15369426, 24868330, 40237882, 65106342, 105344358, 170450838, 275795338

Offset: 0

Alois P. Heinz, Mar 02 2012

The first and the last letters are considered neighbors in a cyclic alphabet. The words are not considered cyclic here.

Also the number of (2*n-1)-step walks on n-dimensional cubic lattice from (1,0,...,0) to (2,2,...,2) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by less than 2 or are in the set {1,n}.

			a(0) = 1: the empty word.
a(1) = 1 = |{aa}|.
a(2) = 3 = |{aabb, abab, abba}|.
a(3) = 30 = |{aabbcc, aabcbc, aabccb, aacbbc, aacbcb, aaccbb, ababcc, abacbc, abaccb, abbacc, abbcac, abbcca, abcabc, abcacb, abcbac, abcbca, abccab, abccba, acabbc, acabcb, acacbb, acbabc, acbacb, acbbac, acbbca, acbcab, acbcba, accabb, accbab, accbba}|.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Row n=2 of A208879.

a:= n-> `if`(n<3, 1+n*(n-1),
        (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.
         <<2, 2, 14, 30>>)[1, 1]):
seq(a(n), n=0..40);

Join[{1,1,3},LinearRecurrence[{3,-2,-1,1},{30,62,114,202},40]] (* Harvey P. Dale, Mar 09 2015 *)

G.f.: -(11*x^6-10*x^5-22*x^4+24*x^3+2*x^2-2*x+1)/((x^2+x-1)*(x-1)^2).

A209184 Number of words, either empty or beginning with the first letter of the cyclic 5-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet.

Original entry on oeis.org

1, 2, 114, 12622, 1754954, 276049002, 46957069166, 8432879950182, 1576025367484986, 303680854369601602, 59946832651601518874, 12067737101428788147678, 2469034689095701731579766, 512096607962969119056789578, 107455511844928367137882085286

Offset: 0

Alois P. Heinz, Mar 05 2012

The first and the last letters are considered neighbors in a cyclic alphabet. The words are not considered cyclic here.

a(n) is also the number of (5*n-1)-step walks on 5-dimensional cubic lattice from (1,0,...,0) to (n,n,...,n) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by less than 2 or are in the set {1,5}.

Column k=5 of A208879.

A209185 Number of words, either empty or beginning with the first letter of the cyclic 6-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet.

Original entry on oeis.org

1, 2, 202, 53768, 19341130, 8151741752, 3795394507240, 1892725627422240, 992594962274742090, 540969426319412656280, 303934170379321788972952, 175019302819674622982714912, 102858166922334018149414066152, 61493440878115135100772134725088

Offset: 0

Alois P. Heinz, Mar 05 2012

The first and the last letters are considered neighbors in a cyclic alphabet. The words are not considered cyclic here.

a(n) is also the number of (6*n-1)-step walks on 6-dimensional cubic lattice from (1,0,...,0) to (n,n,...,n) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by less than 2 or are in the set {1,6}.

Column k=6 of A208879.

cp's OEIS Frontend

A208673 Number of words A(n,k), either empty or beginning with the first letter of the k-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A208881 Number of words either empty or beginning with the first letter of the ternary alphabet, where each letter of the alphabet occurs n times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A209183 Number of words, either empty or beginning with the first letter of the cyclic 4-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet.

Views

Author

Keywords

Comments

Crossrefs

A208880 Number of words either empty or beginning with the first letter of the cyclic n-ary alphabet, where each letter of the alphabet occurs twice and letters of neighboring word positions are equal or neighbors in the alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A209184 Number of words, either empty or beginning with the first letter of the cyclic 5-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet.

Views

Author

Keywords

Comments

Crossrefs

A209185 Number of words, either empty or beginning with the first letter of the cyclic 6-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet.

Views

Author

Keywords

Comments

Crossrefs