A212334 Number of words, either empty or beginning with the first letter of the 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.

1, 1, 9, 163, 3593, 87501, 2266155, 61211095, 1704838665, 48605519665, 1411522695509, 41606511550803, 1241591466423467, 37435593955828069, 1138713916992923679, 34901292375152457663, 1076813644170756916745, 33416749492077957930105, 1042376218505671236116985

Offset: 0

Author

Alois P. Heinz, Aug 07 2012

Keywords

• nonn

Comments

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 absolute difference of the dimension indices used in consecutive steps is <= 1.

It appears that for primes p >= 5, a(p) == 1 (mod p^5). Cf. A352655. - Peter Bala, Dec 12 2021

Conjecture: for r >= 2, and all primes p >= 5, a(p^r) == a(p^(r-1)) (mod p^(3*r+3)). - Peter Bala, Oct 13 2022

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..656

Crossrefs

Column k = 4 of A208673.

Cf. A005259, A352655.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, [1, 1, 9][n+1],
      ((26682*n^4 -102687*n^3 +149385*n^2 -109413*n +31101) *a(n-1)
      +(-161058*n^4 +1392915*n^3 -4418826*n^2 +6030348*n -2931516) *a(n-2)
      +(4718*n^4 -47957*n^3 +176841*n^2 -275751*n +148365) *a(n-3)) /
      (n^3 *(646*n -1057)))
    end:
seq(a(n), n=0..30);

Mathematica

a[n_] := a[n] = If[n < 3, {1, 1, 9}[[n + 1]], ((26682 n^4 - 102687 n^3 + 149385 n^2 - 109413 n + 31101) a[n-1] + (-161058 n^4 + 1392915 n^3 - 4418826 n^2 + 6030348 n - 2931516)a[n-2] + (4718 n^4 - 47957 n^3 + 176841 n^2 - 275751 n + 148365)a[n-3])/(n^3 (646 n - 1057))];
a /@ Range[0, 30] (* Jean-François Alcover, May 14 2020, after Maple *)

Formula

a(n) ~ (1 + sqrt(2))^(4*n-1) / (2^(7/4) * (Pi*n)^(3/2)). - Vaclav Kotesovec, Aug 13 2013, simplified Apr 06 2022

From Peter Bala, Apr 17 2022: (Start)

a(n) = (1/12)*(A005259(n) + 7*A005259(n-1)) for n >= 1.

The supercongruences a(n*p^k) == a(n*p^(k-1)) (mod p^(3*k)) hold for all primes p >= 5 and positive integers n and k.

a(n) = (1/3)*Sum_{k = 0..n} binomial(n,k)^2*binomial(n + k,k)^2*(2*n^2 - 3*k*n + 2*k^2)/(n + k)^2.

(24*n^3 - 102*n^2 + 148*n - 73)*n^3*a(n) = 4*(204*n^6 - 1173*n^5 + 2668*n^4 - 3065*n^3 + 1905*n^2 - 634*n + 86)*a(n-1) - (24*n^3 - 30*n^2 + 16*n-3)*(n - 2)^3*a(n-2) with a(0) = a(1) = 1. (End)

a(n) = Sum_{k=0..n-1} binomial(n,k)*binomial(n-1,k)*binomial(n+k-1,k)^2 for n>=1. - Peter Bala, Mar 22 2023