A002464 -id:A002464 - cp's OEIS frontend

A383312 Number of king permutations on n elements avoiding the mesh pattern (12, {(0,1),(0,2),(1,0),(1,1),(2,0),(2,2)}).

1, 1, 0, 0, 2, 14, 86, 624, 5096, 46554, 470446, 5214936, 62943852, 821949042, 11548027442, 173711893048, 2785807179384, 47448884653218, 855436571437710, 16275060021803232, 325872090863707740, 6850004083354211050, 150827444158572339810, 3471582648001267649808, 83371646323922972242776

Offset: 0

Dan Li, Apr 22 2025

A permutation p(1)p(2)...p(n) is a king permutation if |p(i+1)-p(i)|>1 for each 0

			For n = 4 the a(4) = 2 solutions are the two permutations 2413 and 3142.
For n = 5 the a(5) = 14 solutions are these 14 permutations: 13524, 14253, 24135, 24153, 25314, 31425, 31524, 35142, 35241, 41352, 42513, 42531, 52413, 53142.

Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See Theorem 4.3 at page 16.

Cf. A002464, A382644, A382645, A382651, A383040, A383107.

G.f.: (t + 1/(1 + t) - t^2*A(t)^2/((1 + t)*(1 + t + t*A(t))))*A(t) where A(t) = Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^n is the g.f. for king permutations given by A002464.

A129534 Triangle read by rows: T(n,k) = number of permutations p of 1,...,n, with min(|p(i)-p(i-1)|, i=2..n) = k (n>=2, k>=1).

Original entry on oeis.org

2, 6, 22, 2, 106, 14, 630, 88, 2, 4394, 614, 32, 35078, 4874, 366, 2, 315258, 43638, 3912, 72, 3149494, 435002, 42808, 1494, 2, 34620010, 4775184, 496222, 25224, 160, 415222566, 57214716, 6164470, 393792, 6054, 2, 5395737242, 742861262, 82190752, 6070408, 160784, 352

Offset: 2

Emeric Deutsch, May 05 2007

Row n has floor(n/2) terms. Row sums are the factorial numbers (A000142). T(n,1) = A129535(n). Sum(T(n,k), k>=2) = A002464(n). If, in the definition, min is replaced by max, then one obtains A064482.

			T(4,2) = 2 because we have 3142 and 2413.
Triangle starts:
     2;
     6;
    22,   2;
   106,  14;
   630,  88,  2;
  4394, 614, 32;
  ...

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.

Alois P. Heinz, Rows n = 2..18, flattened

Cf. A000142, A129535, A002464, A064482.

k:=3: with(combinat): a:=proc(n) local P,ct,i: P:=permute(n): ct:=0: for i from 1 to n! do if min(seq(abs(P[i][j]-P[i][j-1]),j=2..n))=k then ct:=ct+1 else ct:=ct: fi: od: ct: end: seq(a(n),n=2..8); # yields the first 7 entries in any specified column k

More terms from R. J. Mathar, Oct 11 2007

A189271 Number of permutations p of 1,2,...,n satisfying |p(i+6)-p(i)|<>6 for all 1<=i<=n-6.

Original entry on oeis.org

1, 2, 6, 24, 120, 720, 4800, 34752, 280512, 2528256, 25282560, 278323200, 3289036800, 42336448512, 589351062528, 8820501301248, 141215147788800, 2407845089203200, 43543159894318080, 832618225074748416, 16782891792284791296

Offset: 1

Vaclav Kotesovec, Apr 19 2011

a(n) is also number of ways to place n nonattacking pieces rook + leaper[6,6] on an n X n chessboard.

Vaclav Kotesovec, Table of n, a(n) for n = 1..24
Vaclav Kotesovec, Non-attacking chess pieces, Sixth edition, p. 633, Feb 02 2013.
Vaclav Kotesovec, Mathematica program for this sequence
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11.

Cf. A002464, A110128, A117574, A189255, A189256.

Column k=6 of A333706.

Asymptotic (R. Tauraso 2006, quadratic term V. Kotesovec 2011): a(n)/n! ~ (1 + 20/n + 168/n^2)/e^2.

Generally (for this sequence is d=6): 1/e^2*(1+4(d-1)/n+2d*(3d-4)/n^2+...).

Terms a(23)-a(24) from Vaclav Kotesovec, Apr 21 2012

A229430 Number of ways to label the cells of a 2 X n grid such that no (orthogonally) adjacent cells have adjacent labels.

Original entry on oeis.org

1, 0, 0, 24, 1660, 160524, 21914632, 4065598248, 987830372684, 304870528356476, 116578000930637000, 54116343193686469960, 29984241542575292762940, 19548555813018460134901516, 14815308073366437897483622056, 12915964646307201385492841052040

Offset: 0

Jens Voß, Sep 23 2013

nonn

a(n) is the number of Hamiltonian paths in the complement of the n-ladder graph. - Andrew Howroyd, Feb 14 2020

			The A(3) = 24 valid labelings of a 2 X 3 grid are
   153   163   135   513   415   416
   426   425   462   246   263   253
together with their 18 reflections and rotations.

Andrew Howroyd, Table of n, a(n) for n = 0..100
F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.
Andrew Howroyd, Worked Solution and Formula
Eric Weisstein's World of Mathematics, Ladder Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path

Row n=2 of A229429.

Cf. A002464.

seq(n)={my(gf=(1 - x)*(1 + (3*y - 2)*x + (y + 1)*x^2)/(1 + (-y^2 + 5*y - 3)*x + (y^3 - 3*y^2 + 3)*x^2 + (-2*y^3 + 5*y^2 - 3*y - 1)*x^3 + (y^3 - y^2 + 2*y)*x^4)); [subst(serlaplace(p*y^0),y,1) | p <- Vec(gf + O(x*x^n))]} \\ Andrew Howroyd, Feb 16 2020

Terms a(9) and beyond from Andrew Howroyd, Feb 14 2020

A279214 Number of permutations sigma such that |sigma(i+1)-sigma(i)| >= 3 for 1 <= i <= n - 1 and |sigma(i+2)-sigma(i)| >= 3 for 1 <= i <= n - 2.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 40, 792, 15374, 281434, 5089060, 93082532, 1743601076, 33694028152

Offset: 0

Seiichi Manyama, Dec 17 2016

2 | a(n) for n > 1.

			a(9) = 2: 369258147, 741852963.

Cf. A002464 (|sigma(i+1)-sigma(i)| >= 2), A127697 (|sigma(i+1)-sigma(i)| >= 3).

def check(d, a, i)
  return true if i == 0
  j = 1
  d_max = [i, d - 1].min
  while (a[i] - a[i - j]).abs >= d && j < d_max
    j += 1
  end
  (a[i] - a[i - j]).abs >= d
end
def solve(d, len, a = [])
  b = []
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.include?(m))
        if check(d, a + [m], s)
          b += solve(d, len, a + [m])
        end
      end
    }
  end
  b
end
def A279214(n)
  (0..n).map{|i| solve(3, i).size}
end
p A279214(12)

a(0)-a(2), a(15)-a(17) from Alois P. Heinz, Dec 01 2018

A283184 a(n) is the number of symmetric permutations (p(1),p(2),...,p(m)) of (1,2,...,m), m=2n or m=2n+1, with p(m+1-k) = m+1-p(k) for 1<=k<=m, such that adjacent numbers do not differ by 1. a(n) is also the number of point-symmetric arrangements of m non-attacking kings on an m X m board, with one in each row and column.

Original entry on oeis.org

1, 0, 2, 14, 122, 1262, 15466, 219646, 3551194, 64431374, 1296712778, 28672204574, 691007296954, 18029138380846, 506320912190506, 15228632768870462, 488405396197019546, 16638380026019579726, 600022595692147574794, 22836184629309211495774, 914717041435012519583098

Offset: 0

Gerhard Kirchner, Mar 02 2017

nonn

