A000179 -id:A000179 - cp's OEIS frontend

A000181 Coefficients of ménage hit polynomials.

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

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

A003435 Number of directed Hamiltonian circuits on n-octahedron with a marked starting node.

Original entry on oeis.org

8, 192, 11904, 1125120, 153262080, 28507207680, 6951513784320, 2153151603671040, 826060810479206400, 384600188992919961600, 213656089636192754073600, 139620366072628402087526400, 106033731334825319789808844800

Offset: 2

N. J. A. Sloane

Also called the relaxed menage problem (cf. A000179).

These are labeled and the order and starting point matter.

			n=2: label vertices of a square 1,2,3,4. Then the 8 Hamiltonian circuits are 1234, 1432, 2341, 2143, 3412, 3214, 4123, 4321; so a(2) = 8.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 2..100
Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519.
D. Singmaster, Enumerating unlabeled Hamiltonian circuts, Preprint (1974).
D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.
D. Singmaster, Letter to N. J. A. Sloane, May 1975
Eric Weisstein's World of Mathematics, Cocktail Party Graph

Cf. A003436, A003437, A129348.

[(&+[ (-1)^k*2^(k+1)*n*Binomial(n, k)*Factorial(2*n-k-1): k in [0..n]]) : n in [2..20]]; // G. C. Greubel, Nov 17 2022

A003435 := n->add((-1)^k*binomial(n,k)*((2*n)/(2*n-k))*2^k*(2*n-k)!,k=0..n);

a[n_] := 2^n*n!*(2n-1)!!*Hypergeometric1F1[-n, 1-2n, -2]; Table[ a[n], {n, 2, 14}] (* Jean-François Alcover, Nov 04 2011 *)

a(n)=sum(k=0,n,(-1)^k*binomial(n,k)*((2*n)/(2*n-k))*2^k*(2*n-k)!) \\ Charles R Greathouse IV, Nov 04 2011

[sum( (-1)^k*2^(k+1)*n*binomial(n, k)*factorial(2*n-k-1) for k in (0..n)) for n in (2..20)] # G. C. Greubel, Nov 17 2022

For n >= 2, a(n) = Sum_{k=0..n}(-1)^k*binomial(n, k)*((2*n)/(2*n-k))*2^k*(2*n-k)!.
Conjecture: a(n) -(4*n^2 - 2*n + 5)*a(n-1) + 2*(n-1)*(4*n-17)*a(n-2) + 12*(n-1)*(n-2)*a(n-3) = 0. - R. J. Mathar, Oct 02 2013
Recurrence: (2*n-3)*a(n) = 2*n*(4*n^2 - 8*n + 5)*a(n-1) + 4*(n-1)*n*(2*n-1)*a(n-2). - Vaclav Kotesovec, Feb 12 2014
a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n+1/2) / exp(2*n+1). - Vaclav Kotesovec, Feb 12 2014
a(n) = -(-2)^(n+1)*n!*hypergeom([n, -n], [], 1/2). - Peter Luschny, Nov 10 2016

Name made more precise by Andrew Howroyd, May 14 2017

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

A127548 O.g.f.: Sum_{n>=0} n!*(x/(1+x)^2)^n.

Original entry on oeis.org

1, 1, 0, 1, 4, 19, 112, 771, 6088, 54213, 537392, 5867925, 69975308, 904788263, 12607819040, 188341689287, 3002539594128, 50878366664393, 913161208490016, 17304836525709097, 345279674107957524, 7235298537356113339

Offset: 0

Vladeta Jovovic, Jun 27 2007

a(n+1) = inverse binomial transform of A013999 = Sum_{k=0..n} binomial(n,k)*(-1)^(n-k)*A013999(k). - Emanuele Munarini, Jul 01 2013

Seiichi Manyama, Table of n, a(n) for n = 0..450

Cf. A000179, A078480, A013999, A000271, A000904, A078509.

A127548 := proc(n) if n = 0 then 1 ; else add(factorial(s)*(-1)^(n-s)*binomial(s+n-1,2*s-1),s=1..n) ; fi ; end: for n from 0 to 20 do printf("%d,",A127548(n)) ; od ; # R. J. Mathar, Jul 13 2007

nn = 21; CoefficientList[Series[Sum[n!*(x/(1 + x)^2)^n, {n, 0, nn}], {x, 0, nn}], x] (* Michael De Vlieger, Sep 04 2016 *)

import math
def binomial(n,m):
    a=1
    for k in range(n-m+1,n+1):
        a *= k
    return a//math.factorial(m)
def A127548(n):
    if n == 0:
        return 1
    a=0
    for s in range(1,n+1):
        a += (-1)**(n-s)*binomial(s+n-1,2*s-1)*math.factorial(s)
    return a
for n in range(30):
    print(A127548(n))
# R. J. Mathar, Oct 20 2009

a(n) = Sum_{s=1..n} (-1)^(n-s)*s!*C(s+n-1,2s-1) if n>=1, where C(a,b)=binomial(a,b). - R. J. Mathar, Jul 13 2007
G.f.: Q(0) where Q(k) = 1 + (2*k + 1)*x/( (1+x)^2- 2*x*(1+x)^2*(k+1)/(2*x*(k+1) + (1+x)^2/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Mar 08 2013
a(n) = A000271(n) + A000271(n-1). - Peter Bala, Sep 02 2016
a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Oct 31 2017

More terms from R. J. Mathar, Jul 13 2007

More terms from R. J. Mathar, Oct 20 2009

A273596 For n >= 2, a(n) is the number of slim rectangular diagrams of length n.

Original entry on oeis.org

1, 3, 9, 32, 139, 729, 4515, 32336, 263205, 2401183, 24275037, 269426592, 3257394143, 42615550453, 599875100487, 9040742057760, 145251748024649, 2478320458476795, 44755020000606961, 852823700470009056, 17101229029400788083, 359978633317886558801, 7936631162022905081707

Offset: 2

Tamas Dekany, May 26 2016

			The initial term is the diagram of the four element diamond shape lattice.

Vaclav Kotesovec, Table of n, a(n) for n = 2..400
P. Bala, Notes on A273596
Gábor Czédli, Tamás Dékány, Gergő Gyenizse, and Júlia Kulin, The number of slim rectangular lattices, Algebra Universalis, 2016, Volume 75, Issue 1, pp 33-50.

Cf. A273988, A000522, A143409, A000179, A000271, A000904, A127548.

Partial sums of A155857.

A273596 := proc (n) option remember; `if`(n = 2, 1, `if`(n = 3, 3, (n-2)*procname(n-1) + procname(n-2) + 2)) end: seq(A273596(n), n = 2..20); # Peter Bala, Jan 08 2017

x = 15;
SRectD = Table[0, {x}];
For[n = 2, n < x, n++,
For[a = 1, a < n, a++,
   For[b = 1, b <= n - a, b++,
    SRectD[[n]] +=
      Binomial[n - a - 1, b - 1]*
       Binomial[n - b - 1, a - 1]*(n - a - b)!;
    ]
   ]
  Print[n, " ", SRectD[[n]]]
]
(* Alternatively: *)
T[n_, k_] := HypergeometricPFQ[{k+1, k-n}, {}, -1];
Table[Sum[T[n,k], {k,0,n}], {n,0,22}] (* Peter Luschny, Oct 05 2017 *)

a(n)= sum(rps=1, n, sum(r=1, n, s = rps-r; binomial(n-r-1, s-1) * binomial(n-s-1, r-1) * (n-r-s)!)); \\ Michel Marcus, Jun 12 2016

a(n) = Sum_{1<=r,s; r+s<=n} binomial(n-r-1, s-1) * binomial(n-s-1, r-1) * (n-r-s)!.
a(n) ~ exp(2) * n! / n^2. - Vaclav Kotesovec, Jun 29 2016
a(n) = Sum_{k=0..n} hypergeom([k+1, k-n], [], -1). - Peter Luschny, Oct 05 2017
From Peter Bala, Jan 08 2018: (Start)
a(n) = Sum_{k = 0..n-2} k!*binomial(n+k-1, 2*k+1).
a(n) = (n - 2)*a(n-1) + a(n-2) + 2, with a(2) = 1, a(3) = 3.
a(n+2) = 1/n!*Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)* A000522(n)^2.
Row sums of array A143409 read as a triangle.
O.g.f.: Sum_{n >= 0} n!*x^(n+2)/(1 - x)^(2*n+2). Cf. A000179, A000271, A000904 and A127548.
O.g.f. with offset 0: 1/(1 - x) o 1/(1 - x) = 1 + 3*x + 9*x^2 + 32*x^3 + ..., where o denotes the white diamond multiplication of power series. See the Bala link for details. (End)

A321352 Triangle T(n,k) giving the number of permutations pi of {1,2,...,n} such that for all i, pi(i) is not in {i, i+1, ..., i+k-1} (mod n), with 0 <= k <= n - 1.

Original entry on oeis.org

1, 2, 1, 6, 2, 1, 24, 9, 2, 1, 120, 44, 13, 2, 1, 720, 265, 80, 20, 2, 1, 5040, 1854, 579, 144, 31, 2, 1, 40320, 14833, 4738, 1265, 264, 49, 2, 1, 362880, 133496, 43387, 12072, 2783, 484, 78, 2, 1, 3628800, 1334961, 439792, 126565, 30818, 6208, 888, 125, 2, 1

Offset: 1

Peter Kagey, Feb 25 2020

This is A008305 with the rows reversed.
First column is A000142 (factorial numbers).
Second column is A000166 (derangements).
Third column is A000179 (ménage numbers).
Fourth column is A000183 (discordant permutations)

			Table begins:
       1
       2,      1
       6,      2,     1
      24,      9,     2,     1
     120,     44,    13,     2,    1
     720,    265,    80,    20,    2,   1
    5040,   1854,   579,   144,   31,   2,  1
   40320,  14833,  4738,  1265,  264,  49,  2, 1
  362880, 133496, 43387, 12072, 2783, 484, 78, 2, 1

Peter Kagey, Table of n, a(n) for n = 1..276 (first 23 rows, flattened)

Cf. A008305.

Cf. A000142, A000166, A000179, A000183, A004307, A189389, A184965.

A324621 Number of permutations p of [1+n] such that n is the maximum of the number of elements in any integer interval [p(i)..i+(1+n)*[i

Original entry on oeis.org

0, 1, 1, 7, 31, 185, 1275, 10095, 90109, 895169, 9793829, 116998199, 1515196619, 21143666585, 316260079951, 5047672782687, 85623656678457, 1538245254809537, 29176112648650441, 582614412521648359, 12217688610474042487, 268445509189890555577

Offset: 0

Alois P. Heinz, Mar 09 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..449

Row n=1 of A324563 and column of A324564 (as array).

Cf. A000166, A000179.

a:= proc(n) option remember; `if`(n<5, [0, 1$2, 7, 31][n+1],
      ((2*n^4-3*n^3-2*n^2+n+4)*a(n-1) -(n^5-4*n^4+7*n^2+6*n-14)*
       a(n-2) -(n^5-2*n^4-4*n^3+2*n^2+13*n-12)*a(n-3)-(n-2)*
       (n^3+2*n^2+n-2)*a(n-4))/(n^3-n^2-2))
    end:
seq(a(n), n=0..23);

menage[n_] := If[n == 0, 1, 2n Sum[(-1)^k Binomial[2n-k, k] (n-k)!/(2n-k), {k, 0, n}]];
a[n_] := If[n == 0, 0, Subfactorial[n+1] - menage[n+1]];
a /@ Range[0, 21] (* Jean-François Alcover, Oct 28 2021 *)

a(n) = A000166(n+1) - A000179(n+1) for n < 0, a(0) = 0.

A324622 Number of permutations p of [2+n] such that n is the maximum of the number of elements in any integer interval [p(i)..i+(2+n)*[i

Original entry on oeis.org

0, 1, 1, 11, 60, 435, 3473, 31315, 313227, 3445641, 41341502, 537313583, 7520316423, 112771887719, 1803821926465, 30656189582521, 551659191788556, 10478765887885181, 209522984620760153, 4398943767896801309, 96755196700729056267, 2224901906327124750355

Offset: 0

Alois P. Heinz, Mar 09 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..448

Row n=2 of A324563 and column of A324564 (as array).

Cf. A000179, A000183.

a(n) = A000179(n+2) - A000183(n+2).

A341439 Table of generalized ménage numbers read by antidiagonals upward: T(n,k) is the number of permutations pi in S_k such that pi(i) != i, i+n (mod k) for all i; n, k >= 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 0, 0, 1, 2, 0, 1, 2, 4, 13, 0, 0, 1, 2, 13, 80, 0, 1, 1, 9, 13, 82, 579, 0, 0, 2, 2, 13, 80, 579, 4738, 0, 1, 1, 4, 44, 82, 579, 4740, 43387, 0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 0, 1, 2, 9, 13, 265, 579, 4752, 43390, 439794, 4890741

Offset: 1

Peter Kagey, Feb 11 2021

The recurrence for the second row comes from Doron Zeilberger's MENAGE program, available via the arXiv reference.

			Table begins:
n\k | 1 2 3 4  5   6    7     8
----+--------------------------
  1 | 0 0 1 2 13  80  579  4738
  2 | 0 1 1 4 13  82  579  4740
  3 | 0 0 2 2 13  80  579  4738
  4 | 0 1 1 9 13  82  579  4752
  5 | 0 0 1 2 44  80  579  4738
  6 | 0 1 2 4 13 265  579  4740
  7 | 0 0 1 2 13  80 1854  4738
  8 | 0 1 1 9 13  82  579 14833

D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Cf. A000166, A000179, A277256, A354408.

T(n,n) = A000166(n) for n >= 1.
T(1,k) = A000179(k).
T(k-1,k) = A000179(k) for k >= 2.
T(n,k) = T(n+k, k).
T(2,k) = k*T(2,k-1) + 3*T(2,k-2) + (-2*k+6)*T(2,k-3) - 3*T(2,k-4) + (k-6)*T(2,k-5) + T(2,k-6) for k > 8.
T(n,k) = A277256(gcd(n,k),k/gcd(n,k)). - Pontus von Brömssen, May 31 2022

cp's OEIS Frontend

A000181 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A000426 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A003435 Number of directed Hamiltonian circuits on n-octahedron with a marked starting node.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

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

A127548 O.g.f.: Sum_{n>=0} n!*(x/(1+x)^2)^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A273596 For n >= 2, a(n) is the number of slim rectangular diagrams of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A321352 Triangle T(n,k) giving the number of permutations pi of {1,2,...,n} such that for all i, pi(i) is not in {i, i+1, ..., i+k-1} (mod n), with 0 <= k <= n - 1.

Views

Author

Keywords