cp's OEIS Frontend

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

%I A208675 #59 Aug 22 2025 17:18:57
%S A208675 1,1,5,37,309,2751,25493,242845,2360501,23301307,232834755,2349638259,
%T A208675 23905438725,244889453043,2523373849701,26132595017037,
%U A208675 271826326839477,2838429951771795,29740725671232119,312573076392760183,3294144659048391059,34802392680979707121
%N A208675 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 A208675 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 A208675 Alois P. Heinz, <a href="/A208675/b208675.txt">Table of n, a(n) for n = 0..960</a>
%H A208675 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 A208675 From _Michael Somos_, Jun 03 2012: (Start)
%F A208675 a(n) = A108625(n-1, n).
%F A208675 a(n) = Hypergeometric3F2([1-n, -n, n], [1, 1], 1).
%F A208675 (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 A208675 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 A208675 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 A208675 From _Peter Bala_, Apr 05 2022: (Start)
%F A208675 a(n) = Sum_{k = 0..n} binomial(n,k)*binomial(n-1,k)*binomial(n+k-1,k).
%F A208675 Using binomial(-n,k) = (-1)^k*binomial(n+k-1,k) for nonnegative k, we have:
%F A208675 a(-n) = Sum_{k = 0..n} binomial(-n,k)*binomial(-n-1,k)*binomial(-n+k-1,k).
%F A208675 a(-n) = Sum_{k = 0..n} (-1)^k* binomial(n+k-1,k)*binomial(n+k,k)*binomial(n,k)
%F A208675 a(-n) = (-1)^n*A108628(n-1), for n >= 1.
%F A208675 a(n) = Sum_{k = 1..n} binomial(n,k)*binomial(n-1,k-1)*binomial(n+k-1,k-1) for n >= 1.
%F A208675 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 A208675 a(n) = Sum_{k = 0..n-1} (-1)^k*binomial(n-1,k)*binomial(2*n-k-1,n-k)^2.
%F A208675 a(n) = (1/5)*(A005258(n) + 2*A005258(n-1)) for n >= 1.
%F A208675 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 A208675 a(n) = B(n,n-1,n-1) in the notation of Straub, equation 24. Hence
%F A208675 a(n) = [(x^n)*(y*z)^(n-1)] 1/(1 - x - y - z + x*z + y*z - x*y*z) for n >= 1.
%F A208675 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 A208675 Conjectures:
%F A208675 1) a(n) = [(x*y)^n*z^(n-1)] 1/(1 - x - y - z + x*y + x*y*z) for n >= 1.
%F A208675 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 A208675 3) a(n) = [x^(n-1)*(y*z)^n] 1/(1 - x - x*y - y*z - x*z - x*y*z) for n >= 1. (End)
%F A208675 From _Peter Bala_, Mar 17 2023: (Start)
%F A208675 For n >= 1:
%F A208675 a(n) = Sum_{k = 0..n} ((n-k)/(n+k))*binomial(n,k)^2*binomial(n+k,k).
%F A208675 a(n) = Sum_{k = 0..n} (-1)^(n+k-1) * ((n-k)/(n+k)) * binomial(n,k) * binomial(n+k,k)^2. (End)
%e A208675 a(2) = 5 = |{aabbcc, aabcbc, aabccb, ababcc, abccba}|.
%e A208675 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 A208675 a:= n-> add(binomial(n-1, k)^2 *binomial(2*n-1-k, n-k), k=0..n):
%p A208675 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jun 26 2012
%t A208675 a[n_]:= HypergeometricPFQ[{1-n,-n,n}, {1,1}, 1] (* _Michael Somos_, Jun 03 2012 *)
%o A208675 (Magma)
%o A208675 A208675:= func< n | (&+[Binomial(n,j)*Binomial(n-1,j)*Binomial(n+j-1,j): j in [0..2*n]]) >;
%o A208675 [A208675(n): n in [0..30]]; // _G. C. Greubel_, Oct 05 2023
%o A208675 (SageMath)
%o A208675 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 [A208675(n) for n in range(31)] # _G. C. Greubel_, Oct 05 2023
%Y A208675 Column k=3 of A208673.
%Y A208675 Cf. A000108, A001622, A005258, A108625, A108628, A271777.
%K A208675 nonn,easy
%O A208675 0,3
%A A208675 _Alois P. Heinz_, Feb 29 2012