For m=2n+1 the symmetry requires p(n+1)=n+1. That is why the number of permutations is the same for m=2n and m=2n+1.
The n-th element of any permutation is not allowed to be n because otherwise the next element would be n+1. Because of the symmetry it is sufficient to consider the first n elements. Any such n-tuple can be created by a permutation of length n, last element smaller than n: Each element b(k) > n has to be replaced by m+1-b(k).
Example m=6: Original symmetric permutation 536142, 3-tuple 536 created by 231: 5 is replaced by 7-5 and 6 by 7-6.
How many such n-tuples can be created by a n-permutation?
Let us analyze the example above: There are two pairs of adjacent numbers (23 and 31) in the permutation 231. The difference of the first pair is 1, so either 2 or 3 must be replaced, whereas the second pair represents a "gap" (difference > 1), so that 1 can be kept or replaced by 6.
This way, 231 creates four 3-tuples: 531, 241, 536, 246.
Let generally g be the number of gaps in a n-permutation (0<=g<=n-1). Then the number of related n-tuples is 2^(g+1) because the first element of the permutation and each element behind a gap can be arbitrarily replaced or not. On the other hand, when the first element of a section between successive gaps is selected, there is no choice for the replacement of the other elements.
When q is a n-permutation, the number of gaps is g(q) = Sum_{j=1..n-1} sign(|p(j+1)-p(j)|-1). (sign = signum)
The extension up to n=50 was done by a new algorithm, see link "Fast recurrence". - Gerhard Kirchner, Mar 17 2017

			Example 1, m=5:
The matrix, transforming 12345 into 41352, can also be thought of as a chessboard; each "1" is a king.
./0 0 0 1 0\  /1\ /4\
| 1 0 0 0 0 | |2| |1|
| 0 0 1 0 0 |*|3|=|3|
| 0 0 0 0 1 | |4| |5|
.\0 1 0 0 0/  \5/ \2/
Example 2, m=6:
q is a 3-permutation not ending on 3:
q   g(q)  2^(g(q)+1) Symmetric 6-permutations, |p(j+1)-p(j)|>1
132   1        4        135246, 635241, 142536, 642531
231   1        4        531642, 536142, 241635, 246135
312   1        4        315264, 362514, 462513, 415263
321   0        2        426153, 351624
Result: a(3)=14.

Alois P. Heinz, Table of n, a(n) for n = 0..400 (terms n = 0..50 from Gerhard Kirchner)
Gerhard Kirchner, Fast recurrence

Cf. A002464.

b:= proc(n, s, l) option remember; `if`(s={},
     `if`(abs(n/2-l)<1, 0, 1), add(add(`if`(abs(j-l)=1, 0,
        b(n, s minus {i}, i)), j=[i, n-i]), i=s))
    end:
a:= n-> b(2*n+1, {$1..n}, -1):
seq(a(n), n=0..10);  # Alois P. Heinz, Mar 15 2017
# second Maple program:
a:= proc(n) option remember; `if`(n<4, (n-1)*
      (7*n^2-5*n-6)/6, (2*n+1)*a(n-1) -(2*n-5)*
      (a(n-2)+a(n-3)) +(2*n-6)*a(n-4))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 17 2017

a[n_] := a[n] = If[n<4, (n-1)*(7n^2-5n-6)/6, (2n+1)*a[n-1] - (2n-5)*(a[n-2] + a[n-3]) + (2n-6)*a[n-4]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 18 2017, after Alois P. Heinz *)

a(n)={subst(serlaplace(polcoef((1 - x)/(1 + (1 - 2*y)*x + 2*y*x^2) + O(x*x^n), n)), y, 1)} \\ Andrew Howroyd, Mar 01 2024

Let q be any permutation (p(1), p(2),..., p(n)) with p(n) < n and g(q) = Sum_{j=1..n-1} sgn(|p(j+1)-p(j)|-1).
a(n) = Sum_{each q} 2^(g(q)+1).
a(n) ~ exp(-1) * 2^n * n!. - Vaclav Kotesovec, Apr 20 2017

a(14)-a(20) from Alois P. Heinz, Mar 15 2017

A288208 Number of permutations of a sequence of length n such that there are no fixed points, and no term is next to a term it was next to originally.

Original entry on oeis.org

1, 0, 0, 0, 2, 2, 27, 214, 1695, 15482, 159019, 1775664, 21542628, 282722448, 3989526469, 60239477384, 969280731152, 16558273230450, 299319139977198, 5708394302035014, 114547714715532531, 2412649672553637772, 53220018152831892175, 1227013593901474460674, 29512839964990444892407

Offset: 0

Peter Kagey, Jun 06 2017

nonn

a(n) is bounded above both by A002464 and A000166.

The Mathematics Stack Exchange link claims that the limit as n goes to infinity of A000166(n)/a(n) = e^2.

			For n = 4 the a(4) = 2 solutions are [2,4,1,3] and [3,1,4,2].
For n = 5 the a(5) = 2 solutions are [3,1,5,2,4] and [2,4,1,5,3].
a(6) = 27: 241635, 246135, 246315, 251364, 264135, 314625, 315264, 351624, 351642, 352614, 352641, 361524, 362514, 415263, 415362, 462513, 462531, 514263, 531624, 531642, 536142, 536241, 631524, 635142, 635241, 642513, 642531.

Max Alekseyev, Table of n, a(n) for n = 0..30
Fine et al., If some series of n terms is deranged, what is the probability that no term stands next to a term it was next to originally?, Mathematics StackExchange, 2017.
Robert P. P. McKone, The permutations n=4 to n=9.

Cf. A002464 is analogous without the fixed point restriction.

Cf. A000142, A000166, A209322, A381461.

pairs l = zip l (drop 1 l)
d n = filter (all (uncurry (/=)) . zip [1..]) $ Data.List.permutations [1..n]
a n = length $ filter (all ((1<) . abs . uncurry (-)) . pairs) $ d n

b:= proc(s, l) option remember; (n-> `if`(n=0, 1, add(
     `if`(j=n or abs(l-j)<2, 0, b(s minus {j}, j)), j=s)))(nops(s))
    end:
a:= n-> b({$1..n}, -1):
seq(a(n), n=0..17);  # Alois P. Heinz, Feb 08 2025

Clear[permCount]; permCount[s_, last_] := permCount[s, last] = Module[{n, j}, n = Length[s]; If[n == 0, 1, Total[Table[If[j == n || Abs[last - j] < 2, 0, permCount[Complement[s, {j}], j]], {j, s}]]]]; Table[permCount[Range[n], -2], {n, 0, 12}] (* Robert P. P. McKone, Mar 22 2025 *)

{ a288208(n) = my(A = matrix(n,n,i,j,abs(i-j)>1)); parsum(s=1,2^n-1, my(M=vecextract(A,s,s), d=matsize(M)[1], v=vectorv(d,i,1), pos=bitand(s,1)); if(pos,v[1]=0); for(k=1,n-1, v=M*v; if(bitand(s>>k,1), v[pos++]=0)); (-1)^(n-d)*vecsum(v) ); } \\ Max Alekseyev, Feb 08 2025

a(12)-a(16) from Lars Blomberg, Jul 05 2017
Terms a(17) onward from Max Alekseyev, Feb 07 2025
a(0)=1 prepended by Alois P. Heinz, Feb 08 2025

Previous Showing 31-40 of 66 results. Next

cp's OEIS Frontend

A189256 Number of permutations p of 1,2,...,n satisfying |p(i+5)-p(i)|<>5 for all 1<=i<=n-5.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A245377 Number of 2-alternating permutations of 1,2,...,n, that is, a(n) is the number of down/up permutations (A000111) of 1,2,...,n such that any two consecutive terms differ by at least two.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A383312 Number of king permutations on n elements avoiding the mesh pattern (12, {(0,1),(0,2),(1,0),(1,1),(2,0),(2,2)}).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129534 Triangle read by rows: T(n,k) = number of permutations p of 1,...,n, with min(|p(i)-p(i-1)|, i=2..n) = k (n>=2, k>=1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Extensions

A189271 Number of permutations p of 1,2,...,n satisfying |p(i+6)-p(i)|<>6 for all 1<=i<=n-6.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A229430 Number of ways to label the cells of a 2 X n grid such that no (orthogonally) adjacent cells have adjacent labels.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A279214 Number of permutations sigma such that |sigma(i+1)-sigma(i)| >= 3 for 1 <= i <= n - 1 and |sigma(i+2)-sigma(i)| >= 3 for 1 <= i <= n - 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs