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,2

Comments

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

References

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

Links

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.

Formula

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]

Example

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.

Maple

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);

Mathematica

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 *)

Prog

(SageMath)
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
(Sage)
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
(PARI) 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

Crossrefs

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

Essentially a mirror image of A094314.

Sequence in context: A287411 A053796 A029391 * A240753 A202149 A236533

Adjacent sequences: A058084 A058085 A058086 * A058088 A058089 A058090

Keyword

sign,easy,tabl,nice

Author

N. J. A. Sloane, Dec 02 2000

Extensions

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

Status

approved