A177316 -id:A177316 - 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

A103882 a(n) = Sum_{i=0..n} C(n+1,i)C(n-1,i-1)C(2n-i,n).

Original entry on oeis.org

1, 2, 12, 92, 780, 7002, 65226, 623576, 6077196, 60110030, 601585512, 6078578508, 61908797418, 634756203018, 6545498596110, 67830161708592, 705951252118284, 7375213677918294, 77310179609631564, 812839595630249540, 8569327862277434280, 90562666977432643862

Offset: 0

Ralf Stephan, Feb 20 2005

Number of permutations of n copies of 1..3 with all adjacent differences <= 1 in absolute value. - R. H. Hardin, May 06 2010 [Cf. A177316. - Peter Bala, Jan 14 2020]

Alois P. Heinz, Table of n, a(n) for n = 0..950 (terms n=1..94 from R. H. Hardin)
A. Straub, Multivariate Apéry numbers and supercongruences of rational functions, arXiv:1401.0854 [math.NT] (2014).

Cf. A005258, A156554, A177316, A352654.
Equals A103881(n, n).
Row n=3 of A331562.

[1] cat [&+[Binomial(n+1, i)*Binomial(n-1, i-1) * Binomial(2*n-i, n): i in [0..n]]:n in  [1..21]]; // Marius A. Burtea, Jan 19 2020

[&+[Binomial(n, k)^2*Binomial(n+k-1, k): k in [0..n]]:n in  [0..21]]; // Marius A. Burtea, Jan 19 2020

a:= proc(n) option remember; `if`(n<2, n+1,
      ((n-1)*(55*n^3-143*n^2+102*n-24)*a(n-1)+
      n*(5*n-3)*(n-2)^2*a(n-2))/((n-1)*(5*n-8)*n^2))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 29 2015
# Alternative:
a := n -> hypergeom([-n, -n, n], [1, 1], 1):
seq(simplify(a(n)), n=0..21); # Peter Luschny, Jan 19 2020

Drop[Table[Sum[Sum[Multinomial[r, g, n + 1 - r - g] Binomial[n - 1,n - r] Binomial[n - 1, n - g], {g, 1, n}], {r, 1, n}], {n, 0, 18}], 1] (* Geoffrey Critzer, Jun 29 2015 *)
Table[Sum[Binomial[n+1,k]Binomial[n-1,k-1]Binomial[2n-k,n],{k,0,n}],{n,0,30}] (* Harvey P. Dale, Jun 19 2021 *)

a(n) = polcoef(pollegendre(n, (1 + x)/(1 - x)) + O(x^(n+1)), n); \\ Michel Marcus, Dec 20 2020

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

def A103882(n): return hypergeometric([-n,-n,n], [1,1], 1).simplify()
[A103882(n) for n in range(31)] # G. C. Greubel, May 24 2023

a(n) = (A005258(n-1) + 3*A005258(n))/5 (Apéry numbers). - Mark van Hoeij, Jul 13 2010
n^2*(n-1)*(5*n-8)*a(n) = (n-1)*(55*n^3-143*n^2+102*n-24)*a(n-1) + n*(n-2)^2*(5*n-3)*a(n-2). - Alois P. Heinz, Jun 29 2015
a(n) ~ phi^(5*n + 3/2) / (2*Pi*5^(1/4)*n), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Jul 21 2019
From Peter Bala, Jan 14 2020: (Start)
a(n) = Sum_{k = 0..n} C(n,k)^2*C(n+k-1,k). Cf. A005258.
For any prime p >= 5, a(n*p^k) == a(n*p^(k-1)) ( mod p^(3*k) ) for all positive integers n and k (follows from known supercongruences satisfied by the Apéry numbers A005258 - see Straub, Example 3.4). (End)
a(n) = hypergeometric([-n, -n, n], [1, 1], 1). - Peter Luschny, Jan 19 2020
From Peter Bala, Dec 19 2020: (Start)
a(n) = Sum_{k = 1..n} C(n,k)*C(n+k,k)*C(n-1,k-1) for n >= 1.
a(n) = [x^n] P(n, (1 + x)/(1 - x)), where P(n,x) denotes the n-th Legendre polynomial. Cf. A156554. (End)
a(n) = Sum_{k = 0..n} binomial(2*n-k-1,n-k)*binomial(n,k)^2. Cf. A108628. - Peter Bala, Mar 24 2022
From Peter Bala, Apr 15 2022: (Start)
a(-n) = (-1)^n*A352654(n).
a(n) = [x^n*y^n*z^(n-1)] 1/(1 - x - y - z + x*z + y*z - x*y*z) for n >= 1.
a(n) = B(n,n,n-1) in the notation of Straub, see equation 24.
a(n) = [x^n*y^n*z^(n-1)] (x + y + z)^n*(x + y)^n*(y + z)^(n-1) for n >= 1. (End)
D-finite with recurrence 9*n^2*a(n) -3*(31*n^2-27*n+6)*a(n-1) -2*(37*n^2-138*n+108)*a(n-2) -(n-3)*(17*n-56)*a(n-3) -(n-4)^2*a(n-4) = 0. - R. J. Mathar, Aug 01 2022
a(n) = Sum_{k = 0..n} (-1)^(n+k) * binomial(n-1, n-k)*binomial(n+k, k)*binomial(n+k-1, k). - Peter Bala, Aug 13 2023
a(n) = Sum_{k = 0..n} (-1)^k * binomial(n+1, k)*binomial(2*n-k, n-k)^2. - Peter Bala, Oct 05 2024

a(0)=1 prepended by Alois P. Heinz, Jun 29 2015

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

Original entry on oeis.org

0, 1, 17, 406, 10257, 268126, 7213166, 198978074, 5609330705, 161095277710, 4700175389142, 138986764820410, 4157185583199534, 125568602682092818, 3825026187780837266, 117376010145070696906, 3625095243230562818065, 112596592142021739522670, 3514965607470183733302470

Offset: 0

Peter Bala, Mar 21 2023

Conjecture 1: the supercongruence a(p) == a(1) (mod p^5) holds for all primes p >= 7 (checked up to p = 199).
Conjecture 2: for r >= 2, the supercongruence a(p^r) == a(p^(r-1)) (mod p^(4*r+1)) holds for all primes p >= 7.
Compare with the Apéry numbers A005259(n) = Sum_{k = 0..n} binomial(n,k)^2 * binomial(n+k,k)^2, which satisfy the weaker supercongruences A005259(p^r) == A005259(p^(r-1)) (mod p^(3*r)) for all positive integers r and all primes p >= 5.

Paolo Xausa, Table of n, a(n) for n = 0..650
Peter Bala, Recurrence equation for A361713

Cf. A005259, A060150, A177316, A212334, A361712, A361714, A361715, A361717.

seq(add(binomial(n,k)^2*binomial(n+k-1,k)^2, k = 0..n-1), n = 0..25);
# Alternative:
A361713 := n -> hypergeom([-n, -n, n, n], [1, 1, 1], 1) - binomial(2*n - 1, n)^2:
seq(simplify(A361713(n)), n = 0..18); # Peter Luschny, Mar 27 2023

A361713[n_] := HypergeometricPFQ[{-n, -n, n, n}, {1, 1, 1}, 1] - Binomial[2*n-1, n]^2; Array[A361713, 20, 0] (* Paolo Xausa, Jul 11 2024 *)

a(n) = (1/3)*(A005259(n) + A005259(n-1)) - (1/4)*binomial(2*n,n)^2 = A177316(n) - A060150(n).
a(n) ~ C*(12*sqrt(2) + 17)^n/n^(3/2), where C = 1/(2^(5/4)*Pi^(3/2)).
a(n) = hypergeom([-n, -n, n, n], [1, 1, 1], 1) - binomial(2*n-1, n)^2. This is another way to write the first formula. - Peter Luschny, Mar 27 2023

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

Original entry on oeis.org

0, 1, 13, 253, 5741, 142001, 3713305, 100961365, 2825369965, 80843126905, 2354354542013, 69555586698533, 2079506849058809, 62797822901091409, 1912714261589863633, 58691012753161717253, 1812592783819686728045, 56298976785759622597385, 1757493098495181029912485

Offset: 0

Peter Bala, Apr 06 2022

Compare with A005259(n) = Sum_{k = 0..n} binomial(n,k)^2*binomial(n+k,k)^2.
Main superdiagonal (or main subdiagonal) of the symmetric square array A143007.
This is the sequence (A(n,n-1,n,n-1)) in the notation of Straub 2014, where it is proved that the supercongruences a(n*p^r) == a(n*p^(r-1)) (mod p^(3*r)) hold for all primes p >= 5 and all positive integers n and r.
More generally, for nonnegative integers A, B and C with A >= 2 let S(n;A,B,C) = Sum_{k = 1..n} binomial(n,k)^A * binomial(n+k-1,k-1)^B * binomial(2*k,n)^C. Then we conjecture the sequence (S(n;A,B,C))n>=1 satisfies the same supercongruences. This is the case A = B = 2, C = 0. Compare with Osburn et al., Theorem 1.2.

			Examples of supercongruences:
a(11) - a(1) = 69555586698533 - 1 = (2^2)*(11^3)*1321*2521*3923 == 0 (mod 11^3).
a(2*7) - a(2) = 1912714261589863633 - 13 = (2^2)*(3^2)*5*(7^3)*776221* 39911503 == 0 (mod 7^3).

Robert Osburn, Brundaban Sahu and Armin Straub, Supercongruences for sporadic sequences, arXiv:1312.2195 [math.NT], 2013-2014.
Armin Straub, Multivariate Apéry numbers and supercongruences of rational functions, Algebra & Number Theory, Vol. 8, No. 8 (2014), pp. 1985-2008; arXiv preprint, arXiv:1401.0854 [math.NT], 2014.
Eric Weisstein's World of Mathematics, Strehl identities

Cf. A002002, A005259, A108628, A143007, A177316.

seq(add(binomial(n,k)^2*binomial(n+k-1,k-1)^2, k = 1..n), n = 0..20);

a[n_] := n^2 HypergeometricPFQ[{1 - n, 1 - n, 1 + n, 1 + n}, {1, 2, 2}, 1];
Table[a[n], {n, 0, 18}] (* Peter Luschny, Apr 17 2022 *)

a(n) = sum(k=1, n, binomial(n,k)^2*binomial(n+k-1,k-1)^2); \\ Michel Marcus, Apr 19 2022

def A352653(n):
    if n == 0: return 0
    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>>1 # Chai Wah Wu, Oct 03 2022

The sequence can be extended to negative values of n:
a(-n) = Sum_{k} binomial(-n,k)*binomial(-n+k,k)*binomial(-n-1,k)*binomial(-n-1+k,k) = a(n), since binomial(-m,k) = (-1)^k*binomial(m+k-1,k) for nonnegative k.
a(n) = A177316(n)/2 for n >= 1.
a(n) = Sum_{k = 1..n} binomial(n,k)^2*binomial(n+k-1,k-1)^2.
a(n) = (1/2)*Sum_{k = 0..n} binomial(n,k)^2*binomial(n+k-1,k)^2 for n >= 1.
a(n) = hypergeom([n, n+1, -n, -n+1], [1, 1, 1], 1) for n >= 1.
a(n) = (1/2)*hypergeom([n, n, -n, -n], [1, 1, 1], 1) for n >= 1.
a(n) = (1/4)*binomial(2*n,n)^2*hypergeom([-n+1, -n+1, -n, -n], [1, -2*n+1, -2*n+1], 1) for n >= 1
a(n) = [x^n*y^(n-1)*z^n*t^(n-1)] 1/((1 - x - y)(1 - z - t) - x*y*z*t).
a(n) = [x^n] 1/(1 - x) * P(n-1,(1 + x)/(1 - x))^2 = [x^(n-1)] 1/(1 - x) * P(n,(1 + x)/(1 - x))^2 for n >= 1, where P(n,x) denotes the n-th Legendre polynomial. Cf. A005259(n) = [x^n] 1/(1 - x) * P(n,(1 + x)/(1 - x))^2.
(n + 1)^3*(2*n - 1)(3*n^2 - 3*n + 1)*a(n+1) = 2*(102*n^6 - 68*n^4 + 21*n^2 - 3)*a(n) - (n - 1)^3*(2*n + 1)*(3*n^2 + 3*n + 1)*a(n-1) with a(0) = 0 and a(1) = 1.
The Gauss congruences a(n*p^r) == a(n*p^(r-1)) (mod p^r) hold for all primes p and all positive integers n and r. It follows that the expansion of exp( Sum_{n >= 1} a(n)/n*x^n ) = 1 + x + 7*x^2 + 91*x^3 + 1544*x^4 + 30448*x^5 + 661506*x^6 + 15377010*x^7 + ... has integer coefficients.
a(n) = n^2*hypergeom([1 - n, 1 - n, 1 + n, 1 + n], [1, 2, 2], 1). - Peter Luschny, Apr 17 2022
From Peter Bala, Mar 18 2023: (Start)
a(n) = Sum_{k = 0..n-1} (n-k)/(n+k) * binomial(n,k)^2 * binomial(n+k,k)^2.
a(n) = 1/6*(A005259(n) + A005259(n-1)). (End)
a(n) ~ (1 + sqrt(2))^(4*n) / (2^(9/4) * Pi^(3/2) * n^(3/2)). - Vaclav Kotesovec, Mar 29 2023
a(n) = (1/3)*Sum_{k = 0..n} binomial(n,k)*binomial(n+k-1,k)*f(k) for n >= 1, where f(n) = A000172(n) denotes the n-th Franel number. Cf. A005259(n) = Sum_{k = 0..n} binomial(n,k)*binomial(n+k,k)*f(k) (the second Strehl identity). - Peter Bala, Jun 26 2023
a(n) = Sum_{0 <= j <= k <= n} (-1)^(n+k)*binomial(n, k)*binomial(n+k, k)* binomial(n+j-1, j)^2*binomial(n-1, k-j) = Sum_{k = 0..n} (-1)^(n+k)*binomial(n, k)*binomial(n+k, k)*A108625(n-1, k). Cf. Sum_{k = 0..n} (-1)^(n+k)*binomial(n, k)*binomial(n+k, k)*A108625(n, k) = A005259(n). - Peter Bala, Sep 22 2024

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

Original entry on oeis.org

1, 12, 660, 51240, 4635540, 457507512, 47768769048, 5188083048720, 580132098966420, 66341857216154520, 7722843117550721160, 912113857017595941072, 109025503164832356811800, 13164173606420256001705200, 1603262885152270822600633200, 196721396289915224779758846240

Offset: 0

R. H. Hardin, May 06 2010

nonn

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

Cf. A050983. A177316 - A177328, A156554.

From Peter Bala, Nov 05 2024: (Start)
The following are conjectural:
For n >= 1, a(n) = Sum_{k = 0..2*n} (-1)^(n+k) * (k/n)^2 * binomial(2*n, k)^4. Cf. the identity Sum_{k = 0..2*n} (-1)^(n+k) * (k/n) * binomial(2*n, k)^2 = binomial(2*n, n) = A000984(n) for n >= 1.
For n >= 1, a(n) = 2 * binomial(2*n, n) * Sum_{k = 0..n} (k/n) * binomial(2*n, n-k)^2 * binomial(2*n+k, k).
P-recursive: n^3*(2*n-1)*(n-1)*(24*n^3-105*n^2+152*n-73)*a(n) = 2*(n-1)*(3264*n^7-20808*n^6+53900*n^5-73159*n^4+55963*n^3-24107*n^2+5436*n-504)*a(n-1) - 4*(2*n-1)*(24*n^3-33*n^2+14*n-2)*(2*n-3)^2*(n-2)^2*a(n-2) with a(1) = 12 and a(0) = 1.
The supercongruences a(n*p^r) == a(n*p^(r-1)) (mod p^(3*r)) hold for all primes p >= 5 and all positive integers n and r. (End)
a(n) = A156554(n) * A000984(n). A156554 counts ways to place 1s and 4s in the permutation; a positive (resp. negative) sequence element in A156554 is a run-length of 1s (resp. 4s) followed by a 2 or 3 or the end of the permutation. Each zero in A156554 corresponds to an additional 2 or 3 in the permutation. - Martin Fuller, Jun 07 2025

a(0)=1 prepended by Alois P. Heinz, Jun 07 2025

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

A103882 a(n) = Sum_{i=0..n} C(n+1,i)*C(n-1,i-1)*C(2n-i,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

Python

SageMath

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A177326 Number of permutations of n copies of 1..5 with all adjacent differences <= 3 in absolute value.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A103882 a(n) = Sum_{i=0..n} C(n+1,i)C(n-1,i-1)C(2n-i,n).

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