A002464 -id:A002464 - cp's OEIS frontend

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

1, 1, 0, 0, 2, 14, 88, 632, 5152, 46972, 474008, 5248616, 63294680, 825940168, 11597278752, 174367336624, 2795167052832, 47591679875632, 857754907053056, 16314976128578752, 326598651690933216, 6863945954213702816, 151108752072042907968, 3477537076217415673344, 83503583639127861347392

Offset: 0

Dan Li, Apr 26 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.6 at page 19.

Cf. A002464, A382644, A382645, A382651, A383040, A383107, A383312, A383406, A383407.

G.f.: (1 + t)*(A(t) - t)/(1 + t*(A(t) - t - 1)) 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.

A085372 If n = 0 or 1 then a(n) = 1; if n = 2, 3 or 4 then a(n) = 0; otherwise a(n) = (n+1)a(n-1)-(n-2)a(n-2)-(n-5)a(n-3)+(n-3)a(n-4).

Original entry on oeis.org

1, 1, 0, 0, 0, 2, 14, 102, 828, 7522, 75706, 836622, 10073824, 131300266, 1841921270, 27673138086, 443343106468, 7544813993618, 135925854199186, 2584491212811038, 51722014716352136, 1086739983701035418, 23919225571408768782, 550360567615450589302

Offset: 0

N. J. A. Sloane, Aug 14 2003

This is the same recurrence as A002464 but with different initial values.

Cf. A002464.

A085372 := proc(n) options remember; if n <= 1 then 1 elif n <= 4 then 0 else (n+1)*A085372(n-1)-(n-2)*A085372(n-2)-(n-5)*A085372(n-3)+(n-3)*A085372(n-4); fi; end;

A098926 Permanent of the (0,1)-matrix with ij-th entry equal to zero iff (i=1,j=1),(i=1,j=2),(i=1,j=3),(i=2,j=3),(i=3,j=3),... In other words, the ij-th entry of the matrix is zero iff it is on the path which start from the entry (i=1,j=1) and moves in the matrix alternating 3 steps to the right to 3 steps down.

Original entry on oeis.org

1, 0, 0, 0, 2, 12, 90, 556, 5242, 42380, 479306, 4817484, 63779034, 767504524, 11661506218, 163541678156, 2806878055610, 44960579074956, 860568917787402, 15502269624912460, 327460573946510746, 6552868832109180044, 151436547414562736234, 3332986639447590230604, 83655126041771262574458

Offset: 0

Simone Severini, Oct 19 2004

nonn

			a(5) = 12 because 12 is the permanent of the following 5 X 5 matrix:
    [0 0 0 1 1]
    [1 1 0 1 1]
    [1 1 0 0 0]
    [1 1 1 1 0]
    [1 1 1 1 0]

Max Alekseyev, Table of n, a(n) for n = 0..100 (terms 3..36 from Vaclav Kotesovec)
Manuel Kauers and Christoph Koutschan, Some D-finite and some Possibly D-finite Sequences in the OEIS, arXiv:2303.02793 [cs.SC], 2023, pp. 43-44.

a(n)={my(M=matrix(n, n, i, j, j-i<>1 && (i%2==0 || abs(j-i-1)<>1))); matpermanent(M)} \\ Andrew Howroyd, Nov 05 2019

From Manuel Kauers and Christoph Koutschan, Mar 02 2023: (Start)
Conjectured recurrence of order 8 and degree 7: (3*n^5 + 80*n^4 + 763*n^3 + 3184*n^2 + 5915*n + 4080)*a(n+8) + (-3*n^5 - 83*n^4 - 833*n^3 - 3663*n^2 - 6967*n - 4465)*a(n+7) + (-3*n^7 - 122*n^6 - 2039*n^5 - 18038*n^4 - 90333*n^3 - 252920*n^2 - 364438*n - 211080)*a(n+6) + (17*n^5 + 445*n^4 + 4253*n^3 + 17161*n^2 + 24893*n + 1765)*a(n+5) + (9*n^7 + 318*n^6 + 4409*n^5 + 30672*n^4 + 113879*n^3 + 219268*n^2 + 186788*n + 35600)*a(n+4) + (-n^5 + 103*n^4 + 2125*n^3 + 14395*n^2 + 38283*n + 32845)*a(n+3) + (-9*n^7 - 294*n^6 - 3677*n^5 - 22722*n^4 - 76591*n^3 - 146304*n^2 - 157554*n - 81720)*a(n+2) - (n+1)*(13*n^4 + 388*n^3 + 3717*n^2 + 13424*n + 16865)*a(n+1) + n*(n+1)*(3*n^5 + 95*n^4 + 1113*n^3 + 5983*n^2 + 14907*n + 14025)*a(n) = 0.
Conjectured differential equation for the generating function: x^5*(x^2 - 1)^3*(x^8 - 2*x^7 - 12*x^6 + 28*x^5 - 10*x^4 - 22*x^3 + 4*x^2 + 4*x + 1)*f'''(x) + x^4*(x^2 - 1)*(5*x^12 - 12*x^11 - 76*x^10 + 212*x^9 - 143*x^8 - 156*x^7 + 80*x^6 + 36*x^5 + 7*x^4 - 24*x^3 - 4*x^2 + 8*x + 3)*f''(x) + x*(x^2 - 1)*(4*x^14 - 9*x^13 - 95*x^12 + 342*x^11 - 288*x^10 - 29*x^9 - 75*x^8 - 336*x^7 + 252*x^6 + 121*x^5 - 53*x^4 + 10*x^3 - 3*x - 1)*f'(x) + 2*(2*x^14 - 13*x^13 + 12*x^12 - 128*x^11 + 40*x^10 + 513*x^9 - 410*x^8 - 24*x^7 + 218*x^6 - 283*x^5 + 16*x^4 + 104*x^3 - 4*x^2 - 9*x - 2)*f(x) = 0. (End)
Conjecture: a(n) ~ exp(-2) * n!, based on the recurrence by Manuel Kauers and Christoph Koutschan. - Vaclav Kotesovec, Mar 02 2023
For even n, a(n) = A002464(n); for odd n, a(n) = A002464(n) - A002464(n-1). These formulae allow to easily verify the above conjectures. - Max Alekseyev, Jun 01 2025

Terms a(11) and beyond from Andrew Howroyd, Nov 05 2019

a(0)-a(2) prepended by Max Alekseyev, May 31 2025

A229429 Number of ways to label the cells of an m-by-n grid such that no (orthogonally) adjacent cells have adjacent labels; square array A(m,n) read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 24, 24, 2, 1, 1, 14, 1660, 12072, 1660, 14, 1, 1, 90, 160524, 16595940, 16595940, 160524, 90, 1, 1, 646, 21914632, 46053512896, 696497375736, 46053512896, 21914632, 646, 1

Offset: 0

Jens Voß, Sep 23 2013

			The A(2,3) = 24 valid labelings of a 2-by-3 grid are
   153   163   135   513   415   416
   426   425   462   246   263   253
together with their 18 reflections and rotations.
The square array starts:
1,   1,   1,   1,   1,   1,  ...
1,   1,   0,   0,   2,  ...
1,   0,   0,  24,  ...
1,   0,  24,  ...
1,   2,  ...
1,  ...

A(1, n) = A002464(n), A(2, n) = A229430(n)

A318790 One-half of the number of permutations sigma of {1,2,...,n^2 + 1} such that |sigma(i+j)-sigma(i)| >= n for 1 <= i <= n^2 + 1 - j, 1 <= j <= n - 1.

Original entry on oeis.org

1, 7, 20, 37, 64, 109

Offset: 1

Seiichi Manyama, Dec 15 2018

			In case n=2:
permutation
--------------------------------
[1, 3, 5, 2, 4] and its reverse.
[1, 4, 2, 5, 3] and its reverse.
[2, 4, 1, 3, 5] and its reverse.
[2, 4, 1, 5, 3] and its reverse.
[2, 5, 3, 1, 4] and its reverse.
[3, 1, 4, 2, 5] and its reverse.
[3, 1, 5, 2, 4] and its reverse.
So a(2) = 14/2 = 7.

Cf. A002464, A279214, A322281, A322308.

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 A318790(n)
  (1..n).map{|i| solve(i, i * i + 1).size / 2}
end
p A318790(4)

A370485 Number of permutations of [n] with the property that no subsequence k(k+1)(k+2) or (k+2)(k+1)k occurs but k(k+1) or (k+1)k occurs.

Original entry on oeis.org

0, 0, 2, 4, 16, 78, 480, 3436, 28050, 256868, 2607584, 29061022, 352747696, 4632195548, 65432845858, 989341728564, 15942876295728, 272777484786062, 4938657746907200, 94332342088674252, 1895781452461383986, 39987981759263286340, 883322358371147863168

Offset: 0

Seiichi Manyama, Feb 19 2024

nonn

			123 contains 3 consecutive number and 321 contains 3 consecutive number in reverse order. So a(3) = 6-2 = 4.

Seiichi Manyama, Table of n, a(n) for n = 0..449

Cf. A002464, A095816, A370390.

my(N=30, x='x+O('x^N)); concat([0, 0], Vec(sum(k=0, N, k!*x^k*(((1-2*x^2+x^3)/(1-x^3))^k-((1-2*x+x^2)/(1-x^2))^k))))

a(n) = A095816(n) - A002464(n).

G.f.: Sum_{k>=0} k! * x^k * ( ((1-2*x^2+x^3)/(1-x^3))^k - ((1-2*x+x^2)/(1-x^2))^k ).

A373877 Triangle read by rows: T(n, k) is the number of permutations of length n, which contain the maximum number of distinct patterns of length k.

Original entry on oeis.org

1, 2, 2, 6, 4, 6, 24, 22, 2, 24, 120, 118, 2, 14, 120, 720, 718, 218, 8, 90, 720, 5040, 5038, 3070, 24, 2, 646, 5040, 40320, 40318, 32972, 64, 28, 20, 5242, 40320, 362880, 362878, 336196, 3704, 4, 4, 158, 47622, 362880, 3628800, 3628798, 3533026, 325752, 16, 16, 16, 1960, 479306, 3628800, 39916800, 39916798, 39574122

Offset: 1

Thomas Scheuerle, Jun 20 2024

Let P be a permutation of the set {1, 2, ..., n}. We consider all subsequences from P of length k and count the different permutation patterns obtained. T(n, k) is the number of permutations with the greatest count among all P.
A373778 gives the greatest count found.
Statistical results show that the maximum number of patterns occurs among the permutations that, when represented as a 2D pointset, maximize the average distance between neighboring points.
Column k gives the number of k-good permutations defined in A124188 for all rows where A373778(n, k) = k!.

			The triangle begins:
   n| k:     1|     2|     3|  4|   5|   6|    7|     8
  =====================================================
  [1]        1
  [2]        2,     2,
  [3]        6,     4,     6,
  [4]       24,    22,     2, 24
  [5]      120,   118,     2, 14, 120
  [6]      720,   718,   218,  8,  90, 720
  [7]     5040,  5038,  3070, 24,   2, 646, 5040
  [8]    40320, 40318, 32972, 64,  28,  20, 5242, 40320
  ...
T(3, 2) = 4 because we have:
  permutations  subsequences      patterns            number of patterns
  {1,2,3} : {1,2},{1,3},{2,3} : [1,2],[1,2],[1,2] :  1.
  {1,3,2} : {1,3},{1,2},{3,2} : [1,2],[1,2],[2,1] :  2 is a winner.
  {2,1,3} : {2,1},{2,3},{1,3} : [2,1],[1,2],[1,2] :  2 is a winner.
  {2,3,1} : {2,3},{2,1},{3,1} : [1,2],[2,1],[2,1] :  2 is a winner.
  {3,1,2} : {3,1},{3,2},{1,2} : [2,1],[2,1],[1,2] :  2 is a winner.
  {3,2,1} : {3,2},{3,1},{2,1} : [2,1],[2,1],[2,1] :  1.
A pattern is a set of indices that may sort a selected subsequence into an increasing sequence.

Cf. A002464, A124188, A342474, A373778.

row(n) = my(rowp = vector(n!, i, numtoperm(n, i)), v = vector(n), t = vector(n)); for (j=1, n, for (i=1, #rowp, my(r = rowp[i], list = List()); forsubset([n, j], s, my(ss = Vec(s)); vp = vector(j, ik, r[ss[ik]]); vs = Vec(vecsort(vp, , 1)); listput(list, vs); ); if( v[j] < #Set(list), v[j] = #Set(list); t[j] = 1, if(v[j] == #Set(list), t[j] = t[j]+1)); ); ); t;

T(n, 1) = n!.
T(n, n) = n!.
T(n, 2) = n! - 2, for n > 2.
T(n, 3) = A124188(n), for n > 4.
T(n, n-1) = A002464(n), for n > 3.

Previous Showing 51-60 of 66 results. Next

cp's OEIS Frontend

A328222 Number of compositions of n into distinct parts such that the difference between adjacent parts is at least two.

Views

Author

Keywords

Comments

Examples

Crossrefs

A346462 Triangle read by rows: T(n,k) gives the number of permutations of length n containing exactly k instances of the 1-box pattern; 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A381461 Number of permutations of [n] with no fixed points where adjacent elements differ by at least 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A085372 If n = 0 or 1 then a(n) = 1; if n = 2, 3 or 4 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1)-(n-2)*a(n-2)-(n-5)*a(n-3)+(n-3)*a(n-4).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Views

Author

Keywords

Examples

Links

Programs

PARI

Formula

Extensions

A229429 Number of ways to label the cells of an m-by-n grid such that no (orthogonally) adjacent cells have adjacent labels; square array A(m,n) read by antidiagonals.

Views

Author

Keywords

Examples

Crossrefs

A318790 One-half of the number of permutations sigma of {1,2,...,n^2 + 1} such that |sigma(i+j)-sigma(i)| >= n for 1 <= i <= n^2 + 1 - j, 1 <= j <= n - 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Ruby

A370485 Number of permutations of [n] with the property that no subsequence k(k+1)(k+2) or (k+2)(k+1)k occurs but k(k+1) or (k+1)k occurs.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A373877 Triangle read by rows: T(n, k) is the number of permutations of length n, which contain the maximum number of distinct patterns of length k.

Views

Author

Keywords

A085372 If n = 0 or 1 then a(n) = 1; if n = 2, 3 or 4 then a(n) = 0; otherwise a(n) = (n+1)a(n-1)-(n-2)a(n-2)-(n-5)a(n-3)+(n-3)a(n-4).