A000179 -id:A000179 - cp's OEIS frontend

A300480 Rectangular array read by antidiagonals: a(m,n) = 2 * Integral_{t>=0} T_n((t+m)/2)exp(-t)dt, m>=0, n>=0, where T_n(x) is n-th Chebyshev polynomial of first kind.

2, 2, 1, 2, 2, 0, 2, 3, 3, 3, 2, 4, 8, 10, 18, 2, 5, 15, 29, 47, 95, 2, 6, 24, 66, 130, 256, 592, 2, 7, 35, 127, 327, 697, 1610, 4277, 2, 8, 48, 218, 722, 1838, 4376, 11628, 35010, 2, 9, 63, 345, 1423, 4459, 11770, 31607, 95167, 320589, 2, 10, 80, 514, 2562, 9820, 30248, 85634, 258690

Offset: 0

Max Alekseyev, Mar 06 2018

a(m,n) is a polynomial in m of degree n.

For any integers m>=0, n>=0, 2 * Integral_{t=-m..m} T_n(t/2)*exp(-t)*dt = 4 * Integral_{z=-m/2..m/2} T_n(z)*exp(-2*z)*dz = A300481(m,n)*exp(m) - a(m,n)*exp(-m).

			Array starts with:
m=0: 2,  1,   0,    3,    18,     95,     592, ...
m=1: 2,  2,   3,   10,    47,    256,    1610, ...
m=2: 2,  3,   8,   29,   130,    697,    4376, ...
m=3: 2,  4,  15,   66,   327,   1838,   11770, ...
m=4: 2,  5,  24,  127,   722,   4459,   30248, ...
...

Values for m<=0 are given in A300481.
Rows: A300482 (m=0), A300483 (m=1), A300484 (m=2), A300485 (m=-1), A102761 (m=-2).
Columns: A007395 (n=0), A000027 (n=1), A005563 (n=2), A084380 (n=3).
Cf. A000179 (almost row m=-2), A127672, A156995.

{ A300480(m,n) = if(n==0,return(2)); subst( serlaplace( 2*polchebyshev(n,1,(x+m)/2)), x, 1); }

a(m,n) = Sum_{i=0..n} A127672(n,i) * i! * Sum_{j=0..i} m^j/j!.

a(m,n) = Sum_{i=0..n} A127672(n,i) * A080955(m,i) = Sum_{i=0..n} A127672(n,i) * A089258(i,m).

A300481 Rectangular array read by antidiagonals: a(m,n) = 2 * Integral_{t>=0} T_n((t-m)/2)exp(-t)dt, m>=0, n>=0, where T_n(x) is n-th Chebyshev polynomial of first kind.

Original entry on oeis.org

2, 2, 1, 2, 0, 0, 2, -1, -1, 3, 2, -2, 0, 2, 18, 2, -3, 3, 1, 7, 95, 2, -4, 8, -6, 2, 34, 592, 2, -5, 15, -25, 15, 13, 218, 4277, 2, -6, 24, -62, 82, -28, 80, 1574, 35010, 2, -7, 35, -123, 263, -269, 106, 579, 12879, 320589

Offset: 0

Max Alekseyev, Mar 06 2018

Although negative values of m are not present here or in A300480, the two arrays are connected with the formula: a(m,n) = A300480(-m,n). Thus, they essentially represent two "halves" of the same array indexed by integers m.
a(m,n) is a polynomial in m of degree n.
For any integers m>=0, n>=0, 2 * Integral_{t=-m..m} T_n(t/2)*exp(-t)*dt = 4 * Integral_{z=-m/2..m/2} T_n(z)*exp(-2*z)*dz = a(m,n)*exp(m) - A300480(m,n)*exp(-m).

			Array starts with:
m=0: 2,  1,  0,    3,   18,     95,    592, ...
m=1: 2,  0, -1,    2,    7,     34,    218, ...
m=2: 2, -1,  0,    1,    2,     13,     80, ...
m=3: 2, -2,  3,   -6,   15,    -28,    106, ...
m=4: 2, -3,  8,  -25,   82,   -269,    920, ...
...

Values for m<=0 are given in A300480.
Rows: A300482 (m=0), A300485 (m=1), A102761 (m=2), A300483 (m=-1), A300484 (m=-2).
Columns (up to signs and offset): A007395 (n=0), A000027 (n=1), A005563 (n=2).
Cf. A000179 (almost row m=2), A127672, A156995.

{ A300481(m,n) = A300480(-m,n); } \\ see code in A300480

