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

%I #60 Jul 23 2022 19:26:36

%S 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,

%T 80,2,35,140,469,994,1477,1344,579,2,48,280,1232,3660,7888,11672,

%U 10800,4738,2,63,504,2856,11268,32958,70152,104256,97434,43387

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

%C 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

%D I. Kaplansky and J. Riordan, The probleme des menages, Scripta Mathematica, 1946, 12 (2), 113-124.

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 198.

%D 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

%H G. C. Greubel, <a href="/A058087/b058087.txt">Rows n = 0..50 of the triangle, flattened</a>

%H I. Kaplansky and J. Riordan, <a href="/A000166/a000166_1.pdf">The problème des ménages</a>, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]

%H Anthony C. Robin, <a href="http://www.jstor.org/stable/40378205">90.72 Circular Wife Swapping</a>, The Mathematical Gazette, Vol. 90, No. 519 (Nov., 2006), pp. 471-478.

%F 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

%F 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

%F 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]

%e The triangle begins:

%e 1;

%e 2, -1;

%e 2, 0, 0;

%e 2, 3, 0, 1;

%e 2, 8, 4, 8, 2;

%e 2, 15, 20, 40, 30, 13;

%e 2, 24, 60, 152, 210, 192, 80;

%e 2, 35, 140, 469, 994, 1477, 1344, 579;

%e 2, 48, 280, 1232, 3660, 7888, 11672, 10800, 4738;

%e 2, 63, 504, 2856, 11268, 32958, 70152, 104256, 97434, 43387;

%e The polynomials start:

%e [0] 1;

%e [1] 2*x - 1;

%e [2] 2*x^2;

%e [3] 2*x^3 + 3*x^2 + 1;

%e [4] 2*x^4 + 8*x^3 + 4*x^2 + 8*x + 2;

%e [5] 2*x^5 + 15*x^4 + 20*x^3 + 40*x^2 + 30*x + 13.

%p U := proc(n) if n = 0 then return 1 fi;

%p add((2*n/(2*n-k))*binomial(2*n-k, k)*(n-k)!*(x-1)^k, k=0..n) end:

%p W := proc(r, s) coeff(U(r), x, s ) end:

%p T := (n, k) -> W(n, n-k): seq(seq(T(n, k), k=0..n), n=0..9);

%t 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 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}]];

%t Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* _G. C. Greubel_, May 15 2021 *)

%o (SageMath)

%o a = [[1]]

%o for n in range(1, 10):

%o g = expand(

%o sum((x - 1)^ k * (2*n) * binomial(2*n-k, k) * factorial(n-k) / (2*n-k)

%o for k in range(0, n + 1)

%o )

%o )

%o coeffs = g.coefficients(sparse=False)

%o coeffs.reverse()

%o a.append(coeffs) # _William P. Orrick_, Aug 12 2020

%o (Sage)

%o 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) )

%o flatten([[A058087(n,k) for k in (0..n)] for n in (0..12)]) # _G. C. Greubel_, May 15 2021

%o (PARI) U(n,t)=sum(k=0,n, ((2*n/(2*n-k))*binomial(2*n-k,k)*(n-k)!*(t-1)^k));

%o print1(1,", "); for(n=1,9,forstep(k=n,0,-1,print1(polcoef(U(n,'x),k),", "))) \\ _Hugo Pfoertner_, Aug 30 2020

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

%Y Essentially a mirror image of A094314.

%K sign,easy,tabl,nice

%O 0,2

%A _N. J. A. Sloane_, Dec 02 2000

%E T(1,1) set to -1 to accord with Riordan by _William P. Orrick_, Aug 09 2020