A114938 -id:A114938 - cp's OEIS frontend

A137737 Number of circular permutations of the multiset {1,1,2,2,...,n,n} (up to rotations) with even distances between equal elements.

0, 1, 0, 30, 0, 13560, 0, 27785520, 0, 162030637440, 0, 2156625389318400, 0, 56857271240920550400, 0, 2686506065987036477184000, 0, 211180868835057744408834048000, 0, 26072812428113877344085395644416000, 0

Offset: 1

Max Alekseyev, Feb 09 2008

nonn

Cf. A114938, A137729, A137730, A137749

For odd n, a(n) = 0. For even n, a(n) = (n!^3 / (n/2)!^2 / 2^n + n!) / (2n).

a(2n) = A137749(n)

A137749 Number of circular permutations of the multiset {1,1,2,2,...,2n,2n} (up to rotations) with even distances between equal elements.

Original entry on oeis.org

1, 30, 13560, 27785520, 162030637440, 2156625389318400, 56857271240920550400, 2686506065987036477184000, 211180868835057744408834048000, 26072812428113877344085395644416000, 4829206317935252350431489703482654720000

Offset: 1

Max Alekseyev, Feb 09 2008

nonn

Cf. A114938, A137729, A137730, A137737

a(n) = ((2n)!^3 / n!^2 / 2^(2n) + (2n)!) / (4n).

a(n) = A137737(2n)

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

A114939 Number of essentially different seating arrangements for n couples around a circular table with 2n seats avoiding spouses being neighbors and avoiding clusters of 3 persons with equal gender.

Original entry on oeis.org

0, 1, 7, 216, 10956, 803400, 83003040, 11579823360, 2080493573760, 469031859192960, 129727461014726400, 43176116371928601600, 17025803126147196057600, 7850538273249476117913600

Offset: 1

Hugo Pfoertner, Jan 08 2006

Arrangements that differ only by rotation or reflection are excluded by the following conditions: Seat number 1 is assigned to person (a). Person (a)'s spouse (A) can only take seats with numbers <=(n+1). If (A) gets seat n+1 (i.e. sits exactly opposite to her/his spouse) then person (B) can only take seats with numbers <= n.

			a(2)=1 because the only valid arrangement is aBAb.
a(3)=7 because the only valid arrangements under the given conditions are: abAcBC, aBAcbC, aBcAbC, aBcACb, acAbCB, acBAbC, aCAbcB.

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.

Cf. A114938, A137729, A137730, A137737, A137749, A258338.

a[1] = 0;
a[n_] := (n-1)!/4 Sum[(-1)^j(n-j)! SeriesCoefficient[ SeriesCoefficient[Tr[ MatrixPower[{{0, 1, 0, y^2, 0, 0}, {z y^2, 0, 1, 0, y^2, 0}, {z y^2, 0, 0, 0, y^2, 0}, {0, 1, 0, 0, 0, z}, {0, 1, 0, y^2, 0, z}, {0, 0, 1, 0, y^2, 0}}, 2n]], {y, 0, 2n}] , {z, 0, j}], {j, 0, n}];
Array[a, 14] (* Jean-François Alcover, Dec 03 2018, from PARI *)

{ a(n) = if(n<=1, 0, (-1)^n*(n-1)!*2^(n-1) + n! * polcoeff( polcoeff( [0, 2*y*z^3 + z^2, -3*y*z^5 - 4*z^4 + ((-2*y^2 - 1)/y)*z^3, 6*y*z^7 + (4*y^2 + 11)*z^6 + ((8*y^2 + 4)/y)*z^5 + 3*z^4] * sum(j=0,n-1, j! * [0, 0, 0, -z^6 + z^4; 1, 0, 0, ((y^2 + 1)/y)*z^5 - 2*z^4 + ((-y^2 - 1)/y)*z^3; 0, 1, 0, ((2*y^2 + 2)/y)*z^3 + z^2; 0, 0, 1, -2*z^2]^(n+j) ) * [1,0,0,0]~, 2*n,z), 0,y) / 2 ); }

See Alekseyev (2016) and the PARI code for the formula.

a(n) = A258338(n) / (4*n).

a(4)-a(7) corrected, formula and further term provided by Max Alekseyev, Feb 15 2008

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

Original entry on oeis.org

1, 0, 2, 1092, 2265024, 11804626080, 131402141197200, 2778291737177034960, 102284730928300590754560, 6134232798447803932455457920, 568598490353320413296928514444800, 78076149156802562231395694989534464000, 15336188146163145199585928509793662920345600

Offset: 0

Seiichi Manyama, Nov 15 2018

nonn

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

Seiichi Manyama, Table of n, a(n) for n = 0..129
Mathematics.StackExchange, Find the number of k 1's, k 2's, ... , k n's - total kn cards, Apr 08 2012.

