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

A190826 Number of permutations of 3 copies of 1..n introduced in order 1..n with no element equal to another within a distance of 1.

Original entry on oeis.org

1, 0, 1, 29, 1721, 163386, 22831355, 4420321081, 1133879136649, 372419001449076, 152466248712342181, 76134462292157828285, 45552714996556390334921, 32173493282909179882613934, 26487410329744429030530295991, 25143126122564855343240882599761, 27260957330891104469298062949026065

Offset: 0

R. H. Hardin, May 21 2011

nonn

			Some of the a(3) = 29 solutions for n=3: 123232131, 123121323, 123123213, 123212313, 123213123, 121323132, 123132312, 123123123, 123231213, 121323123, 121321323, 121312323, 121323231, 123231321, 121313232, 123132321, ...

Seiichi Manyama, Table of n, a(n) for n = 0..223 (terms 0..101 from Andrew Woods)
H. Eriksson and A. Martin, Enumeration of Carlitz multipermutations, arXiv:1702.04177 [math.CO], 2017.
R. J. Mathar, A class of multinomial permutations avoiding object clusters, vixra:1511.0015 (2015), sequence M_{c,3}/3!.

Cf. A192990, A193624, A193638.

Row n=3 of A322013.

B:=Binomial;
f:= func< n,j | (&+[B(n,k)*B(2*k,j)*(-3)^(k-j): k in [Ceiling(j/2)..n]]) >;
A190826:= func< n | (-1/2)^n*(&+[Factorial(j)*B(n+j,j)*f(n,j): j in [0..2*n]]) >;
[A190826(n): n in [0..30]]; // G. C. Greubel, Sep 22 2023

a[n_]:= 1/(6^n*n!)*Sum[(n+j)! Sum[Binomial[n,k] Binomial[2k,j] (-3)^(n+k-j), {k, Ceiling[j/2], n}], {j,0,2n}]; Array[a, 16, 0] (* Jean-François Alcover, Jul 22 2017, after Tani Akinari's code for A193638 *)

b=binomial;
def f(j,n): return sum(b(n,k)*b(2*k,j)*(-3)^(k-j) for k in range((j//2),n+1))
def A190826(n): return (-1/2)^n*sum(factorial(j)*b(n+j,j)*f(j,n) for j in range(2*n+1))
[A190826(n) for n in range(31)] # G. C. Greubel, Sep 22 2023

a(n) = A193624(n)/(6^n * n!), for n >= 1.
a(n) = A193638(n)/n!, for n >= 1.
a(n) = A192990(binomial(n+2,3)) / (6^n * n!), for n >= 1.
2*a(n) -3*(3*n^2-3*n+4)*a(n-1) +2*(9*n^2-42*n+47)*a(n-2) +8*(3*n-7)*a(n-3) -8*a(n-4) = 0. - R. J. Mathar, May 23 2014
a(n) = (1/(6^n * n!)) * Sum_{j=0..2*n} Sum_{k=ceiling(j/2)..n} (n+j)! * binomial(2*k, j) * binomial(n, k) * (-3)^(n+k-j). - Jean-François Alcover, Jul 22 2017
a(n) ~ 3^(2*n + 1/2) * n^(2*n) / (2^n * exp(2*n + 2)). - Vaclav Kotesovec, Nov 24 2018

a(0)=1 prepended by Alois P. Heinz, Jul 22 2017

A193638 Number of permutations of the multiset {1,1,1,2,2,2,3,3,3,...,n,n,n} with no two consecutive terms equal.

Original entry on oeis.org

1, 0, 2, 174, 41304, 19606320, 16438575600, 22278418248240, 45718006789687680, 135143407245840698880, 553269523327347306412800, 3039044104423605600086688000, 21819823367694505460651694873600, 200345011881335747639978525387827200

Offset: 0

Andrew Woods, Aug 01 2011

nonn

			a(2) = 2 because there are two permutations of {1,1,1,2,2,2} avoiding equal consecutive terms: 121212 and 212121.

Andrew Woods, Table of n, a(n) for n = 0..101
H. Eriksson and A. Martin, Enumeration of Carlitz multipermutations, arXiv:1702.04177 [math.CO], 2017.

Cf. A114938 = similar, with two copies instead of three.
Cf. A193624 = arrangements of triples with no adjacent siblings.
Cf. A190826.

B:=Binomial;
f:= func< n,j | (&+[B(n,k)*B(2*k,j)*(-3)^(k-j): k in [Ceiling(j/2)..n]]) >;
A193638:= func< n | (-1/2)^n*(&+[Factorial(n+j)*f(n,j): j in [0..2*n]]) >;
[A193638(n): n in [0..30]]; // G. C. Greubel, Sep 22 2023

a:= proc(n) option remember; `if`(n<3, (n-1)*(3*n-2)/2,
    n*((3*n-1)*(3*n^2-5*n+4) *a(n-1) +2*(n-1)*(6*n^2-9*n-1) *a(n-2)
    -4*n*(n-1)*(n-2) *a(n-3))/(2*n-2))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Jun 05 2013

a[n_]:= (1/6^n)*Sum[(n+j)!*Binomial[n, k]*Binomial[2k, j]*(-3)^(n+k-j), {j,0,2n}, {k, Ceiling[j/2], n}]; Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Jul 22 2017, after Tani Akinari *)

a(n):= (1/6^n)*sum((n+j)!*sum(binomial(n,k)*binomial(2*k,j)* (-3)^(n+k-j), k,ceiling(j/2),n), j,0,2*n); /* Tani Akinari, Sep 23 2012 */

from sympy.core.cache import cacheit
@cacheit
def a(n): return (n-1)*(3*n-2)//2 if n<3 else n*((3*n-1)*(3*n**2 - 5*n + 4)*a(n-1) + 2*(n-1)*(6*n**2 -9*n-1)*a(n-2) - 4*n*(n-1)*(n-2)*a(n- 3))//(2*n-2)
print([a(n) for n in range(51)]) # Indranil Ghosh, Jul 22 2017, formula after Maple code

b=binomial;
def f(j,n): return sum(b(n,k)*b(2*k,j)*(-3)^(k-j) for k in range((j//2),n+1))
def A193638(n): return (-1/2)^n*sum(factorial(n+j)*f(j,n) for j in range(2*n+1))
[A193638(n) for n in range(31)] # G. C. Greubel, Sep 22 2023

a(n) = A190826(n) * n! for n >= 1.
a(n) = A193624(n)/6^n.
a(n) = Sum_{s+t+u=n} (-1)^t*multinomial(n;s,t,u)*(3*s+2*t+u)!/(3!)^s. - Alexis Martin, Nov 16 2017
a(n) = (1/6^n) * Sum_{j=0..2*n} Sum_{k=ceiling(j/2)..n} (n+j)! * binomial(2*k, j) * binomial(n, k) * (-3)^(n+k-j). - Tani Akinari, Sep 23 2012
a(n) = n*( (3*n-1)*(3*n^2-5*n+4)*a(n-1) +2*(n-1)*(6*n^2-9*n-1)*a(n-2) -4*n*(n-1)*(n-2)*a(n-3) )/(2*n-2). - Alois P. Heinz, Jun 05 2013

A192990 Pyramid P(n, t, d) read by planes and rows, for 0 <= t+d <= n: number of ways n triples can sit in a row so that exactly t triples are together and exactly d triples are separated into a couple and a loner.

Original entry on oeis.org

1, 0, 0, 6, 72, 144, 288, 0, 144, 72, 37584, 95904, 98496, 51840, 11664, 25920, 31104, 1296, 7776, 1296, 53529984, 127899648, 130761216, 69921792, 17915904, 11321856, 26002944, 23887872, 10202112, 1430784, 2985984, 2612736, 124416, 373248, 31104

Offset: 0

Andrew Woods, Aug 02 2011

The plane P(n,,) contains (n+1)*(n+2)/2 numbers.
The row P(n,t,) contains n+1-t numbers.
P(n,t,d) = a((n+1)*(n+2)*(n+3)/6 - (n-t+1)*(n-t+2)/2 + d)
The plane P(n,,) sums to (3n)!

			Pyramid starts:
1...0 0...72 144 288...37584 95904 98496 51840
....6..... 0 144.......11664 25920 31104
..........72........... 1296  7776
....................... 1296
There are P(3,1,2) = 31104 ways to arrange three sets of triples in a row so that one is together and two are split into a couple and a loner.

Andrew Woods, Table of n, a(n) for n = 0..1770, i.e. from P(0,,) to P(20,,)

P(n,0,0) = A193624(n).

A330266 Number of ways to shuffle a deck of 4n cards, with 4 cards in each of n ranks, so that adjacent cards have different ranks.

Original entry on oeis.org

1, 0, 1152, 15095808, 751480602624, 93995798935633920, 25111340235557122867200, 12742555660097789273088983040, 11259023892340311657074592904642560, 16205462460428776872054787528078739374080, 36051066700209244649349258741114804984663244800, 118807003903158552156678227915553602167323425243136000

Offset: 0

David Radcliffe, Dec 07 2019

nonn

			a(13) = 3668033946384704437729512814619767610579526911188666362431432294400 is the number of ways to shuffle a standard 52-card deck of playing cards so that no two cards of the same rank are adjacent.

James Enouen, What is the Perfect Shuffle?, arXiv:1911.07426 [math.CO], 2019.

Cf. A007060 (2n cards), A193624 (3n cards).

Table[Integrate[(x^4 - 12x^3 + 36x^2 - 24x)^n *Exp[-x],{x,0,Infinity}],{n,0,10}] (* Stefano Spezia, Dec 09 2019 *)

a(n) = Integral_{x=0..oo} (x^4 - 12x^3 + 36x^2 - 24x)^n*exp(-x) dx.
a(n) = 24^n * A321633(n).
Conjecture: Limit_{n->oo} a(n)/(4n)! = 1/e^3. The conjecture is based on the observation of the asymptotic behavior of A007060 and A193624; it seems that it can be generalized in the following way. Let b(n) be the number of ways to shuffle a deck of k*n cards, with k cards in each of n ranks, so that adjacent cards have different ranks. Then, lim_{n->oo} b(n)/(kn)! = 1/e^(k-1); maybe we could prove it with the help of rook polynomials theory or in some other way. - Sergey Kirgizov, Sep 29 2023

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

A190826 Number of permutations of 3 copies of 1..n introduced in order 1..n with no element equal to another within a distance of 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A193638 Number of permutations of the multiset {1,1,1,2,2,2,3,3,3,...,n,n,n} with no two consecutive terms equal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

Python

SageMath

Formula

A192990 Pyramid P(n, t, d) read by planes and rows, for 0 <= t+d <= n: number of ways n triples can sit in a row so that exactly t triples are together and exactly d triples are separated into a couple and a loner.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A330266 Number of ways to shuffle a deck of 4n cards, with 4 cards in each of n ranks, so that adjacent cards have different ranks.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula