A000425 -id:A000425 - cp's OEIS frontend

A058087 Triangle read by rows, giving coefficients of the ménage hit polynomials ordered by descending powers. T(n, k) for 0 <= k <= n.

1, 2, -1, 2, 0, 0, 2, 3, 0, 1, 2, 8, 4, 8, 2, 2, 15, 20, 40, 30, 13, 2, 24, 60, 152, 210, 192, 80, 2, 35, 140, 469, 994, 1477, 1344, 579, 2, 48, 280, 1232, 3660, 7888, 11672, 10800, 4738, 2, 63, 504, 2856, 11268, 32958, 70152, 104256, 97434, 43387

Offset: 0

N. J. A. Sloane, Dec 02 2000

Riordan's book (page 197) notes that an alternative convention is to put 2 in the first row of the triangle. - William P. Orrick, Aug 09 2020

			The triangle begins:
  1;
  2, -1;
  2,  0,   0;
  2,  3,   0,    1;
  2,  8,   4,    8,     2;
  2, 15,  20,   40,    30,    13;
  2, 24,  60,  152,   210,   192,    80;
  2, 35, 140,  469,   994,  1477,  1344,    579;
  2, 48, 280, 1232,  3660,  7888, 11672,  10800,  4738;
  2, 63, 504, 2856, 11268, 32958, 70152, 104256, 97434, 43387;
The polynomials start:
  [0] 1;
  [1] 2*x - 1;
  [2] 2*x^2;
  [3] 2*x^3 + 3*x^2 + 1;
  [4] 2*x^4 + 8*x^3 + 4*x^2 + 8*x + 2;
  [5] 2*x^5 + 15*x^4 + 20*x^3 + 40*x^2 + 30*x + 13.

I. Kaplansky and J. Riordan, The probleme des menages, Scripta Mathematica, 1946, 12 (2), 113-124.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 198.
Tolman, L. Kirk, "Extensions of derangements", Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Humboldt State University, Arcata, California, September 5-7, 1979. Vol. 26. Utilitas Mathematica Pub., 1980. See Table I. - N. J. A. Sloane, Jul 06 2014

G. C. Greubel, Rows n = 0..50 of the triangle, flattened
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
Anthony C. Robin, 90.72 Circular Wife Swapping, The Mathematical Gazette, Vol. 90, No. 519 (Nov., 2006), pp. 471-478.

Diagonals give A000179, A000425, A000033, A000159, A000181, A000185, A058089, A058090.

Essentially a mirror image of A094314.

U := proc(n) if n = 0 then return 1 fi;
add((2*n/(2*n-k))*binomial(2*n-k, k)*(n-k)!*(x-1)^k, k=0..n) end:
W := proc(r, s) coeff(U(r), x, s ) end:
T := (n, k) -> W(n, n-k): seq(seq(T(n, k), k=0..n), n=0..9);

u[n_] := Sum[ 2*n/(2*n-k)*Binomial[2*n-k, k]*(n-k)!*(x-1)^k, {k, 0, n}]; w[r_, s_] := Coefficient[u[r], x, s]; a[n_, k_] := w[n, n-k]; a[0, 0]=1; Table[a[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 10 2012, translated from Maple *)
T[n_, k_]:= If[n==0, 1, Sum[(-1)^j*(2*n*(k-j)!/(n+k-j))*Binomial[j+n-k, n - k]*Binomial[n+k-j, n-k+j], {j, 0, k}]];
Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, May 15 2021 *)

U(n,t)=sum(k=0,n, ((2*n/(2*n-k))*binomial(2*n-k,k)*(n-k)!*(t-1)^k));
print1(1,", "); for(n=1,9,forstep(k=n,0,-1,print1(polcoef(U(n,'x),k),", "))) \\ Hugo Pfoertner, Aug 30 2020

def A058087(n,k): return 1 if (n==0) else sum( (-1)^j*(2*n*factorial(k-j)/(n+k-j))*binomial(j+n-k, n-k)*binomial(n+k-j, n-k+j) for j in (0..k) )
flatten([[A058087(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 15 2021

a = [[1]]
for n in range(1, 10):
    g = expand(
        sum((x - 1)^ k * (2*n) * binomial(2*n-k, k) * factorial(n-k) / (2*n-k)
            for k in range(0, n + 1)
        )
    )
    coeffs = g.coefficients(sparse=False)
    coeffs.reverse()
    a.append(coeffs) # William P. Orrick, Aug 12 2020

G.f.: (1-x*(y-1))*Sum_{n>=0} ( n!*(x*y)^n/(1+x*(y-1))^(2*n+1) ). - Vladeta Jovovic, Dec 14 2009
Row n of the triangle lists the coefficients of the polynomial U_n(t) = Sum_{k=0..n} (2*n/(2*n-k))*binomial(2*n-k,k)*(n-k)!*(t-1)^k, with higher order terms first (Kaplansky and Riordan). - William P. Orrick, Aug 09 2020
T(n, k) = Sum_{j=0..k} (-1)^j*(2*n*(k-j)!/(n+k-j))*binomial(n-k+j, n-k)*binomial(n+k-j, n-k+j), with T(0, k) = 1. - G. C. Greubel, May 15 2021 [Corrected by Sean A. Irvine, Jul 23 2022]

T(1,1) set to -1 to accord with Riordan by William P. Orrick, Aug 09 2020

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

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

A000181 Coefficients of ménage hit polynomials.

Original entry on oeis.org

2, 15, 60, 469, 3660, 32958, 328920, 3614490, 43341822, 563144725, 7880897892, 118177520295, 1890389939000, 32130521850972, 578260307815920, 10985555094348948, 219687969344126490, 4613039009310624795, 101479234383619208204, 2333872309936442446905

Offset: 4

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 = 4..250

A diagonal of A058087. Cf. A000179, A000425.

Conjecture: 3*(2111*n-8303)*(n-4)*(-9+2*n)^2*a(n) - (n-3)*(25332*n^4 - 377236*n^3 + 1898681*n^2 - 3320738*n + 484000)*a(n-1) - 2*(n-4)*(12140*n^4 - 118152*n^3 + 337063*n^2 - 377436*n + 225720)*a(n-2) + (1052*n^5 - 40656*n^4 + 266063*n^3 - 549153*n^2 + 49850*n + 655200)*a(n-3) +(263*n+640)*(n-3)*(-7+2*n)^2*a(n-4) = 0. - R. J. Mathar, Nov 02 2015

Conjecture: a(n) + 2*a(n+p) + a(n+2*p) is divisible by p for any prime p > 3. - Mark van Hoeij, Jun 10 2019

A094314 Triangle read by rows: T(n,k) = number of ways of seating n couples around a circular table so that exactly k married couples are adjacent (0 <= k <= n).

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 1, 0, 3, 2, 2, 8, 4, 8, 2, 13, 30, 40, 20, 15, 2, 80, 192, 210, 152, 60, 24, 2, 579, 1344, 1477, 994, 469, 140, 35, 2, 4738, 10800, 11672, 7888, 3660, 1232, 280, 48, 2, 43387, 97434, 104256, 70152, 32958, 11268, 2856, 504, 63, 2, 439792, 976000, 1036050, 695760, 328920, 115056, 30300, 6000, 840, 80, 2

Offset: 0

N. J. A. Sloane, based on a suggestion from Anthony C Robin, Jun 02 2004

The men and women alternate.

			Triangle begins:
     1;
     0,     1;
     0,     0,     2;
     1,     0,     3,    2;
     2,     8,     4,    8,    2;
    13,    30,    40,   20,   15,    2;
    80,   192,   210,  152,   60,   24,   2;
   579,  1344,  1477,  994,  469,  140,  35,  2;
  4738, 10800, 11672, 7888, 3660, 1232, 280, 48, 2;
  ...

I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. See Table 1.
Tolman, L. Kirk, "Extensions of derangements", Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Humboldt State University, Arcata, California, September 5-7, 1979. Vol. 26. Utilitas Mathematica Pub., 1980. See Table I.

Alois P. Heinz, Rows n = 0..140, flattened
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
Anthony C. Robin, 90.72 Circular Wife Swapping, The Mathematical Gazette, Vol. 90, No. 519 (Nov., 2006), pp. 471-478.
L. Takacs, On the probleme des menages, Discr. Math. 36 (3) (1981) 289-297, Table 1.

Essentially a mirror image of A058087, which has much more information.

Diagonals give A000179, A000425, A000033, A000159, A000181, etc.

T[n_, k_]:= If[n<2, (1+(-1)^(n-k))/2, Sum[(-1)^j*(2*n*(n-k-j)!/(2*n-k-j))* Binomial[k+j, k]*Binomial[2*n-k-j, k+j], {j, 0, n-k}]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, May 15 2021 *)

def A094314(n,k): return (1+(-1)^(n+k))/2 if (n<2) else sum( (-1)^j*(2*n*factorial(n-k-j)/(2*n-k-j))*binomial(k+j, k)*binomial(2*n-k-j, k+j) for j in (0..n-k) )
flatten([[A094314(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 15 2021

Sum_{k=0..n} T(n,k) = n!.

T(n, k) = Sum_{j=0..n-k} (-1)^j*(2*n*(n-k-j)!/(2*n-k-j))*binomial(k+j, k) * binomial(2*n-k-j, k+j) for n > 1, T(0, 0) = T(1, 1) = 1, and T(1, 0) = 0. - G. C. Greubel, May 15 2021

A000185 Coefficients of ménage hit polynomials.

Original entry on oeis.org

2, 24, 140, 1232, 11268, 115056, 1284360, 15596208, 204710454, 2888897032, 43625578836, 702025263328, 11993721979336, 216822550325472, 4135337882588880, 82986434235959712, 1747976804189353962, 38559791049947726328, 889047923669760546140

Offset: 5

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 = 5..250

A diagonal of A058087. Cf. A000179, A000425.

Conjecture: +4*(210968408*n^2 -1603518486*n +2343057493) *a(n) +(-843873632*n^3 -4039256254*n^2 +144382575631*n -553812368850) *a(n-1) +(10453330198*n^3 -175111274403*n^2 +798927275864*n -639098546595) *a(n-2) +(10059264970*n^3 -98879552663*n^2 +170576803994*n -134993524720) *a(n-3) +(470894110*n^3 -5178116941*n^2 +108179055193*n -215961878286) *a(n-4) +(1708832970*n^3 -29554327949*n^2 +137453332457*n -152801514054) *a(n-5) +3*(569610990*n^2 -3742686463*n +4740040723) *a(n-6)=0. - R. J. Mathar, Nov 02 2015
Conjecture: (241*n-1066) *(2*n-11) *(-5+n)^2 *a(n) +(-482*n^5 +10099*n^4 -79756*n^3 +285961*n^2 -426904*n +149292) *a(n-1) -(2*n-9) *(n-3) *(248*n^3 -2229*n^2 +5065*n -7134) *a(n-2) +(-14*n^5 -49*n^4 -619*n^3 +13174*n^2 -51690*n +61248) *a(n-3) -(n-3) *(n-4) *(7*n-87) *(2*n-7) *a(n-4)= 0. - R. J. Mathar, Nov 02 2015
a(n)+2*a(n+p)+a(n+2*p) is divisible by p for any prime except 3 and 5. - Mark van Hoeij, Jun 13 2019

A058089 Coefficients of ménage hit polynomials.

Original entry on oeis.org

2, 35, 280, 2856, 30300, 349734, 4351368, 58217640, 834296862, 12759002305, 207501063952, 3577028170736, 65167077604440, 1251273416561196, 25258559758736880, 534813397441926960, 11852765770416416538, 274422835213034666655

Offset: 6

N. J. A. Sloane, Dec 02 2000

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.

A diagonal of A058087. Cf. A000179, A000425.

A058090 Coefficients of ménage hit polynomials.

Original entry on oeis.org

2, 48, 504, 6000, 73260, 951984, 13152984, 193295952, 3016469790, 49879061920, 871884630672, 16072938332064, 311769325656312, 6349343550308640, 135485465497382160, 3023380765038115680, 70429101211136913498, 1709801309366361996624

Offset: 7

N. J. A. Sloane, Dec 02 2000

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.

A diagonal of A058087. Cf. A000179, A000425.

cp's OEIS Frontend

A058087 Triangle read by rows, giving coefficients of the ménage hit polynomials ordered by descending powers. T(n, k) for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

SageMath

Formula

Extensions

A000033 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

SageMath

Formula

Extensions

A000159 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A000181 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A094314 Triangle read by rows: T(n,k) = number of ways of seating n couples around a circular table so that exactly k married couples are adjacent (0 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A000185 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A058089 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Crossrefs

A058090 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References