A000179 -id:A000179 - cp's OEIS frontend

A102761 Same as A000179, except that a(0) = 2.

2, -1, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123

Offset: 0

N. J. A. Sloane, Apr 04 2010, following a suggestion from Vladimir Shevelev

For any integer n>=0, 2 * Integral_{t=-2..2} T_n(t/2)*exp(-t)*dt = 4 * Integral_{z=-1..1} T_n(z)*exp(-2*z)*dz = a(n)*exp(2) - A300484(n)*exp(-2). - Max Alekseyev, Mar 08 2018

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.

Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Λ_n^3 and Λ_n(α,β,γ), arXiv:1104.4051 [math.CO], 2011.

Row m=2 in A300481.
Cf. A000023, A000179, A000186, A300484.
A000179, A102761, and A335700 are all essentially the same sequence but with different conventions for the initial terms a(0) and a(1). - N. J. A. Sloane, Aug 06 2020

{ A102761(n) = subst( serlaplace( 2*polchebyshev(n, 1, (x-2)/2)), x, 1); } \\ Max Alekseyev, Mar 06 2018

a(n) = Sum_{i=0..n} A127672(n,i) * A000023(i). - Max Alekseyev, Mar 06 2018
a(n) = A300481(2,n) = A300480(-2,n). - Max Alekseyev, Mar 06 2018
a(n) = A335391(0,n) (Touchard). - William P. Orrick, Aug 29 2020

Changed a(0)=2 (making the sequence more consistent with existing formulae) by Max Alekseyev, Mar 06 2018

A335700 A variant of A000179 and A102761.

Original entry on oeis.org

1, 0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123

Offset: 0

N. J. A. Sloane, Aug 06 2020

nonn

William Orrick, Postings to Sequence Fans Mailing List, August 2020

A000179, A102761, and the present sequence are all essentially the same sequence but with different conventions for the initial terms a(0) and a(1).

A000270 For n >= 2, a(n) = b(n+1)+b(n)+b(n-1), where the b(i) are the ménage numbers A000179; a(0)=a(1)=1.

Original entry on oeis.org

1, 1, 0, 3, 16, 95, 672, 5397, 48704, 487917, 5373920, 64547175, 839703696, 11762247419, 176509466560, 2825125339305, 48040633506048, 864932233294681, 16436901752820288, 328791893988472843, 6905593482159150480, 151941269284478380119, 3495011687269591273312

Offset: 0

N. J. A. Sloane

The old name (in the 1973 Handbook) was "Discordant permutations".
For n >= 2, a(n) is the number of permutations of [n+1] discordant with both the identity permutation and a permutation consisting of one 1-cycle and one n-cycle. - William P. Orrick, Aug 03 2020
The term a(0) = 1, which comes from the table on page 118 of Touchard's 1953 Scripta Math. paper is possibly in error. Equation (3) in Touchard's 1934 Comptes Rendus article produces a(0) = 0, and the formulas following equation (30) on page 117 of his 1953 paper give incorrect results unless a(0) = 0. - William P. Orrick, Aug 07 2020

			From _William P. Orrick_, Aug 07 2020: (Start)
There are no permutations of 123 discordant with both 123 and 132, so a(2) = 0; the permutations of 1234 discordant with both 1234 and 1342 are 2413, 3421, and 4123, so a(3) = 3.
Touchard (1953), p. 117, writes a(4) + a(0) for the number of permutations discordant with 12345 and 13254. There are 16 = 4*2*2 such permutations, obtained by letting (x,y) be one of (2,3), (3,2), (4,5), (5,4), then placing x in position 1, and finally, if (x,y) is (2,3) or (3,2), placing 4, 5 (in either order) in positions 2, 3 while placing 1, y (in either order) in positions 4, 5, or, if (x,y) is (4,5) or (5,4), placing 1, y (in either order) in positions 2, 3 while placing 2, 3 (in either order) in positions 4, 5. Hence Touchard's expression gives the correct result, assuming a(0) = 0.
(End)

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).
J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 109-119.

Alois P. Heinz, Table of n, a(n) for n = 0..175
Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See 33.
J. Touchard, Sur un problème de permutations, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.

Cf. A000179, A335391.

a:= n-> coeftayl(1+(1-x)/(1+x)*add(k*k!*(x/(1+x)^2)^k, k=0..n), x=0, n):
seq(a(n), n=0..25); # Alois P. Heinz, Sep 24 2008
# second Maple program:
A000270 := proc(n) if n <= 1 then 1 else n * add((-1)^(n-s)*s!*binomial(s+n-1, 2*s-1), s=1..n) fi end; seq(A000270(n), n=0..30);  # Mark van Hoeij, May 12 2013

max = 20; f[x_] := 1+(1-x)/(1+x)*Sum[ n*n!*(x/(1+x)^2)^n, {n, 0, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Dec 09 2011, after Vladeta Jovovic *)

G.f.: 1+(1-x)/(1+x)*Sum_{n>=0} n*n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 29 2007
D-finite with recurrence: (n-3)*a(n) = (n-3)*n*a(n-1) + (n-3)*n*a(n-2) + n*a(n-3). - Vaclav Kotesovec, Mar 15 2014
a(n) ~ (n+1)! / exp(2). - Vaclav Kotesovec, Mar 15 2014
a(n) = A335391(1,n) for n >= 1. - William P. Orrick, Aug 03 2020

More terms from Alois P. Heinz, Sep 24 2008

Entry revised by N. J. A. Sloane, Jul 23 2020. Thanks to William P. Orrick for suggesting that this sequence needed a better definition. The initial terms a(0)=a(1)=1 have been preserved in order to agree with the sequence in Touchard's 1953 paper.

A193356 If n is even then 0, otherwise n.

Original entry on oeis.org

1, 0, 3, 0, 5, 0, 7, 0, 9, 0, 11, 0, 13, 0, 15, 0, 17, 0, 19, 0, 21, 0, 23, 0, 25, 0, 27, 0, 29, 0, 31, 0, 33, 0, 35, 0, 37, 0, 39, 0, 41, 0, 43, 0, 45, 0, 47, 0, 49, 0, 51, 0, 53, 0, 55, 0, 57, 0, 59, 0, 61, 0, 63, 0, 65, 0, 67, 0, 69, 0, 71, 0, 73, 0, 75

Offset: 1

José María Grau Ribas, Jul 24 2011

Multiplicative with a(2^e)=0 if e>0 and a(p^e)=p^e for odd primes p. - R. J. Mathar, Aug 01 2011
A005408 and A000004 interleaved (the usual OEIS policy is not to include sequences like this where alternate terms are zero; this is an exception). - Omar E. Pol, Feb 02 2013
Row sums of A057211. - Omar E. Pol, Mar 05 2014
Column k=2 of triangle A196020. - Omar E. Pol, Aug 07 2015
a(n) is the determinant of the (n+2) X (n+2) circulant matrix with the first row [0,0,1,1,...,1]. This matrix is closely linked with the famous ménage problem (see also comments of Vladimir Shevelev in sequence A000179). Namely it defines the class of permutations p of 1,2,...,n+2 such that p(i)<>i and p(i)<>i+1 for i=1,2,...,n+1, and p(n+2)<>1,n+2. And a(n) is also the difference between the number of even and odd such permutations. - Dmitry Efimov, Feb 02 2016

Franz Lemmermeyer, Reciprocity Laws. From Euler to Eisenstein, Springer, 2000, p. 237, eq. (8.5).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
C. Kravvaritis, Determinant evaluations for binary circulant matrices, Special Matrices, V2(1) (2014), 187-199.
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).

Cf. A000004, A000010, A005408, A027656, A042948, A057211, A196020.

I:=[1,0,3,0]; [n le 4 select I[n] else 2*Self(n-2)-Self(n-4): n in [1..80]]; // Vincenzo Librandi, Feb 24 2014

A193356:=n->(1-(-1)^n)*n/2: seq(A193356(n), n=1..100); # Wesley Ivan Hurt, Aug 07 2015

Mathematica
```
Table[PowerMod[n,n,2*n], {n,200}]
```

a(n)=if(n%2,n) \\ Charles R Greathouse IV, Jul 24 2011

A193356 = [i if i%2 else 0 for i in range(1, 101)] # Jwalin Bhatt, Jun 17 2025

a(n) = n^k mod 2n, for any k>=2, also for k=n. [extended by Wolfdieter Lang, Dec 21 2011]
Dirichlet g.f.: (1-2^(1-s))*zeta(s-1). - R. J. Mathar, Aug 01 2011
G.f.: x*(1+x^2)/(1-x^2)^2. - Philippe Deléham, Feb 13 2012
a(n) = A027656(A042948(n-1)) = (1-(-1)^n)*n/2. - Bruno Berselli, Feb 19 2012
a(n) = n * (n mod 2). - Wesley Ivan Hurt, Jun 29 2013
G.f.: Sum_{n >= 1} A000010(n)*x^n/(1 + x^n). - Mircea Merca, Feb 22 2014
a(n) = 2*a(n-2)-a(n-4), for n>4. - Wesley Ivan Hurt, Aug 07 2015
E.g.f.: x*cosh(x). - Robert Israel, Feb 03 2016
a(n) = Product_{k=1..floor(n/2)}(sin(2*Pi*k/n))^2, for n >= 1 (with the empty product put to 1). Trivial for even n from the factor 0 for k = n/2. For odd n see, e.g., the Lemmermeyer reference, eq. (8.5) on p. 237. - Wolfdieter Lang, Aug 29 2016
a(n) = Sum_{k=1..n} (-1)^((n-k)*k). - Rick L. Shepherd, Sep 18 2020
a(n) = Sum_{k=1..n} (-1)^(1+gcd(k,n)) = Sum_{d | n} (-1)^(d+1)*phi(n/d), where phi(n) = A000010(n). - Peter Bala, Jan 14 2024
Dirichlet g.f.: DirichletLambda(s-1). - Michael Shamos, Jun 13 2025

A003436 Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.

Original entry on oeis.org

1, 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749, 113184512236563589997407

Offset: 0

N. J. A. Sloane

Also called the relaxed ménage problem (cf. A000179).
a(n) can be seen as a subset of the unordered pairings of the first 2n integers (A001147) with forbidden pairs (1,2n) and (i,i+1) for all i in [1,2n-1] (all adjacent integers modulo 2n). The linear version of this constraint is A000806. - Olivier Gérard, Feb 08 2011
Number of perfect matchings in the complement of C_{2n} where C_{2n} is the cycle graph on 2n vertices. - Andrew Howroyd, Mar 15 2016
Also the number of 2-uniform set partitions of {1...2n} containing no two cyclically successive vertices in the same block. - Gus Wiseman, Feb 27 2019

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 = 0..200
F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.
Robert Cori and G. Hetyei, Counting partitions of a fixed genus, arXiv preprint arXiv:1710.09992 [math.CO], 2017.
M. Hazewinkel and V. V. Kalashnikov, Counting Interlacing Pairs on the Circle, CWI report AM-R9508 (1995)
Evgeniy Krasko, Igor Labutin, and Alexander Omelchenko, Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs, arXiv:1709.03218 [math.CO], 2017.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv preprint arXiv:1601.05073 [math.CO], 2016.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, The Electronic Journal of Combinatorics, 24(3) (2017), #P3.43.
D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.
Gus Wiseman, The a(5) = 293 interlacing chord diagrams.

Cf. A003435, A129348. A003437 gives unlabeled case.
First differences of A000806.
Column k=2 of A324428.
Cf. A000179, A000296, A000699, A001147, A005493, A170941, A190823, A278990, A306386, A306419, A322402, A324011, A324172, A324173.

A003436 := proc(n) local k;
      if n = 0 then 1
    elif n = 1 then 0
    else add( (-1)^k*binomial(n,k)*2*n/(2*n-k)*2^k*(2*n-k)!/2^n/n!,k=0..n) ;
    end if;
end proc: # R. J. Mathar, Dec 11 2013
A003436 := n-> `if`(n<2, 1-n, (-1)^n*2*hypergeom([n, -n], [], 1/2)):
seq(simplify(A003436(n)), n=0..18); # Peter Luschny, Nov 10 2016

a[n_] := (2*n-1)!! * Hypergeometric1F1[-n, 1-2*n, -2]; a[1] = 0;
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Apr 05 2013 *)
twounifll[{}]:={{}};twounifll[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@twounifll[Complement[set,s]]]/@Table[{i,j},{j,If[i==1,Select[set,2<#i+1&]]}];
Table[Length[twounifll[Range[n]]],{n,0,14,2}] (* Gus Wiseman, Feb 27 2019 *)

a(n) = A003435(n)/(n!*2^n).
a(n) = 2*n*a(n-1)-2*(n-3)*a(n-2)-a(n-3) for n>4. [Corrected by Vasu Tewari, Apr 11 2010, and by R. J. Mathar, Oct 02 2013]
G.f.: x + ((1-x)/(1+x)) * Sum_{n>=0} A001147(n)*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 27 2007
a(n) ~ 2^(n+1/2)*n^n/exp(n+1). - Vaclav Kotesovec, Aug 13 2013
a(n) = (-1)^n*2*hypergeom([n, -n], [], 1/2) for n >= 2. - Peter Luschny, Nov 10 2016

a(0)=1 prepended by Gus Wiseman, Feb 27 2019

A000186 Number of 3 X n Latin rectangles in which the first row is in order.

Original entry on oeis.org

1, 0, 0, 2, 24, 552, 21280, 1073760, 70299264, 5792853248, 587159944704, 71822743499520, 10435273503677440, 1776780700509416448, 350461958856515690496, 79284041282622163140608, 20392765404792755583221760, 5917934230798104348783083520, 1924427226324694427836833857536

Offset: 0

N. J. A. Sloane

Or number of n X n matrices with exactly one 1 and one 2 in each row and column which are not in the main diagonal, other entries 0. - Vladimir Shevelev, Mar 22 2010

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 183.
Dulmage, A. L.; McMaster, G. E. A formula for counting three-line Latin rectangles. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 279-289. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0392611 (52 #13428). - From N. J. A. Sloane, Apr 06 2012
I. Gessel, Counting three-line Latin rectangles, Lect. Notes Math, 1234(1986), 106-111. [From Vladimir Shevelev, Mar 25 2010]
Goulden and Jackson, Combin. Enum., Wiley, 1983 p. 284.
S. M. Jacob, The enumeration of the Latin rectangle of depth three..., Proc. London Math. Soc., 31 (1928), 329-336.
S. M. Kerawala, The enumeration of the Latin rectangle of depth three by means of a difference equation, Bull. Calcutta Math. Soc., 33 (1941), 119-127.
S. M. Kerawala, The asymptotic number of three-deep Latin rectangles, Bull. Calcutta Math. Soc., 39 (1947), 71-72.
Koichi, Yamamoto, An asymptotic series for the number of three-line Latin rectangles, J. Math. Soc. Japan 1, (1950). 226-241.
W. Moser. A generalization of Riordan's formula for 3Xn Latin rectangles, Discrete Math., 40, 311-313 [From Vladimir Shevelev, Mar 25 2010]
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 210.
V. S. Shevelev, Reduced Latin rectangles and square matrices with identical sums in the rows and columns [Russian], Diskret. Mat., 4 (1992), no. 1, 91-110.
V. S. Shevelev, A generalized Riordan formula for three-rowed Latin rectangles and its applications, DAN of the Ukraine, 2 (1991), 8-12 (in Russian) [From Vladimir Shevelev, Mar 25 2010]
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).
D. S. Stones, The many formulas for the number of Latin rectangles, Electron. J. Combin 17 (2010), A1.
RJ Stones, S Lin, X Liu, G Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1

N. J. A. Sloane, Table of n, a(n) for n = 0..207
F. Alayont and N. Krzywonos, Rook Polynomials in Three and Higher Dimensions, 2012. - From _N. J. A. Sloane_, Jan 02 2013
K. P. Bogart and J. Q. Longyear, Counting 3 by n Latin rectangles, Proc. Amer. Math. Soc., 54 (1976), 463-467.
S. M. Jacob, The enumeration of the Latin rectangle of depth three..., Proc. London Math. Soc., 31 (1928), 329-336.
S. M. Kerawala, The enumeration of the Latin rectangle of depth three by means of a difference equation, Bull. Calcutta Math. Soc., 33 (1941), 119-127. [Annotated scanned copy]
S. M. Kerawala, The asymptotic number of three-deep Latin rectangles, Bull. Calcutta Math. Soc., 39 (1947), 71-72. [Annotated scanned copy]
John Riordan, Table of a(0) - a(25), circa 1968
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha, beta, gamma), arXiv preprint arXiv:1104.4051[math.CO], 2011.
D. S. Stones and I. M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A 117 (2010), 204-215.
Index entries for sequences related to Latin squares and rectangles

Cf. A000512, A000166, A000179, A335700, A170904.

for n from 1 to 250 do t0:=0; for j from 0 to n do for k from 0 to n-j do t0:=t0 + (2^j/j!)*k!*binomial(-3*(k+1), n-k-j); od: od: t0:=n!*t0; lprint(n,t0); od:
Maple code for A000186 based on Eq. (30) of Riordan, p. 205. Eq. (30a) on p. 206 is wrong. - N. J. A. Sloane, Jan 21 2010. Thanks to Neven Juric for correcting an error in the definition of fU, Mar 01 2010. Additional comment and modifications of code due to changes in underlying sequences from William P. Orrick, Aug 12 2020: Eq. (30) and Eq. (30a) are, in fact, related to each other by a trivial transformation and are both valid. Current code is based on Eq. (30a).
# A000166
unprotect(D);
D := proc(n) option remember; if n<=1 then 1-n else (n-1)*(D(n-1)+D(n-2));fi; end;
[seq(D(n), n=0..30)];
# A000179
U := proc(n) if n=0 then 1 else add ((-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k), k=0..n); fi; end;
[seq(U(n), n=0..30)];
# A000186
K:=proc(n) local k; global D, U; add( binomial(n,k)*D(n-k)*D(k)*U(n-2*k), k=0..floor(n/2) ); end;
[seq(K(n), n=0..30)];
# another Maple program:
a:= proc(n) option remember; `if`(n<5, [1, 0, 0, 2, 24][n+1],
     ((n-1)*(n^2-2*n+2)*a(n-1) +(n-1)*(n-2)*(n^2-2*n+2)*a(n-2)
      +(n-1)*(n-2)*(n^2-2*n-2) *a(n-3)
      +2*(n-1)*(n-2)*(n-3)*(n^2-5*n+3) *a(n-4)
      -4*(n-2)*(n-3)*(n-4)*(n-1)^2 *a(n-5)) / (n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 02 2013

a[n_] := (t0 = 0; Do[t0 = t0 + (2^j/j!)*k!*Binomial[-3*(k+1), n-k-j], {j, 0, n}, {k, 0, n-j}]; n!*t0); Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Oct 13 2011, after Maple *)

# after Maple code based on Riordan's Eq. (30a)
d = [1,0]
for j in range(2,31):
    d.append((j - 1) * (d[-1] + d[-2]))
def u(n):
    if n == 0:
        return 1
    else:
        return sum((-1)^k * (2 * n) * binomial(2 * n - k, k) * factorial(n - k) / (2 * n - k) for k in range(0, n + 1))
def k(n):
    return sum(binomial(n, k) * d[n - k] * d[k] * u(n - 2 * k) for k in range(0, floor(n / 2) + 1))
[k(n) for n in range(0, 31)] # William P. Orrick, Aug 12 2020

a(n) = n!*Sum_{k+j<=n} (2^j/j!)*k!*binomial(-3*(k+1), n-k-j).
Note that the formula Sum_{k=0..n, k <= n/2} binomial(n, k)*D(n-k)*D(k)*U(n-2*k), where D() = A000166 and U() represents the menage numbers given by Riordan, p. 209 gives the wrong answers unless we set U(1) = -1 (or in other words we must take U() = A000179). With U(1) = 0 (see A335700) it produces A170904. See the Maple code here. - N. J. A. Sloane, Jan 21 2010, Apr 04 2010. Thanks to Vladimir Shevelev for clarifying this comment. Additional changes from William P. Orrick, Aug 12 2020
E.g.f.: exp(2*x) Sum(n>=0; n! x^n /(1+x)^(3*n+3)) from Gessel reference. - Wouter Meeussen, Nov 02 2013
a(n) ~ n!^2/exp(3). - Vaclav Kotesovec, Sep 08 2016
a(n+p)-2*a(n) is divisible by p for any prime p. - Mark van Hoeij, Jun 13 2019

Formula and more terms from Vladeta Jovovic, Mar 31 2001

Edited by N. J. A. Sloane, Jan 21 2010, Mar 04 2010, Apr 04 2010

A000271 Sums of ménage numbers.

Original entry on oeis.org

1, 0, 0, 1, 3, 16, 96, 675, 5413, 48800, 488592, 5379333, 64595975, 840192288, 11767626752, 176574062535, 2825965531593, 48052401132800, 865108807357216, 16439727718351881, 328839946389605643, 6906458590966507696

Offset: 0

N. J. A. Sloane

Permanent of the (0,1)-matrix having (i,j)-th entry equal to 0 iff this is on the diagonal or the first upper-diagonal. - Simone Severini, Oct 14 2004
Equivalently, number of permutations p of {1,2,...,n} such that p(i)-i not in {0,1}. - Andrew Howroyd, Sep 19 2017
From Vladimir Shevelev, Jun 21 2015: (Start)
Let 2*n!*V(n)=A137886(n) be the number of ways of seating n married couples at 2*n chairs arranged side-by-side in a straight line, men and women in alternate positions, so that no husband is next to his wife.
It is known [Riordan, Ch. 8, Th. 1, t=0] that, if 2*n!*U(n) is a solution of an analogous problem at a circular table, then U(n) = V(n) - V(n-1), n>=3, where U(n) = A000179(n). Thus V(n) = Sum_{i=3,...,n} A000179(i), n>=1, and comparing the initial conditions, we conclude that a(n) = V(n), n>=1. This gives a combinatorial interpretation for 2*n!*a(n).
(End)

			G.f. = 1 + x^3 + 3*x^4 + 16*x^5 + 96*x^6 + 675*x^7 + 5413*x^8 + ...

W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 2, p. 79.
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.

Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..100 from T. D. Noe)
W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901.
J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122.
J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122. [Annotated scanned copy]
Dmitry Efimov, Determinants of generalized binary band matrices, arXiv:1702.05655 [math.RA], 2017.
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 222.
Y. Li, Ménage Numbers and Ménage Permutations, J. Int. Seq. 18 (2015) 15.6.8
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]
M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480.

Cf. A000179, A000904, A001883, A137886, A292574. A diagonal of A058057.

[ &+[(-1)^(n-k)*Binomial(n+k, 2*k)*Factorial(k): k in [0..n]]: n in [0..21]]; // Bruno Berselli, Apr 11 2011

V := proc(n) local k; add( binomial(2*n-k,k)*(n-k)!*(x-1)^k, k=0..n); end; W := proc(r,s) coeff( V(r),x,s ); end; A000271 := n->W(n-2,0);

Table[Sum[(-1)^(n - k) k! Binomial[n + k, 2 k], {k, 0, n}], {n, 0, 22}] (* Jean-François Alcover, Apr 11 2011, after Paul Barry *)
RecurrenceTable[{a[0] == 1, a[1] == a[2] == 0, a[n] == (n - 1) a[n - 2] + (n - 1) a[n - 1] +  a[n - 3]}, a, {n, 30}] (* Harvey P. Dale, Jun 01 2012 *)
Table[(-1)^n HypergeometricPFQ[{1, -n, n + 1}, {1/2}, 1/4], {n, 20}] (* Michael Somos, May 28 2014 *)

a(n) = if(n, round( 2*exp(-2)*(besselk(n+1,2) + besselk(n,2)) ), 1) \\ Charles R Greathouse IV, May 11 2016

a(n) = (n - 1) a(n - 2) + (n - 1) a(n - 1) + a(n - 3).
From Paul Barry, Feb 08 2009: (Start)
G.f.: 1/(1+x-x/(1+x-x/(1+x-2x/(1+x-2x/(1+x-3x/(1+x-3x/(1+x-4x/(1+... (continued fraction);
a(n) = Sum_{k=0..n} binomial(2n-k,k)*(n-k)!*(-1)^k. (End)
a(n) = (-1)^n*hypergeom([1, -n, n+1],[1/2],1/4). - Mark van Hoeij, Nov 12 2009
a(n) = round( 2*exp(-2)*(BesselK(1+n,2) + BesselK(n,2)) ) for n>0. - Mark van Hoeij, Nov 12 2009
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n+k,2*k)*k!. - Paul Barry, Jun 23 2010
G.f.: Sum_{n>=0} n!*x^n/(1+x)^(2*n+1). - Ira M. Gessel, Jan 15 2013
a(n) ~ exp(-2)*n!. - Vaclav Kotesovec, Mar 10 2014
a(-1 - n) = -a(n) for all n in Z. - Michael Somos, May 28 2014
a(n) = Sum_{i=3..n} A000179(i), n>=1. - Vladimir Shevelev, Jun 21 2015
0 = a(n)*(-a(n+2) - a(n+3)) + a(n+1)*(+a(n+1) + 2*a(n+2) + a(n+3) - a(n+4)) + a(n+2)*(+a(n+2) + 2*a(n+3) - a(n+4)) + a(n+3)*(+a(n+3)) for all n in Z. - Michael Somos, Oct 16 2016

More terms from James Sellers, Aug 21 2000

More terms from Simone Severini, Oct 14 2004

A094047 Number of seating arrangements of n couples around a round table (up to rotations) so that each person sits between two people of the opposite sex and no couple is seated together.

Original entry on oeis.org

0, 0, 2, 12, 312, 9600, 416880, 23879520, 1749363840, 159591720960, 17747520940800, 2363738855385600, 371511874881100800, 68045361697964851200, 14367543450324474009600, 3464541314885011705344000, 946263209467217020194816000, 290616691739323132839591936000

Offset: 1

Matthijs Coster, Apr 29 2004

nonn

Also, the number of Hamiltonian directed circuits in the crown graph of order n.

Or the number of those 3 X n Latin rectangles (cf. A000186) the second row of which is a full cycle. - Vladimir Shevelev, Mar 22 2010

V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr.Mat.(J. of the Akademy of Sciences of Russia) 4(1992),91-110.

Seiichi Manyama, Table of n, a(n) for n = 1..253
M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12, arXiv:1510.07926, [math.CO], 2015-2016.
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Cf. A059375 (rotations are counted as different).

Cf. A000179, A000186, A114939, A137729, A306496.

A094047 := proc(n)
    if n < 3 then
        0;
    else
        (-1)^n*2*(n-1)!+n!*add( (-1)^j*(n-j-1)!*binomial(2*n-j-1,j),j=0..n-1) ;
    end if;
end proc: # R. J. Mathar, Nov 02 2015

Join[{0},Table[(-1)^n 2(n-1)!+n!Sum[(-1)^j (n-j-1)!Binomial[2n-j-1,j],{j,0,n-1}],{n,2,20}]] (* Harvey P. Dale, Mar 07 2012 *)

For n>1, a(n) = (-1)^n * 2 * (n-1)! + n! * Sum_{j=0..n-1} (-1)^j * (n-j-1)! * binomial(2*n-j-1,j). - Max Alekseyev, Feb 10 2008
a(n) = A059375(n) / (2*n) = A000179(n) * (n-1)!.
Conjecture: a(n) +(-n^2+2*n-3)*a(n-1) -(n-2)*(n^2-3*n+5)*a(n-2) -3*(n-2)*(n-3)*a(n-3) +(n-2)*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Nov 02 2015
Conjecture: (-n+2)*a(n) +(n-1)*(n^2-3*n+3)*a(n-1) +(n-2)*(n-1)*(n^2-3*n+3)*a(n-2) +(n-2)*(n-3)*(n-1)^2*a(n-3)=0. - R. J. Mathar, Nov 02 2015
a(n) = (n-1) * (n * (a(n-1) + a(n-2)) - 4 * (-1)^n * (n-3)!) for n > 3. - Seiichi Manyama, Jan 18 2020
a(n) = 2 * A306496(n). - Alois P. Heinz, Jun 19 2022

Better definition from Joel B. Lewis, Jun 30 2007

Formula and further terms from Max Alekseyev, Feb 10 2008

A008305 Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

The point is, we are counting permutations of [n] = {1,2,...,n} with the restriction that i cannot move by more than k places. Hence the phrase "permutations with restricted displacements". - N. J. A. Sloane, Mar 07 2014

The triangle could have been defined as an infinite square array by setting a(n,k) = n! for k >= n.

			a(4,3) = 9 because 9 permutations of {1,2,3,4} are allowed if each i can be placed on 3 positions i+0, i+1, i+2 (mod 4): 1234, 1423, 1432, 3124, 3214, 3412, 4123, 4132, 4213.
Triangle begins:
  1,
  1, 2,
  1, 2,   6,
  1, 2,   9,  24,
  1, 2,  13,  44,  120,
  1, 2,  20,  80,  265,   720,
  1, 2,  31, 144,  579,  1854,   5040,
  1, 2,  49, 264, 1265,  4738,  14833,  40320,
  1, 2,  78, 484, 2783, 12072,  43387, 133496,  362880,
  1, 2, 125, 888, 6208, 30818, 126565, 439792, 1334961, 3628800,
  ...

H. Minc, Permanents, Encyc. Math. #6, 1978, p. 48

Alois P. Heinz, Rows n = 1..23, flattened
Henry Beker and Chris Mitchell, Permutations with restricted displacement, SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 338--363. MR0897734 (89f:05009)
N. S. Mendelsohn, Permutations with confined displacement, Canad. Math. Bull., 4 (1961), 29-38.
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
Wikipedia, Permanent (mathematics)

Diagonals (from the right): A000142, A000166, A000179, A000183, A004307, A189389, A184965.
Diagonals (from the left): A000211 or A048162, 4*A000382 or A004306 or A000803, A000804, A000805.
a(n,ceiling(n/2)) gives A306738.
Cf. A002467, A306714.

with(LinearAlgebra):
a:= (n, k)-> Permanent(Matrix(n,
             (i, j)-> `if`(0<=j-i and j-i

a[n_, k_] := Permanent[Table[If[0 <= j-i && j-i < k || j-i < k-n, 1, 0], {i, 1,n}, {j, 1, n}]]; Table[Table[a[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 10 2014, after Alois P. Heinz *)

a(n,k) = per(sum(P^j, j=0..k-1)), where P is n X n, P[ i, i+1 (mod n) ]=1, 0's otherwise.

a(n,n) - a(n,n-1) = A002467(n). - Alois P. Heinz, Mar 06 2019

Comments and more terms from Len Smiley
More terms from Vladeta Jovovic, Oct 02 2003
Edited by Alois P. Heinz, Dec 18 2010

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

Original entry on oeis.org

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

cp's OEIS Frontend

A102761 Same as A000179, except that a(0) = 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A335700 A variant of A000179 and A102761.

Views

Author

Keywords

References

Crossrefs

A000270 For n >= 2, a(n) = b(n+1)+b(n)+b(n-1), where the b(i) are the ménage numbers A000179; a(0)=a(1)=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A193356 If n is even then 0, otherwise n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A003436 Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000186 Number of 3 X n Latin rectangles in which the first row is in order.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

Extensions

A000271 Sums of ménage numbers.

Views

Author

Keywords

Comments