A000033 -id:A000033 - 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

A000426 Coefficients of ménage hit polynomials.

Original entry on oeis.org

0, 1, 1, 1, 8, 35, 211, 1459, 11584, 103605, 1030805, 11291237, 135015896, 1749915271, 24435107047, 365696282855, 5839492221440, 99096354764009, 1780930394412009, 33789956266629001, 674939337282352360, 14157377139256183723, 311135096550816014651

Offset: 1

N. J. A. Sloane and Simon Plouffe

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 198.
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).
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.

David W. Wilson, Table of n, a(n) for n = 1..100
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]

Cf. A000179, A000271. A diagonal of A058057.

[0] cat [&+[(-1)^k*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[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 *)

a(n) = Sum_{k=2..n} (-1)^k*(2n-k-1)!*(n-k)!/((2n-2k)!*(k-2)!).
a(n) = A000033(n)/n.
a(n) = ((2*n-5)*a(n-1) + (5*n-11)*a(n-2) + (5*n-14)*a(n-3) + (2*n-5)*a(n-4) + 2*a(n-5))/2 for n >= 6.
Shorter recurrence: (14*n-67)*a(n) = (14*n^2-95*n+137)*a(n-1) + (14*n^2-105*n+180)*a(n-2) - 24*a(n-4) + (57-10*n)*a(n-3). - Vaclav Kotesovec, Oct 26 2012
a(n) ~ 2/e^2*(n-1)!. - Vaclav Kotesovec, Oct 26 2012
a(n) = round((exp(-2)*(8*BesselK(n,2) - (4*n-10)*BesselK(n-1,2)))) for n > 6. - Mark van Hoeij, Jun 09 2019
a(n)+2*a(n+p)+a(n+2*p) is divisible by p for any prime p. - Mark van Hoeij, Jun 13 2019

Edited by David W. Wilson, Dec 27 2007

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

A230113 Digital root of summed Fibonacci and Lucas digital roots indexed by numbers not divisible by 2, 3 or 5.

Original entry on oeis.org

3, 4, 5, 6, 6, 5, 4, 3, 4, 6, 6, 5, 4, 3, 3, 5, 6, 5, 4, 3, 3, 4, 5, 6, 5, 3, 3, 4, 5, 6, 6, 4, 3, 4, 5, 6, 6, 5, 4, 3, 4, 6, 6, 5, 4, 3, 3, 5, 6, 5, 4, 3, 3, 4, 5, 6, 5, 3, 3, 4, 5, 6, 6, 4, 3, 4, 5, 6, 6, 5, 4, 3, 4, 6, 6, 5, 4, 3, 3, 5, 6, 5, 4, 3, 3, 4, 5, 6, 5, 3, 3, 4, 5, 6, 6, 4

Offset: 1

Gary Croft, Dec 20 2013

32-beat repeating sequence is periodically palindromic starting at Length(40), then at Lengths (72)...(104)...(136)...(168)...{+32 terms ... repeat ... n}.

			Referencing A227896 (Fibo) and A233766 (Lucas): 1st Fibo term (1) + 1st Lucas term (2) = 3 = digital root 3. Likewise, 2nd Fibo term (4) + 2nd Lucas term (9) = 13 = digital root 4.

Cf. A007775, A227896, A233766, A000032, A000033.

Conjectures from Colin Barker, Sep 22 2019: (Start)
G.f.: x*(3 + x + x^2 + x^3 - x^5 - x^6 - x^7 + x^8 + 2*x^9 - x^11 - x^12 - x^13 + 2*x^15 + 4*x^16) / ((1 - x)*(1 + x^16)).
a(n) = a(n-1) - a(n-16) + a(n-17) for n>17.
(End)

cp's OEIS Frontend

A109469 Cumulative sum of coefficients of ménage hit polynomials (A000033).

Views

Author

Keywords

Crossrefs

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

A000426 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

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

A230113 Digital root of summed Fibonacci and Lucas digital roots indexed by numbers not divisible by 2, 3 or 5.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula