A229430 -id:A229430 - cp's OEIS frontend

A007060 Number of ways n married couples can sit in a row without any spouses next to each other.

1, 0, 8, 240, 13824, 1263360, 168422400, 30865121280, 7445355724800, 2287168006717440, 871804170613555200, 403779880746418176000, 223346806774106790297600, 145427383048755178635264000, 110105698060190464791596236800, 95914116314126658718742347776000, 95252504853751428295192341381120000

Offset: 0

David Roberts Keeney (David.Roberts.Keeney(AT)directory.Reed.edu)

Limit_{n->oo} a(n)/(2n)! = 1/e.
Also the number of (directed) Hamiltonian paths of the n-cocktail party graph. - Eric W. Weisstein, Dec 16 2013
Also the number of ways to label the cells of a 2 X n grid such that no vertically adjacent cells have adjacent labels. - Sela Fried, May 29 2023

			For n = 2, the a(2) = 8 solutions for the couples {1,2} and {3,4} are {1324, 1423, 2314, 2413, 3142, 3241, 4132, 4231}.

Andrew Woods, Table of n, a(n) for n = 0..100
G. Almkvist, Letter to N. J. A. Sloane, Apr. 1992.
Eric Weisstein's World of Mathematics, Cocktail Party Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Path.

Cf. A000166, A000806, A114938, A177840, A053983, A053984, A193624, A229430, A330266.

seq(add((-1)^i*binomial(n, i)*2^i*(2*n-i)!, i=0..n),n=0..20);

Table[Sum[(-1)^i Binomial[n,i] (2 n - i)! 2^i, {i, 0, n}], {n, 0, 20}]
Table[(2 n)! Hypergeometric1F1[-n, -2 n, -2], {n, 0, 20}]

a(n)=sum(k=0, n, binomial(n, k)*(-1)^(n-k)*(n+k)!*2^(n-k)) \\ Charles R Greathouse IV, May 11 2016

from sympy import binomial, subfactorial
def a(n): return sum([(-1)**(n - k)*binomial(n, k)*subfactorial(2*k) for k in range(n + 1)]) # Indranil Ghosh, Apr 28 2017

a(n) = (Pi*BesselI(n+1/2,1)*(-1)^n+BesselK(n+1/2,1))*exp(-1)*(2/Pi)^(1/2)*2^n*n!. - Mark van Hoeij, Nov 12 2009
a(n) = (-1)^n*2^n*n!*A000806(n), n>0. - Vladeta Jovovic, Nov 19 2009
a(n) = n!*hypergeom([-n, n+1],[],1/2)*(-2)^n. - Mark van Hoeij, Nov 13 2009
a(n) = 2^n * A114938(n). - Toby Gottfried, Nov 22 2010
a(n) = 2*n((2*n-1)*a(n-1) + (2*n-2)*a(n-2)), n > 1. - Aaron Meyerowitz, May 14 2014
From Peter Bala, Mar 06 2015: (Start)
a(n) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*A000166(2*k).
For n >= 1, Integral_{x = 0..1} (x^2 - 1)^n*exp(x) dx = a(n)*e - A177840(n). Hence lim_{n->oo} A177840(n)/a(n) = e. (End)
a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n + 1/2) / exp(2*n+1). - Vaclav Kotesovec, Mar 09 2016

More terms from Michel ten Voorde, Apr 11 2001

A189281 Number of permutations p of 1,2,...,n satisfying p(i+2) - p(i) <> 2 for all 1 <= i <= n-2.

Original entry on oeis.org

1, 1, 2, 5, 18, 75, 410, 2729, 20906, 181499, 1763490, 18943701, 222822578, 2847624899, 39282739034, 581701775369, 9202313110506, 154873904848803, 2762800622799362, 52071171437696453, 1033855049655584786, 21567640717569135515

Offset: 0

Vaclav Kotesovec, Apr 19 2011

nonn

a(n) is also the number of ways to place n nonattacking pieces rook + semi-leaper (2,2) on an n X n chessboard.
Comments from Vaclav Kotesovec, Mar 05 2022: (Start)
The original submission had keyword hard because of the following running times (in 2012):
a(33) 39 hours
a(34) 78 hours
a(35) 147 hours
The conjectured recurrence would imply the asymptotic expansion for a(n)/n! ~
(1 + 3/n + 2/n^2 + 1/n^3 + 0/n^4 + 3/n^5 + 26/n^6 + 101/n^7 + 124/n^8 - 1409/n^9 - 13266/n^10)/e.
This exactly matches the formula from 2011. In addition, all coefficients are integers. It is highly probable that recurrence is correct.
(End)
There are good reasons to believe the conjecture is correct. (It has the expected form.)  The problem is one of counting Hamiltonian cycles in the complement of some simple graph. There is a method for counting these efficiently (although I have not implemented in code). Similar to A242522 / A229430. - Andrew Howroyd, Mar 06 2022
See also Manuel Kauers's comments below. Since the four new terms took weeks of computation, the keyword "hard" continues to be justified. - N. J. A. Sloane, Mar 06 2022
a(40)-a(300) were computed using an independent solution (dynamic programming, O(N^4) per term), and the conjectured recurrence was further confirmed to be correct up to n=300. Consequently, the keyword "hard" is removed. - Rintaro Matsuo, Oct 18 2022

Rintaro Matsuo, Table of n, a(n) for n = 0..300 (terms 0..35 from Vaclav Kotesovec, terms 36..39 from Christoph Koutschan, computed using a parallelization of Kotesovec's Mathematica program)
Robert Dougherty-Bliss, Experimental Methods in Number Theory and Combinatorics, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 4.
Manuel Kauers, Comments on the Conjectured Recurrence for A189281.
Manuel Kauers and Christoph Koutschan, Guessing with Little Data, arXiv:2202.07966 [cs.SC], 2022.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 644.
Vaclav Kotesovec, Mathematica program for this sequence.
Rintaro Matsuo, O(n^4) code to calculate a(n)
George Spahn and Doron Zeilberger, Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s (For any given positive integers r and s), arXiv:2211.02550 [math.CO], 2022.

Cf. A000255, A002464, A055790, A110128.

Asymptotics: a(n)/n! ~ (1 + 3/n + 2/n^2)/e.
Conjectured recurrence of degree 11 and order 8: (262711*n + 1387742*n^2 - 824875*n^3 - 1855253*n^4 - 111530*n^5 + 680983*n^6 + 364242*n^7 + 84992*n^8 + 10332*n^9 + 640*n^10 + 16*n^11)*a(n) + (-1050844*n - 9705192*n^2 - 7414683*n^3 + 3536494*n^4 + 6459004*n^5 + 3326393*n^6 + 903534*n^7 + 144684*n^8 + 13756*n^9 + 720*n^10 + 16*n^11)*a(n+1) + (3492344 - 2212342*n - 8507169*n^2 - 11544227*n^3 - 12034116*n^4 - 8216995*n^5 - 3442049*n^6 - 890050*n^7 - 142300*n^8 - 13660*n^9 - 720*n^10 - 16*n^11)*a(n+2) + (19817984 + 45323852*n + 825228*n^2 - 57004661*n^3 - 57059306*n^4 - 28077270*n^5 - 8398637*n^6 - 1631510*n^7 - 207980*n^8 - 16828*n^9 - 784*n^10 - 16*n^11)*a(n+3) + (9586160 + 6680237*n - 13772613*n^2 - 27689586*n^3 - 22162455*n^4 - 9855085*n^5 - 2629562*n^6 - 427656*n^7 - 41332*n^8 - 2176*n^9 - 48*n^10)*a(n+4) + (22192864 + 44710768*n - 2924668*n^2 - 52385912*n^3 - 45161616*n^4 - 18784740*n^5 - 4549208*n^6 - 674256*n^7 - 60400*n^8 - 3008*n^9 - 64*n^10)*a(n+5) + (557152 - 2032472*n - 2937392*n^2 - 1594200*n^3 - 517688*n^4 - 122032*n^5 - 19856*n^6 - 1792*n^7 - 64*n^8)*a(n+6) + (3786960 + 7105324*n - 1191064*n^2 - 8059160*n^3 - 5938996*n^4 - 2073752*n^5 - 402736*n^6 - 44528*n^7 - 2624*n^8 - 64*n^9)*a(n+7) + (-598208 - 943004*n + 414196*n^2 + 1213772*n^3 + 728648*n^4 + 203584*n^5 + 29616*n^6 + 2176*n^7 + 64*n^8)*a(n+8) = 0. This recurrence correctly predicted the four new terms in the b-file. - Christoph Koutschan, Feb 19 2022
Comment from N. J. A. Sloane, Mar 12 2022: (Start)
The preceding conjectured recurrence is equivalent to the following, which has degree 3 and order 13, and was obtained by Doron Zeilberger and then reformatted by Manuel Kauers (it uses Mathematica syntax):
Conjecture: ((-1 + n)^2*n*a[n])/4 + (n*(-16 + 38*n + 11*n^2)*a[1 + n])/16 +
(3/2 + (139*n)/16 + (29*n^2)/8 + (3*n^3)/16)*a[2 + n] +
(-21/4 - (51*n)/4 - (79*n^2)/16 - (5*n^3)/8)*a[3 + n] +
(-15/2 - n/8 + (5*n^2)/4 + n^3/8)*a[4 + n] +
(603/4 + (307*n)/4 + (49*n^2)/4 + (11*n^3)/16)*a[5 + n] +
(-41 - (533*n)/16 - (49*n^2)/8 - (5*n^3)/16)*a[6 + n] +
(-911/2 - 161*n - (303*n^2)/16 - (3*n^3)/4)*a[7 + n] +
(-363 - (417*n)/4 - (37*n^2)/4 - n^3/4)*a[8 + n] +
(-993/4 - 53*n - (11*n^2)/4)*a[9 + n] + (-130 - (93*n)/4 - n^2)*a[10 + n] +
(-71/4 - 2*n)*a[11 + n] + (-10 - n)*a[12 + n] + a[13 + n] == 0.
(End)
From Mark van Hoeij, Jul 25 2012: (Start)
A compact way to write the order 13 recurrence is as follows:
Let b(n) = a(n+3) + a(n+2) + (n/2+2)*a(n+1) + (n-1)*a(n)/2
and c(n) = b(n+4) + (n/2+2)*b(n+2) - b(n+1)/2 + (1-n)*b(n)/2;
then c(n+6) - (n+11)*c(n+5) - (2*n+75/4)*c(n+4) + (3-n)*c(n+3)/4 - c(n+2)/2 - (7*n+22)*c(n+1)/4-n*c(n) = 0. (End)

cp's OEIS Frontend

A007060 Number of ways n married couples can sit in a row without any spouses next to each other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A189281 Number of permutations p of 1,2,...,n satisfying p(i+2) - p(i) <> 2 for all 1 <= i <= n-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A229429 Number of ways to label the cells of an m-by-n grid such that no (orthogonally) adjacent cells have adjacent labels; square array A(m,n) read by antidiagonals.

Views

Author

Keywords

Examples

Crossrefs