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
Examples
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.
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.
Crossrefs
Programs
-
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 *) -
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
-
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
-
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
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]
Extensions
T(1,1) set to -1 to accord with Riordan by William P. Orrick, Aug 09 2020
Comments