login
Number of words, either empty or beginning with the first letter of the ternary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet.
9

%I #53 Oct 06 2023 11:04:25

%S 1,1,5,37,309,2751,25493,242845,2360501,23301307,232834755,2349638259,

%T 23905438725,244889453043,2523373849701,26132595017037,

%U 271826326839477,2838429951771795,29740725671232119,312573076392760183,3294144659048391059,34802392680979707121

%N Number of words, either empty or beginning with the first letter of the ternary 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 (3*n-1)-step walks on 3-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.

%H Alois P. Heinz, <a href="/A208675/b208675.txt">Table of n, a(n) for n = 0..300</a>

%H Armin Straub, <a href="http://dx.doi.org/10.2140/ant.2014.8.1985">Multivariate Apéry numbers and supercongruences of rational functions</a>, Algebra & Number Theory, Vol. 8, No. 8 (2014), pp. 1985-2008; <a href="https://arxiv.org/abs/1401.0854">arXiv preprint</a>, arXiv:1401.0854 [math.NT], 2014.

%F From _Michael Somos_, Jun 03 2012: (Start)

%F a(n) = A108625(n-1, n).

%F a(n) = Hypergeometric3F2([1-n, -n, n], [1, 1], 1).

%F (n+1)^2 * (1 -4*n +5*n^2) * a(n+1) = (5 -5*n -26*n^2 +11*n^3 +55*n^4) * a(n) + (n-1)^2 * (2 +6*n +5*n^2) * a(n-1). (End)

%F a(n) ~ sqrt((5-sqrt(5))/10)/(2*Pi*n) * ((1+sqrt(5))/2)^(5*n). - _Vaclav Kotesovec_, Dec 06 2012. Equivalently, a(n) ~ phi^(5*n - 1/2) / (2 * 5^(1/4) * Pi * n), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, Dec 07 2021

%F exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 3*x^2 + 15*x^3 + 94*x^4 + 668*x^5 + 5144*x^6 + 41884*x^7 + 355307*x^8 + ... appears to have integer coefficients. Cf. A108628. - _Peter Bala_, Jan 12 2016

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

%F a(n) = Sum_{k = 0..n} binomial(n,k)*binomial(n-1,k)*binomial(n+k-1,k).

%F Using binomial(-n,k) = (-1)^k*binomial(n+k-1,k) for nonnegative k, we have:

%F a(-n) = Sum_{k} binomial(-n,k)*binomial(-n-1,k)*binomial(-n+k-1,k).

%F a(-n) = Sum_{k} (-1)^k* binomial(n+k-1,k)*binomial(n+k,k)*binomial(n,k)

%F a(-n) = (-1)^n*A108628(n-1),

%F for n >= 1.

%F a(n) = Sum_{k = 1..n} binomial(n,k)*binomial(n-1,k-1)*binomial(n+k-1,k-1) for n >= 1.

%F Equivalently, a(n) = [(x^n)*(y*z)^(n-1)] (x + y + z)^n*(x + y)^(n-1)*(y + z)^(n-1) for n >= 1.

%F a(n) = Sum_{k = 0..n-1} (-1)^k*binomial(n-1,k)*binomial(2*n-k-1,n-k)^2.

%F a(n) = (1/5)*(A005258(n) + 2*A005258(n-1)) for n >= 1.

%F a(n) = [x^n] 1/(1 - x)*P(n-1,(1 + x)/(1 - x)) for n >= 1, where P(n,x) denotes the n-th Legendre polynomial. Compare with A005258(n) = [x^n] 1/(1 - x)*P(n,(1 + x)/(1 - x)).

%F a(n) = B(n,n-1,n-1) in the notation of Straub, equation 24. Hence

%F a(n) = [(x^n)*(y*z)^(n-1)] 1/(1 - x - y - z + x*z + y*z - x*y*z) 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 all positive integers n and k.

%F Conjectures:

%F 1) a(n) = [(x*y)^n*z^(n-1)] 1/(1 - x - y - z + x*y + x*y*z) for n >= 1.

%F 2) a(n) = - [(x*z)^(n-1)*(y^n)] 1/(1 + y + z + x*y + y*z + x*z + x*y*z) for n >= 1.

%F 3) a(n) = [x^(n-1)*(y*z)^n] 1/(1 - x - x*y - y*z - x*z - x*y*z) for n >= 1.

%F (End)

%F From _Peter Bala_, Mar 17 2023: (Start)

%F For n >= 1:

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

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

%e a(2) = 5 = |{aabbcc, aabcbc, aabccb, ababcc, abccba}|.

%e a(3) = 37 = |{aaabbbccc, aaabbcbcc, aaabbccbc, aaabbcccb, aaabcbbcc, aaabcbcbc, aaabcbccb, aaabccbbc, aaabccbcb, aaabcccbb, aababbccc, aababcbcc, aababccbc, aababcccb, aabbabccc, aabbcccba, aabcbabcc, aabcbccba, aabccbabc, aabccbcba, aabcccbab, aabcccbba, abaabbccc, abaabcbcc, abaabccbc, abaabcccb, abababccc, ababcccba, abbaabccc, abbcccbaa, abcbaabcc, abcbccbaa, abccbaabc, abccbcbaa, abcccbaab, abcccbaba, abcccbbaa}|.

%p a:= n-> add(binomial(n-1, k)^2 *binomial(2*n-1-k, n-k), k=0..n):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jun 26 2012

%t a[n_]:= HypergeometricPFQ[{1-n,-n,n}, {1,1}, 1] (* _Michael Somos_, Jun 03 2012 *)

%o (Magma)

%o A208675:= func< n | (&+[Binomial(n,j)*Binomial(n-1,j)*Binomial(n+j-1,j): j in [0..2*n]]) >;

%o [A208675(n): n in [0..30]]; // _G. C. Greubel_, Oct 05 2023

%o (SageMath)

%o def A208675(n): return sum(binomial(n,j)*binomial(n-1,j)*binomial(n+j-1,j) for j in range(n+1))

%o [A208675(n) for n in range(31)] # _G. C. Greubel_, Oct 05 2023

%Y Column k=3 of A208673.

%Y Cf. A000108, A001622, A005258, A108625, A108628, A271777.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Feb 29 2012