A177316 Number of permutations of n copies of 1..4 with all adjacent differences <= 1 in absolute value.

1, 2, 26, 506, 11482, 284002, 7426610, 201922730, 5650739930, 161686253810, 4708709084026, 139111173397066, 4159013698117618, 125595645802182818, 3825428523179727266, 117382025506323434506, 3625185567639373456090, 112597953571519245194770

Offset

0,2

Comments

See A103882 and A177317 through A177328 for the number of permutations of n copies of 1..k (for different values of k) with adjacent differences restricted in size. We conjecture that all these sequences satisfy the congruences A(n*p^k) == A(n*p^(k-1)) ( mod p^(3*k) ) for all positive integers n and k and any prime p >= 5. - Peter Bala, Jan 16 2020

Links

Alois P. Heinz, Table of n, a(n) for n = 0..656 (terms n=1..31 from R. H. Hardin)

Formula

From Peter Bala, Jan 14 2020: (Start)

Conjecture: a(n) = (1/3)*( A005259(n) + A005259(n-1) ).

Equivalently, a(n) = Sum_{k = 0..n} binomial(n,k)^2*binomial(n+k-1,k)^2. Cf. A103882. If true, then the sequence satisfies the recurrence a(n) = (2*(102*n^6 - 612*n^5 + 1462*n^4 - 1768*n^3 + 1143*n^2 - 382*n+52) * a(n-1) - (2*n-1)*(3*n^2 - 3*n+1) * (n-2)^3 * a(n-2)) / (n^3*(2*n - 3) * (3*n^2 - 9*n+7)) and the supercongruences a(n*p^k) == a(n*p^(k-1)) ( mod p^(3*k) ) for all positive integers n and k and any prime p >= 5. [added Apr 18 2022: assuming the recurrence given in the Maple program below is correct then these conjectures are true.] (End)

a(n) = 2*A352653(n) for n >= 1. - Peter Bala, Apr 18 2022

a(n) = hypergeom([-n, -n, n, n], [1, 1, 1], 1). - Peter Luschny, Mar 27 2023

a(n) ~ (1 + sqrt(2))^(4*n) / (2^(5/4) * Pi^(3/2) * n^(3/2)). - Vaclav Kotesovec, Mar 29 2023

Maple

a:= proc(n) option remember; `if`(n<3, [1, 2, 26][n+1],
       (3*((105*n^4-356*n^3+402*n^2-208*n+43)*a(n-1)
      -(105*n^4-904*n^3+2868*n^2-3932*n+1930)*a(n-2))
      +(9*n-11)*(n-3)^3*a(n-3))/((9*n-16)*n^3))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Jan 22 2020
A177316 := n -> hypergeom([-n, -n, n, n], [1, 1, 1], 1):
seq(simplify(A177316(n)), n = 0..17); # Peter Luschny, Mar 27 2023

Mathematica

a[n_] := HypergeometricPFQ[{-n, -n, n, n}, {1, 1, 1}, 1];
Table[a[n], {n, 0, 17}] (* Jean-François Alcover, May 28 2023, after Peter Luschny *)

Prog

(Python)
def A177316(n):
    if n == 0: return 1
    m, g = 1, 0
    for k in range(n+1):
        g += m*n**2//(n+k)**2
        m *= ((n+k+1)*(n-k))**2
        m //= (k+1)**4
    return g # Chai Wah Wu, Oct 03 2022

Crossrefs

Cf. A005259, A103882, A177317 - A177328, A352653.

Row n=4 of A331562.

Sequence in context: A371700 A364196 A216254 * A255538 A302719 A090247

Adjacent sequences: A177313 A177314 A177315 * A177317 A177318 A177319

Keyword

nonn

Author

R. H. Hardin, May 06 2010

Extensions

a(0)=1 prepended by Alois P. Heinz, Jan 20 2020

Status

approved