a(m,n) = A300480(-m,n) = Sum_{i=0..n} A127672(n,i) * i! * Sum_{j=0..i} (-m)^j/j!.

a(m,n) = Sum_{i=0..n} A127672(n,i) * A292977(i,m).

A000033 Coefficients of ménage hit polynomials.

Original entry on oeis.org

0, 2, 3, 4, 40, 210, 1477, 11672, 104256, 1036050, 11338855, 135494844, 1755206648, 24498813794, 366526605705, 5851140525680, 99271367764480, 1783734385752162, 33837677493828171, 675799125332580020, 14173726082929399560, 311462297063636041906

Offset: 1

N. J. A. Sloane and Simon Plouffe

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

David W. Wilson, Table of n, a(n) for n = 1..100

A diagonal of A058087.

Cf. A000159, A000179, A000425.

fac = a000142
a n = sum $ map f [2..n]
  where f k = g k `div` h k
        g k = (-1)^k * n * fac (2*n-k-1) * fac (n-k)
        h k = fac (2*n-2*k) * fac (k-2)
-- James Spahlinger, Oct 08 2012

[0] cat [&+[(-1)^k*n*Factorial(2*n-k-1)*Factorial(n-k)/(Factorial(2*n-2*k)*Factorial(k-2)): k in [2..n]]: n in [2..25]]; // Vincenzo Librandi, Jun 11 2019

Table[n*Sum[(-1)^k*(2*n-k-1)!*(n-k)!/((2*n-2*k)!*(k-2)!),{k,2,n}],{n,1,20}] (* Vaclav Kotesovec, Oct 26 2012 *)

def A000033(n): return n*sum((-1)^k*(2*n-3-2*k)*factorial(n-k-2)*binomial(2*n-k-3, k) for k in range(n-1)) # G. C. Greubel, Jul 10 2025

a(n) = coefficient of t^2 in polynomial p(t) = Sum_{k=0..n} 2*n*C(2*n-k,k)*(n-k)!*(t-1)^k/(2*n-k).
a(n) = Sum_{k=2..n} (-1)^k*n*(2*n-k-1)!*(n-k)!/((2*n-2*k)!*(k-2)!). - David W. Wilson, Jun 22 2006
a(n) = n*A000426(n) - Vladeta Jovovic, Dec 27 2007
Recurrence: (n-3)*(n-2)*(2*n-5)*(2*n-7)*a(n) = (n-3)*(n-2)*n*(2*n-7)^2*a(n-1) + (n-4)*(n-3)*n*(2*n-3)^2*a(n-2) + (n-2)*n*(2*n-5)*(2*n-3)*a(n-3). - Vaclav Kotesovec, Oct 26 2012
a(n) ~ 2/e^2*n!. - Vaclav Kotesovec, Oct 26 2012
From Mark van Hoeij, Jun 09 2019: (Start)
a(n) = round(2*(exp(-2)*n*(4*BesselK(n,2) - (2*n-5)*BesselK(n-1,2)) - (-1)^n)), for n > 9.
a(n) = (3/2)*(A000159(n+1)*n/(n+1) - A000159(n))/(n-1) for n > 2. (End)
Conjecture: a(n) + 2*a(n+p) + a(n+2*p) is divisible by p for any prime p. - Mark van Hoeij, Jun 10 2019

Extended to 34 terms by N. J. A. Sloane, May 25 2005

Edited and further extended by David W. Wilson, Dec 27 2007

A184965 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 6 for all i.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 2, 78, 888, 13909, 204448, 3182225, 51504968, 873224962, 15498424578, 287972983669, 5598118158336, 113756109812283, 2413723031593090, 53416658591208438, 1231458960862452472, 29538634475147637783, 736321207493996695072

Offset: 0

Alois P. Heinz, Apr 20 2011

nonn

			a(8) = 2: (2,3,4,5,6,7,8,1), (3,4,5,6,7,8,1,2).

Shalosh B. Ekhad and Doron Zeilberger, Table of n, a(n) for n = 0..100
D. Zeilberger, Automatic Enumeration of Generalized Ménage Numbers

A diagonal of A008305.

Cf. A000142, A000166, A000179, A000183, A004307.

with(LinearAlgebra):
a:= n-> `if`(n=0, 1, Permanent(Matrix(n, (i, j)->
                     `if`(i-j<=0 and i-j>-6 or i-j>n-6, 0, 1)))):
seq(a(n), n=0..15);

a[n_] := Permanent[Table[If[i-j <= 0 && i-j > -6 || i-j > n-6, 0, 1], {i, 1, n}, {j, 1, n}]]; a[0] = 1; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 15}] (* Jean-François Alcover, Jan 07 2016, adapted from Maple *)

A277256 Multi-table menage numbers T(n,k) for n,k >= 1 equals the number of ways to seat the gentlemen from nk married couples at n round tables with 2k seats each such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other; provided that the ladies are already properly seated (i.e., no two ladies sit next to each other).

Original entry on oeis.org

0, 1, 0, 2, 4, 1, 9, 80, 82, 2, 44, 4752, 43390, 4740, 13, 265, 440192, 59216968, 59216648, 439794, 80, 1854, 59245120, 164806652728, 2649391488016, 164806435822, 59216644, 579, 14833, 10930514688, 817056761525488, 312400218967336992, 312400218673012936, 817056406224656, 10927434466, 4738

Offset: 1

Max Alekseyev, Oct 07 2016

			Table T(n,k):
  n=1:  0,      0,            1,                  2, ...
  n=2:  1,      4,           82,               4740, ...
  n=3:  2,     80,        43390,           59216648, ...
  n=4:  9,   4752,     59216968,      2649391488016, ...
  n=5: 44, 440192, 164806652728, 312400218967336992, ...
  ...

Cf. A000179 (row n=1), A000166 (column k=1), A000316 (column k=2), A277257, A277265, A341439.

{ A277256(n,k) = my(m,s,g); m=n*k; s=sqrt(1+4*x+O(x^(m+1))); g=if(k==1,1+z,((1-s)/2)^(2*k)+((1+s)/2)^(2*k))^n; sum(j=0,m,(-1)^j*polcoeff(g,j)*(m-j)!); }

T(n,k) = Sum_{j=0..n*k} (-1)^j * (n*k-j)! * [z^j] F(k,z)^n, where F(1,z) = 1+z and F(k,z) = ((1-sqrt(1+4*z))/2)^(2*k) + ((1+sqrt(1+4*z))/2)^(2*k) for k >= 2. [Corrected by Pontus von Brömssen, Jun 01 2022]

T(n,k) = A341439(n,n*k). - Pontus von Brömssen, May 31 2022

A078480 Number of permutations p of {1,2,...,n} such that |p(i)-i| != 1 for all i.

Original entry on oeis.org

1, 1, 1, 2, 5, 21, 117, 792, 6205, 55005, 543597, 5922930, 70518905, 910711193, 12678337945, 189252400480, 3015217932073, 51067619064873, 916176426422089, 17355904144773970, 346195850534379613, 7252654441500887309

Offset: 0

Vladeta Jovovic, Jan 03 2003

For positive n, a(n) equals the permanent of the n X n matrix with 0's along the superdiagonal and the subdiagonal, and 1's everywhere else. [John M. Campbell, Jul 09 2011]

Vincenzo Librandi, Table of n, a(n) for n = 0..200
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 223.
N. S. Mendelsohn, The asymptotic series for a certain class of permutation problems, Canadian Journal of Mathematics, vol. VIII, No.2, 1956, p.238 (Example 5).

Cf. A000179, A000271.
Column k=0 of A320582.
Column k=1 of A306512.

(* Explicit formula: *) Table[Sum[Sum[(-1)^k*(i-k)!*Binomial[2i-k,k],{k,0,i}],{i,0,n}],{n,0,21}] (* Vaclav Kotesovec, Mar 28 2011 *)

G.f.: 1/(1-x^2)*Sum_{n>=0} n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 26 2007
Asymptotic (N. S. Mendelsohn, 1956): a(n)/n! -> 1/e^2
Recurrence: a(n) = n*a(n-1) - (n-2)*a(n-3) - a(n-4), for n>=5

A189389 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 5 for all i.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 2, 49, 484, 6208, 79118, 1081313, 15610304, 238518181, 3850864416, 65598500129, 1177003136892, 22203823852849, 439598257630414, 9117748844458320, 197776095898147080, 4479171132922158213, 105749311074795459594, 2598770324359627927649

Offset: 0

Alois P. Heinz, Apr 20 2011

nonn

			a(7) = 2: (2,3,4,5,6,7,1), (3,4,5,6,7,1,2).

Shalosh B. Ekhad and Doron Zeilberger, Table of n, a(n) for n = 0..100
D. Zeilberger, Automatic Enumeration of Generalized Ménage Numbers

A diagonal of A008305.

Cf. A000142, A000166, A000179, A000183, A004307.

with(LinearAlgebra):
a:= n-> `if`(n=0, 1, Permanent(Matrix(n, (i, j)->
                     `if`(i-j<=0 and i-j>-5 or i-j>n-5, 0, 1)))):
seq(a(n), n=0..15);

a[n_] := Permanent[Table[If[i-j <= 0 && i-j > -5 || i-j > n-5, 0, 1], {i, 1, n}, {j, 1, n}]]; a[0] = 1; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jan 07 2016, adapted from Maple *)

A000159 Coefficients of ménage hit polynomials.

Original entry on oeis.org

2, 8, 20, 152, 994, 7888, 70152, 695760, 7603266, 90758872, 1174753372, 16386899368, 245046377410, 3910358788256, 66323124297872, 1191406991067168, 22596344660865282, 451208920617687720, 9461897733571886372, 207894669895136763704, 4776019866458134139042

Offset: 3

N. J. A. Sloane, Simon Plouffe

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Sean A. Irvine, Table of n, a(n) for n = 3..250
Belgacem Bouras, A New Characterization of Catalan Numbers Related to Hankel Transforms and Fibonacci Numbers, Journal of Integer Sequences, 16 (2013), #13.3.3.
M. Dougherty, C. French, B. Saderholm, W. Qian, Hankel Transforms of Linear Combinations of Catalan Numbers, J. Int. Seq. 14 (2011) # 11.5.1.

A diagonal of A058087.

Cf. A000179, A000425.

Conjecture: 2*(-252307*n + 1041077)*a(n) + (504614*n^2 - 3362985*n + 5118150)*a(n-1) + (1280831*n^2 - 7397886*n + 6461565)*a(n-2) + (746598*n^2 - 2913543*n - 1336090)*a(n-3) + (-405481*n^2 + 6175011*n - 15469320)*a(n-4) + (-375862*n^2 + 4098537*n - 8846430)*a(n-5) + 2*(-187931*n + 560630)*a(n-6) = 0. - R. J. Mathar, Nov 02 2015
a(n) = round(2*n*(4*exp(-2)*((n+3/2)*BesselK(n-1,2) - (n-9/2)*BesselK(n-2,2)) + (-1)^n)/3) for n > 11 assuming the recurrence is correct. - Mark van Hoeij, Jun 09 2019
Conjecture: a(n) + 2*a(n+p) + a(n+2*p) is divisible by p for any prime p except 3. - Mark van Hoeij, Jun 10 2019

A258338 Ternary ménage problem: number of seating arrangements for n opposite-sex couples around a circular table such that no spouses and no triples of the same sex seat next to each other. Seats are labeled.

Original entry on oeis.org

0, 8, 84, 3456, 219120, 19281600, 2324085120, 370554347520, 74897768655360, 18761274367718400, 5708008284647961600, 2072453585852572876800, 885341762559654194995200, 439630143301970662603161600, 251099117378080818090596352000, 163464570058143774978660630528000

Offset: 1

Max Alekseyev, May 27 2015

nonn

Conjecture: (a(n)/n!^2)^(1/n) ~ (3+sqrt(5))/2. - Vaclav Kotesovec, May 29 2015

Max Alekseyev, Table of n, a(n) for n = 1..100
M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12; arXiv:1510.07926 [math.CO], 2015-2016.

Cf. A114939 (counts up to rotations and reflections)

Cf. A059375, A094047, A000179, A114938, A137729, A137730, A137737, A137749.

a[1] = 0;
a[n_] := n! Sum[(-1)^j (n-j)! SeriesCoefficient[ SeriesCoefficient[ Tr[ MatrixPower[{{0, 1, 0, y^2, 0, 0}, {z y^2, 0, 1, 0, y^2, 0}, {z y^2, 0, 0, 0, y^2, 0}, {0, 1, 0, 0, 0, z}, {0, 1, 0, y^2, 0, z}, {0, 0, 1, 0, y^2, 0}}, 2n]], {y, 0, 2n}], {z, 0, j}], {j, 0, n}];
Array[a, 16] (* Jean-François Alcover, Dec 03 2018, from 1st PARI program *)

{ a(n) = if(n<2, 0, n! * sum(j=0,n, (-1)^j * (n-j)! *polcoeff( polcoeff( trace([0, 1, 0, y^2, 0, 0; z*y^2, 0, 1, 0, y^2, 0; z*y^2, 0, 0, 0, y^2, 0; 0, 1, 0, 0, 0, z; 0, 1, 0, y^2, 0, z; 0, 0, 1, 0, y^2, 0]^(2*n)), 2*n,y) ,j,z)) ); }