Row 4 of A322093.

Cf. A000142, A114938, A190830, A193638.

a[n_] := Integrate[(-x + 3/2 * x^2 - 1/2 * x^3 + 1/24 * x^4)^n  * Exp[-x],  {x, 0, Infinity}]; Array[a, 10, 0] (* Stefano Spezia, Nov 27 2018 *)

a(n) = n! * A190830(n).

a(n) = Integral_{0..oo} (-x + 3/2 * x^2 - 1/2 * x^3 + 1/24 * x^4)^n * exp(-x) dx.

A258338 Ternary ménage problem: number of seating arrangements for n opposite-sex couples around a circular table such that no spouses and no triples of the same sex seat next to each other. Seats are labeled.

Original entry on oeis.org

0, 8, 84, 3456, 219120, 19281600, 2324085120, 370554347520, 74897768655360, 18761274367718400, 5708008284647961600, 2072453585852572876800, 885341762559654194995200, 439630143301970662603161600, 251099117378080818090596352000, 163464570058143774978660630528000

Offset: 1

Max Alekseyev, May 27 2015

nonn

Conjecture: (a(n)/n!^2)^(1/n) ~ (3+sqrt(5))/2. - Vaclav Kotesovec, May 29 2015

Max Alekseyev, Table of n, a(n) for n = 1..100
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.

Cf. A114939 (counts up to rotations and reflections)

Cf. A059375, A094047, A000179, A114938, A137729, A137730, A137737, A137749.

a[1] = 0;
a[n_] := n! Sum[(-1)^j (n-j)! SeriesCoefficient[ SeriesCoefficient[ Tr[ MatrixPower[{{0, 1, 0, y^2, 0, 0}, {z y^2, 0, 1, 0, y^2, 0}, {z y^2, 0, 0, 0, y^2, 0}, {0, 1, 0, 0, 0, z}, {0, 1, 0, y^2, 0, z}, {0, 0, 1, 0, y^2, 0}}, 2n]], {y, 0, 2n}], {z, 0, j}], {j, 0, n}];
Array[a, 16] (* Jean-François Alcover, Dec 03 2018, from 1st PARI program *)

{ a(n) = if(n<2, 0, n! * sum(j=0,n, (-1)^j * (n-j)! *polcoeff( polcoeff( trace([0, 1, 0, y^2, 0, 0; z*y^2, 0, 1, 0, y^2, 0; z*y^2, 0, 0, 0, y^2, 0; 0, 1, 0, 0, 0, z; 0, 1, 0, y^2, 0, z; 0, 0, 1, 0, y^2, 0]^(2*n)), 2*n,y) ,j,z)) ); }

{ a(n) = if(n<2, 0, n! *  polcoeff( serlaplace( polcoeff( trace([-y, z*y, z, 0, z*y, -y; -y, (z - 1)*y, 0, (z - 1)*y^2, z*y, -y; 0, (z - 1)*y, 0, (z - 1)*y^2, 0, -y; -y, 0, z - 1, 0, (z - 1)*y, 0; -y, z*y, z - 1, 0, (z - 1)*y, -y; -y, z*y, 0, z*y^2, z*y, -y]^n), n, y) )/(1-z) + O(z^(n+1)), n, z) ) }

a(n) = A114939(n) * 4 * n.

A275801 Number of alternating permutations of the multiset {1,1,2,2,...,n,n}.

Original entry on oeis.org

1, 0, 1, 4, 53, 936, 25325, 933980, 45504649, 2824517520, 217690037497, 20394614883316, 2282650939846781, 300814135522967736, 46103574973075123877, 8130996533576437261772, 1635028654501420083152785, 371853339350614571322913824, 94969025880924845123887493233

Offset: 0

Max Alekseyev, Aug 09 2016

nonn

Number of permutations (p(1),...,p(2n)) of {1,1,2,2,...,n,n} satisfying p(1) < p(2) > p(3) < ... < p(2n).

a(n) <= A005799(n) <= A275829(n).

Max Alekseyev, Table of n, a(n) for n = 0..70
Wikipedia, Alternating permutation.
hkju et al., Number of updown sequences of 1,1,2,2,...,n,n, Mathoverflow, 2016.

Column k=2 of A275784.

Cf. A000111, A001250, A000459, A004075, A005799, A114938, A137729, A137730, A137737, A137749, A275829.

A335432 Number of anti-run permutations of the prime indices of Mersenne numbers A000225(n) = 2^n - 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 6, 2, 6, 2, 36, 1, 6, 6, 24, 1, 24, 1, 240, 6, 24, 2, 1800, 6, 6, 6, 720, 6, 1800, 1, 120, 24, 6, 24, 282240, 2, 6, 24, 15120, 2, 5760, 6, 5040, 720, 24, 6, 1451520, 2, 5040, 120, 5040, 6, 1800, 720, 40320, 24, 720, 2, 1117670400, 1, 6, 1800, 5040, 6

Offset: 1

Gus Wiseman, Jul 02 2020

nonn

An anti-run is a sequence with no adjacent equal parts.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(1) = 1 through a(10) = 6 permutations:
  ()  (2)  (4)  (2,3)  (11)  (2,4,2)  (31)  (2,3,7)  (21,4)  (11,2,5)
                (3,2)                       (2,7,3)  (4,21)  (11,5,2)
                                            (3,2,7)          (2,11,5)
                                            (3,7,2)          (2,5,11)
                                            (7,2,3)          (5,11,2)
                                            (7,3,2)          (5,2,11)

Andrew Howroyd, Table of n, a(n) for n = 1..200

The version for factorial numbers is A335407.
Anti-run compositions are A003242.
Anti-run patterns are A005649.
Permutations of prime indices are A008480.
Anti-runs are ranked by A333489.
Separable partitions are ranked by A335433.
Inseparable partitions are ranked by A335448.
Anti-run permutations of prime indices are A335452.
Strict permutations of prime indices are A335489.
Cf. A056239, A106351, A112798, A114938, A278990, A292884, A325535, A335125.
Mersenne numbers: A000225, A046051, A046800, A046801, A049093, A059305, A159611, A325610, A325611, A325612, A325625.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Permutations[primeMS[2^n-1]],!MatchQ[#,{_,x_,x_,_}]&]],{n,0,30}]

\\ See A335452 for count.
a(n) = {count(factor(2^n-1)[,2])} \\ Andrew Howroyd, Feb 03 2021

a(n) = A335452(A000225(n)).

Terms a(51) and beyond from Andrew Howroyd, Feb 03 2021

A275829 Number of weakly alternating permutations of the multiset {1,1,2,2,...,n,n}.

Original entry on oeis.org

1, 1, 2, 12, 140, 2564, 68728, 2539632, 123686800, 7677924688, 591741636128, 55438330474944, 6204888219697856, 817697605612952384, 125322509904814743424, 22102340129003429880576, 4444468680409243484516608, 1010802175212828388101900544, 258152577318424951261637001728

Offset: 0

Max Alekseyev, Aug 11 2016

nonn

Number of permutations (p(1),...,p(2n)) of {1,1,2,2,...,n,n} satisfying p(1) <= p(2) >= p(3) <= p(4) >= p(5) <= ... <= p(2n).

a(n) >= A005799(n) >= A275801(n).

Max Alekseyev, Table of n, a(n) for n = 0..70

Cf. A000111, A001250, A000459, A004075, A005799, A114938, A137729, A137730, A137737, A137749, A275801.

A321634 Number of arrangements of n 1's, n 2's, ..., n n's avoiding equal consecutive terms.

Original entry on oeis.org

1, 1, 2, 174, 2265024, 7946203275000, 12229789732207993835280, 12202002913678756821228939869239920, 10937192762438008527903830198163831816546577931520, 11655577382287102750765311537460065620507094071664576111302628243840

Offset: 0

Seiichi Manyama, Nov 15 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..26
Mathematics.StackExchange, Find the number of k 1's, k 2's, ... , k n's - total kn cards, Apr 08 2012.

Cf. A000142, A110706, A114938, A193638, A321633, A321666.

{a(n) = sum(i=n, n^2, i!*polcoef(sum(j=1, n, (-1)^(n-j)*binomial(n-1, j-1)*x^j/j!)^n, i))} \\ Seiichi Manyama, May 27 2019

a(n) ~ n^(n^2 - n/2 + 1) / ((2*Pi)^((n-1)/2) * exp(n - 5/12)). - Vaclav Kotesovec, Nov 24 2018

cp's OEIS Frontend

A137737 Number of circular permutations of the multiset {1,1,2,2,...,n,n} (up to rotations) with even distances between equal elements.

Views

Author

Keywords

Crossrefs

Formula

A137749 Number of circular permutations of the multiset {1,1,2,2,...,2n,2n} (up to rotations) with even distances between equal elements.

Views

Author

Keywords

Crossrefs

Formula

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

A114939 Number of essentially different seating arrangements for n couples around a circular table with 2n seats avoiding spouses being neighbors and avoiding clusters of 3 persons with equal gender.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A258338 Ternary ménage problem: number of seating arrangements for n opposite-sex couples around a circular table such that no spouses and no triples of the same sex seat next to each other. Seats are labeled.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A275801 Number of alternating permutations of the multiset {1,1,2,2,...,n,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A335432 Number of anti-run permutations of the prime indices of Mersenne numbers A000225(n) = 2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica