A177322 Number of permutations of n copies of 1..4 with all adjacent differences <= 2 in absolute value.
1, 12, 660, 51240, 4635540, 457507512, 47768769048, 5188083048720, 580132098966420, 66341857216154520, 7722843117550721160, 912113857017595941072, 109025503164832356811800, 13164173606420256001705200, 1603262885152270822600633200, 196721396289915224779758846240
Offset: 0
Keywords
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..471 (terms n=1..35 from R. H. Hardin)
Formula
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
Extensions
a(0)=1 prepended by Alois P. Heinz, Jun 07 2025