{ a(n) = if(n<2, 0, n! *  polcoeff( serlaplace( polcoeff( trace([-y, z*y, z, 0, z*y, -y; -y, (z - 1)*y, 0, (z - 1)*y^2, z*y, -y; 0, (z - 1)*y, 0, (z - 1)*y^2, 0, -y; -y, 0, z - 1, 0, (z - 1)*y, 0; -y, z*y, z - 1, 0, (z - 1)*y, -y; -y, z*y, 0, z*y^2, z*y, -y]^n), n, y) )/(1-z) + O(z^(n+1)), n, z) ) }

a(n) = A114939(n) * 4 * n.

A354408 Triangle read by rows of generalized ménage numbers: T(n,k) is the number of permutations pi in S_n such that pi(i) != i and pi(i) != i+k (mod n) for all i; n, 1 <= k < n.

Original entry on oeis.org

0, 1, 1, 2, 4, 2, 13, 13, 13, 13, 80, 82, 80, 82, 80, 579, 579, 579, 579, 579, 579, 4738, 4740, 4738, 4752, 4738, 4740, 4738, 43387, 43387, 43390, 43387, 43387, 43390, 43387, 43387, 439792, 439794, 439792, 439794, 440192, 439794, 439792, 439794, 439792

Offset: 2

Peter Kagey, May 25 2022

Conjectures: (Start)
T(n,1) <= T(n,k) for all 1 < k < n.
With the exception of T(6,3) = 80, T(n,k) > T(n,1) whenever gcd(n,k) > 1. (End)

			Triangle begins:
  n\k|     1     2     3     4     5     6     7     8
-----+------------------------------------------------
   2 |     0
   3 |     1     1
   4 |     2     4     2
   5 |    13    13    13    13
   6 |    80    82    80    82    80
   7 |   579   579   579   579   579   579
   8 |  4738  4740  4738  4752  4738  4740  4738
   9 | 43387 43387 43390 43387 43387 43390 43387 43387
  ...

Brian Moehring, Counting permutations pi in S_n such that pi(i) != i and pi(i) - k != i mod n, Mathematics Stack Exchange.

Cf. A277256, A341439, A354409 (record values in rows).

Cf. A000179 (column 1), A354152 (column 2).

from sympy import Matrix
def A354408(n,k):
    return Matrix(n,n,lambda i,j:int(i!=j and i!=(j+k)%n)).per() # Pontus von Brömssen, May 31 2022

# This version, based on the formula in A277256, is much faster than the version using permanents, at least for large n.
from sympy import factorial,gcd,sqrt
from sympy.abc import z
def A354408(n,k):
    k=gcd(n,k)
    F=((1-sqrt(1+4*z))/2)**(2*(n//k))+((1+sqrt(1+4*z))/2)**(2*(n//k))
    p=(F**k).series(z,0,n+1)
    return sum((-1)**j*factorial(n-j)*p.coeff(z,j) for j in range(n+1)) # Pontus von Brömssen, Jun 02 2022

T(n,1) = A000179(n).
T(n,k) = T(n,n-k).
T(n,k) = A341439(k,n).
T(n,k) = A000179(n) if k is coprime to n.
T(n,j) = T(n,k) if gcd(n,j) = gcd(n,k). - Pontus von Brömssen, May 30 2022
Conjecture: T(n,j) < T(n,k) if gcd(n,j) < gcd(n,k) and (n,k) != (6,3). - Pontus von Brömssen, May 31 2022

cp's OEIS Frontend

A300480 Rectangular array read by antidiagonals: a(m,n) = 2 * Integral_{t>=0} T_n((t+m)/2)*exp(-t)*dt, m>=0, n>=0, where T_n(x) is n-th Chebyshev polynomial of first kind.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A300481 Rectangular array read by antidiagonals: a(m,n) = 2 * Integral_{t>=0} T_n((t-m)/2)*exp(-t)*dt, m>=0, n>=0, where T_n(x) is n-th Chebyshev polynomial of first kind.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A000033 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

SageMath

Formula

Extensions

A184965 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 6 for all i.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A078480 Number of permutations p of {1,2,...,n} such that |p(i)-i| != 1 for all i.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A189389 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 5 for all i.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A000159 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

A300480 Rectangular array read by antidiagonals: a(m,n) = 2 * Integral_{t>=0} T_n((t+m)/2)exp(-t)dt, m>=0, n>=0, where T_n(x) is n-th Chebyshev polynomial of first kind.

A300481 Rectangular array read by antidiagonals: a(m,n) = 2 * Integral_{t>=0} T_n((t-m)/2)exp(-t)dt, m>=0, n>=0, where T_n(x) is n-th Chebyshev polynomial of first kind.