A177317 -id:A177317 - cp's OEIS frontend

A331562 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding absolute differences between adjacent elements larger than one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 6, 2, 1, 1, 1, 20, 12, 2, 1, 1, 1, 70, 92, 26, 2, 1, 1, 1, 252, 780, 506, 48, 2, 1, 1, 1, 924, 7002, 11482, 2288, 86, 2, 1, 1, 1, 3432, 65226, 284002, 135040, 10010, 148, 2, 1, 1, 1, 12870, 623576, 7426610, 8956752, 1543862, 41618, 250, 2, 1

Offset: 0

Alois P. Heinz, Jan 20 2020

All columns are linear recurrences with constant coefficients and for k > 0 the order of the recurrence is bounded by 3*k-1. For k up to at least 17 this upper bound is exact. - Andrew Howroyd, May 16 2020

Row 2, the sequence of central binomial numbers A000984, satisfies the supercongruences u(n*p^r) == u(n*p^(r-1)) (mod p^(3*r)) for all primes p >= 5 and all positive integers n and r (see Meštrović, equation 39). This is also known to be true for row 3 (A103882) and row 4 (A177316). We conjecture that each row sequence of the table satisfies the same congruences. - Peter Bala, Oct 26 2024.

			A(2,2) = 6: 1122, 1212, 1221, 2112, 2121, 2211.
A(3,2) = 12: 112233, 112323, 112332, 121233, 123321, 211233, 233211, 321123, 323211, 332112, 332121, 332211.
A(2,3) = 20: 111222, 112122, 112212, 112221, 121122, 121212, 121221, 122112, 122121, 122211, 211122, 211212, 211221, 212112, 212121, 212211, 221112, 221121, 221211, 222111.
A(3,3) = 92: 111222333, 111223233, 111223323, 111223332, ..., 333221112, 333221121, 333221211, 333222111.
Square array A(n,k) begins:
  1, 1,  1,     1,       1,         1,           1, ...
  1, 1,  1,     1,       1,         1,           1, ...
  1, 2,  6,    20,      70,       252,         924, ...
  1, 2, 12,    92,     780,      7002,       65226, ...
  1, 2, 26,   506,   11482,    284002,     7426610, ...
  1, 2, 48,  2288,  135040,   8956752,   640160976, ...
  1, 2, 86, 10010, 1543862, 276285002, 54331653686, ...

Andrew Howroyd, Antidiagonals n = 0..50, flattened (antidiagonals 0..15 from Alois P. Heinz)
Romeo Meštrović, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862-2012), arXiv:1111.3057 [math.NT], (2011).

Columns k=0-9 give: A000012, A130130 (for n>0), A177282, A177291, A177298, A177301, A177304, A177307, A177310, A177313.
Rows n=0+1, 2-9 give: A000012, A000984, A103882, A177316, A177317, A177318, A177319, A177320, A177321.
Main diagonal gives A331623.
Cf. A269129, A275784.

b:= proc(l, q) option remember; (n-> `if`(n<2, 1, add(
     `if`(l[j]=1, `if`(j in [1, n], b(subsop(j=[][], l),
     `if`(j=1, 0, n)), 0), b(subsop(j=l[j]-1, l), j)), j=
     `if`(q<0, 1..n, max(1, q-1)..min(n, q+1)))))(nops(l))
    end:
A:= (n, k)-> `if`(k=0, 1, b([k$n], -1)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[l_, q_] := b[l, q] = With[{n = Length[l]}, If[n < 2, 1, Sum[
      If[l[[j]] == 1, If[j == 1 || j == n, b[ReplacePart[l, j -> Nothing],
      If[j == 1, 0, n]], 0], b[ReplacePart[l, j -> l[[j]] - 1], j]], {j,
      If[q < 0, Range[n], Range[Max[1, q - 1], Min[n, q + 1]]]}]]];
A[n_, k_] := If[k == 0, 1, b[Table[k, {n}], -1]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

step(m,R)={my(M=matrix(3, m+1, q, p, q--; p--; sum(j=0, m-p-q, sum(i=max(p+j-#R+1, 2*p+q+j-m), p, R[1+q, 1+p+j-i] * binomial(p,i) * binomial(p+q+j-i-1, j) * binomial(m-1, 2*p+q+j-i-1))))); M[3,]+=2*M[2,]+M[1,]; M[2,]+=M[1,]; M}
AdjPathsBySig(sig)={if(#sig<1, 1, my(R=[1;1;1]); for(i=1, #sig-1, R=step(sig[i], R)); my(m=sig[#sig]); sum(i=1, min(m, #R), binomial(m-1, i-1)*R[3,i]))}
T(n,k) = {if(k==0, 1, AdjPathsBySig(vector(n,i,k)))} \\ Andrew Howroyd, May 16 2020

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

Original entry on oeis.org

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

Offset: 0

R. H. Hardin, May 06 2010

nonn

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

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

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

Row n=4 of A331562.

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

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 *)

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

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

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

cp's OEIS Frontend

A331562 Number A(n,k) of sequences with k copies each of 1,2,...,n avoiding absolute differences between adjacent elements larger than one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI