login
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.
15

%I #42 Apr 06 2023 10:56:24

%S 1,1,9,163,3593,87501,2266155,61211095,1704838665,48605519665,

%T 1411522695509,41606511550803,1241591466423467,37435593955828069,

%U 1138713916992923679,34901292375152457663,1076813644170756916745,33416749492077957930105,1042376218505671236116985

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

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

%C It appears that for primes p >= 5, a(p) == 1 (mod p^5). Cf. A352655. - _Peter Bala_, Dec 12 2021

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

%H Alois P. Heinz, <a href="/A212334/b212334.txt">Table of n, a(n) for n = 0..656</a>

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

%F From _Peter Bala_, Apr 17 2022: (Start)

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

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

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

%F (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)

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

%p a:= proc(n) option remember; `if`(n<3, [1, 1, 9][n+1],

%p ((26682*n^4 -102687*n^3 +149385*n^2 -109413*n +31101) *a(n-1)

%p +(-161058*n^4 +1392915*n^3 -4418826*n^2 +6030348*n -2931516) *a(n-2)

%p +(4718*n^4 -47957*n^3 +176841*n^2 -275751*n +148365) *a(n-3)) /

%p (n^3 *(646*n -1057)))

%p end:

%p seq(a(n), n=0..30);

%t 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))];

%t a /@ Range[0, 30] (* _Jean-François Alcover_, May 14 2020, after Maple *)

%Y Column k = 4 of A208673.

%Y Cf. A005259, A352655.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Aug 07 2012