A096789 -id:A096789 - cp's OEIS frontend

A089039 Number of circular permutations of 2n letters that are free of jealousy.

1, 2, 6, 60, 960, 24000, 861840, 42104160, 2686763520, 217039253760, 21651071904000, 2614084251609600, 375698806311628800, 63383303286471168000, 12403896267489382656000, 2786994829444848422400000, 712575504763406361133056000

Offset: 1

Akemi Nakamura, Michihiro Takahashi, Shogaku Meitantei (naka(AT)sansu.org), Dec 03 2003

The number of circular permutations of 2*n people consisting of n married couples, such that no one sits next to a person of the opposite sex who is not his or her spouse.

Limit_{n->oo} a(n)/(n-1)!^2 = Sum_{k>=1} 1/(k!*(k-1)!) = 1.590636854637329063382254424999666247954478159495536647132... (A096789).

			a(3)=6 because ABCcba, ACBbca, ABbacC, ACcabB, AabcCB, AacbBC are possible.

Eiji Kurihara, Small room of mathematics; see the answer for No. 380 of arithmetic challenges version 1.
Mikhail Kurkov and others, On a A089039 and pair of sequences with simple recursion, Math Overflow, Apr 20 2024
Masaru Yoshikawa, Arithmetic challenges. See problem No. 380.

a[1] = 1; a[n_] := n!*(n-2)!*HypergeometricPFQ[{1-n/2, 3/2-n/2}, {2, 2-n, 2-n}, 4]; Table[a[n], {n, 1, 17}] (* Jean-François Alcover, Oct 30 2013, after symbolic sum *)

a(n) = if (n==1, 1, sum (k=1, n\2, n!*(n-k-1)!^2/((k-1)!^2*(n-2*k)!*k))); \\ Michel Marcus, Sep 03 2013

a(1)=1, a(n) = Sum_{k=1..floor(n/2)} n!*(n-k-1)!^2/((k-1)!^2*(n-2*k)!*k) for n > 1.
a(n) = (n-1)!*(A001040(n-1) + A001053(n)) = 2*A276356(n), n > 1. - Conjectured by Mikhail Kurkov, Feb 10 2019 and proved by Max Alekseyev, Apr 23 2024 (see MO link)
a(n+4) = -(n+3)*(n+2)*(n*(n+1)*a(n) + 2*(n+1)^2*a(n+1) + n*(n+3)*a(n+2) - 2*a(n+3)) for all integer n>1. - conjectured by Michael Somos, Apr 21 2024. [The conjecture is equivalent to Kurkov's formula and thus is also proved. - Max Alekseyev, Apr 23 2024]

A141827 a(n) = (n^3*a(n-1) - 1)/(n - 1) for n >= 2, with a(0) = 1, a(1) = 4.

Original entry on oeis.org

1, 4, 31, 418, 8917, 278656, 12037939, 688168846, 50334635593, 4586743668412, 509638185379111, 67832842473959674, 10655922890454756061, 1950921882527424922168, 411794588127327229725307, 99271909637837814308779366, 27107849458438912493917352209

Offset: 0

Peter Bala, Jul 09 2008, Oct 06 2008

For related recurrences of the form a(n) = (n^k*a(n-1)-1)/(n-1) see A001339, A007808 (both k = 2) and A141828 (k = 4). a(n) is a difference divisibility sequence, that is, the difference a(n) - a(m) is divisible by n - m for all n and m (provided n is not equal to m). See A000522 for further properties of difference divisibility sequences.
From Peter Bala, Jul 02 2016: (Start)
For k = 1,2,3,... and x in Z, the recurrence equation a(n) = (n^k*a(n-1) - 1)/(n - 1) with starting value a(1) = x produces an integer sequence. This is because the sequence also satisfies the second-order recurrence a(n) = (1 + (n^k - 1)/(n - 1))*a(n-1) - (n - 1)^(k-1)*a(n-2) with integer starting values a(1) = x, a(2) = x*2^k - 1. Here we take k = 3 and x = 4.
The solution to the recurrence is a(n) = n*n!^(k-1)*( x - Sum_{i = 2..n} 1/(i*(i-1)*i!^(k-1)) ). Hence limit (n -> inf) a(n)/(n*n!^(k-1)) equals the constant x - Sum_{i = 2..inf} 1/(i*(i-1)*i!^(k-1)). Note that the sequence b(n) := n*n!^(k-1) satisfies the same second-order recurrence but with starting values b(1) = 1, b(2) = 2^k. From this observation one can get a generalized continued fraction expansion for a(n)/b(n) and hence, by going to the limit, for the constant x - Sum_{i = 2..n} 1/(i*(i-1)*i!^(k-1)). See, for example, A130820.  (End)

Cf. A001339, A007808, A070910, A082425, A096789, A130820, A141828.

a(n) := n -> n!^2*sum((n-k+1)*(k+1)/k!^2, k = 0..n): seq(a(n), n = 0..16);

a[0] = 1; a[1] = 4; a[n_] := a[n] = (n^3 a[n - 1] - 1)/(n - 1); Table[a@ n, {n, 0, 14}] (* or *)
Table[n!^2 Sum[(n - k + 1) (k + 1)/k!^2, {k, 0, n}], {n, 0, 14}] (* or *)
Table[n n!^2 (4 - Sum[ 1/(k!^2*k*(k - 1)), {k, 2, n}]), {n, 0, 14}] /. 0 -> 1 (* Michael De Vlieger, Jul 03 2016 *)

Sum_{n = 0..inf} a(n)*x^n/n!^2 = 1/(1 - x)^2*Sum_{n = 0..inf} (n + 1)*x^n/n!^2.
a(n) = n!^2*Sum_{k = 0..n} (n - k + 1)(k + 1)/k!^2.
a(n) = n*n!^2*(4 - Sum_{k = 2..n} 1/(k!^2*k*(k - 1))).
Congruence property: a(n) == (1 + n + n^2) (mod n^3).
The recurrence a(n) = (n^2 + n + 2)*a(n-1) - (n - 1)^2*a(n-2), n >= 2, shows that a(n) is always a positive integer. The sequence b(n) := n*n!^2 also satisfies the same recurrence with b(0) = 0, b(1) = 1. Hence we obtain the finite continued fraction expansion a(n)/(n*n!^2) = 4 - 1^2/(8 - 2^2/(14 - 3^2/(22 -...-(n - 1)^2/(n^2 + n + 2)))), for n > 1. a(n)*b(n+1) - b(n)*a(n+1) = n!^2.
Limit_{n -> infinity} a(n)/(n*n!^2) = Sum_{n = 0..inf} (n + 1)/n!^2 = BesselI(0,2) + BesselI(1,2) = 3.87022 21569 ..., using the values of the modified Bessel function, BesselI(0, 2) = 2.27958 53023 ... and BesselI(1, 2) = 1.59063 68546 ... (see A070910 and A096789; Cf. A130820). This yields the continued fraction expansion BesselI(0,2) + BesselI(1,2) = 4 - 1^2/(8 - 2^2/(14 - 3^2/(22 -...-(n - 1)^2/(n^2 + n + 2 - ... )))).
Limit_{n -> infinity} a(n)/(n*n!^2) = Sum_{n = 1..inf} (n + n^2)/n!^2 = Sum_{n = 1..inf} n^3/n!^2 = 1/2 * Sum_{n = 1..inf} n^4/n!^2.
Limit_{n -> infinity} a(n)/(n*n!^2) = Sum_{n = 0..inf} A001405 (n)/n!.
Limit_{n -> infinity} a(n)/(n*n!^2) = 1 + Sum_{n = 0..inf} 1/(Product_{k = 0..n} A008619(k)).

a(15)-a(16) from Jason Yuen, Jan 31 2025

A328378 Number of permutations of length n that possess the maximal sum of distances between contiguous elements.

Original entry on oeis.org

1, 1, 2, 4, 2, 8, 8, 48, 72, 576, 1152, 11520, 28800, 345600, 1036800, 14515200, 50803200, 812851200, 3251404800, 58525286400, 263363788800, 5267275776000, 26336378880000, 579400335360000, 3186701844480000, 76480844267520000, 458885065605120000, 11931011705733120000

Offset: 0

Tomás Roca Sánchez, Oct 14 2019

nonn

From Andrew Howroyd, Oct 16 2019: (Start)
No permutation with maximal sum of distances between contiguous elements can contain three contiguous elements a, b, c such that a < b < c or a > b > c. Otherwise removing b will not alter the sum and then appending b to the end of the permutation will increase it so that the original permutation could not have been maximal. In this sense all solution permutations are alternating.
For odd n consider an alternating permutation of the form p_1 p_2 ... p_n with p_1 > p2, p_2 < p_3, etc. The sum of distances is given by (p_1 + 2*p_3 + 2*p_5 + ... 2*p_{n-2} + p_n) - 2*(p_2 + p_4 + ... p_{n-1}). This is maximized by choosing the central odd p_i to be as highest possible and the even p_i to be least possible but other than that the order does not alter the sum. Similar arguments can be made for p_1 < p_2 and for the case when n is even.
The above considerations lead to a formula for this sequence with the maximum sum being given by A047838(n). (End)

			(1,3,2) is a permutation of length 3 with distance sum |1-3| + |3-2| = 2 + 1 = 3. For n = 3, the 4 permutations with maximum sum of distances are (1,3,2), (2,1,3), (2,3,1) and (3,1,2).

Alois P. Heinz, Table of n, a(n) for n = 0..508
Tomás Roca Sánchez, Github Python program along with explanations.

Cf. A047838 is the maximum distance for every length n, except for n = 0 and n = 1.

Cf. A070910, A096789.

A328378[n_]:=If[n<2,1,2(Floor[n/2]-1)!^2If[Divisible[n,2],1,n-1]];Array[A328378,30,0] (* Paolo Xausa, Aug 13 2023 *)

a(n)={if(n<2, n>=0, 2*(n\2-1)!^2*if(n%2, n-1, 1))} \\ Andrew Howroyd, Oct 16 2019

Python
```
# See Github link
```

a(2*n) = 2*(n-1)!^2 for n > 0; a(2*n+1) = 4*n!*(n-1)! for n > 0. - Andrew Howroyd, Oct 16 2019
D-finite with recurrence: - (12*n-20)*a(n) + 4*a(n-1) + (3*n-2)*(n-3)*(n-2)*a(n-2) = 0. - Georg Fischer, Nov 25 2022
Sum_{n>=0} 1/a(n) = BesselI(0, 2)/2 + BesselI(1, 2)/4 + 2 = A070910/2 + A096789/4 + 2. - Amiram Eldar, Oct 03 2023

Terms a(12) and beyond from Andrew Howroyd, Oct 16 2019

A386710 Decimal expansion of BesselI(2, 2 * sqrt(2)).

Original entry on oeis.org

1, 8, 5, 7, 5, 1, 7, 7, 8, 0, 2, 2, 9, 2, 1, 9, 1, 0, 8, 7, 7, 0, 5, 9, 8, 1, 8, 7, 6, 5, 3, 1, 3, 7, 1, 5, 0, 1, 3, 9, 0, 4, 9, 0, 9, 1, 1, 3, 5, 7, 0, 5, 0, 9, 1, 7, 2, 0, 6, 3, 4, 6, 3, 6, 1, 1, 2, 0, 8, 2, 2, 2, 1, 6, 4, 7, 0, 8, 7, 1, 8, 0, 7, 3, 4, 5, 8, 2, 7, 2, 2, 8, 3, 0, 6, 6, 5, 7, 7, 3, 9, 3, 8, 5, 8

Offset: 1

Kelvin Voskuijl, Jul 30 2025

			1.8575177802292191087705981876531371501390490911357...

Kelvin Voskuijl, Table of n, a(n) for n = 1..20000

Cf. A386927 (continued fraction).
Cf. A096789 (for factorial squared).
Cf. A006472 (triangular polygorials).

RealDigits[BesselI[2, 2 * Sqrt[2]],10,100][[1]] (* Stefano Spezia, Aug 02 2025 *)

besseli(2, 2*sqrt(2)) \\ Amiram Eldar, Aug 02 2025

Equals Sum_{k >= 1} 2^k/((k-1)!*(k+1)!).

A152873 Number of permutations of {1,2,...,n} (n>=2) having a single run of even entries. For example, the permutation 513284679 has a single run of even entries: 2846.

Original entry on oeis.org

2, 6, 12, 48, 144, 720, 2880, 17280, 86400, 604800, 3628800, 29030400, 203212800, 1828915200, 14631321600, 146313216000, 1316818944000, 14485008384000, 144850083840000, 1738201006080000, 19120211066880000, 248562743869440000, 2982752926433280000, 41758540970065920000

Offset: 2

Emeric Deutsch, Dec 14 2008

nonn

			a(4) = 12 because we have 2413, 2431, 4213, 4231, 1243, 1423 and their reverses.

Cf. A152667.

Cf. A096789, A229020.

ae := proc (n) options operator, arrow: factorial(n)^2*(n+1) end proc: ao := proc (n) options operator, arrow: factorial(n)*factorial(n+2) end proc: a := proc (n) if `mod`(n, 2) = 0 then ae((1/2)*n) else ao((1/2)*n-1/2) end if end proc; seq(a(n), n = 2 .. 23);
# second Maple program:
a:= n-> (h-> h!*(h+1+(n mod 2))!)(iquo(n, 2)):
seq(a(n), n=2..25);  # Alois P. Heinz, Sep 24 2024

a[n_] := If[OddQ[n], ((n - 1)/2)!*((n + 3)/2)!, (n/2 + 1) ((n/2)!)^2]; Array[a, 25, 2] (* Amiram Eldar, Jan 22 2023 *)

a(n) = A152667(n,1).
a(2n) = (n+1)(n!)^2;
a(2n+1) = n!(n+2)!
E.g.f.: 24*sqrt(4-x^2)*arcsin(x/2)/[(2-x)^3*(2+x)^2] - x(6-8x-3x^2+2x^3)/ [(2+x)(2-x)^2].
G.f.: G(0)/x^2 -1/x^2 -2/x, where G(k) = 1 + x*(k+2)/(1 - x*(k+1)/ (x*(k+1) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 07 2013
D-finite with recurrence 4*a(n) -2*a(n-1) -(n+2)*(n-1)*a(n-2)=0. - R. J. Mathar, Jul 24 2022
Sum_{n>=2} 1/a(n) = BesselI(1, 2) + BesselI(2, 2) - 3/2 = A096789 + A229020 - 3/2. - Amiram Eldar, Jan 22 2023

cp's OEIS Frontend

A089039 Number of circular permutations of 2n letters that are free of jealousy.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Formula

A141827 a(n) = (n^3*a(n-1) - 1)/(n - 1) for n >= 2, with a(0) = 1, a(1) = 4.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A328378 Number of permutations of length n that possess the maximal sum of distances between contiguous elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A386710 Decimal expansion of BesselI(2, 2 * sqrt(2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A152873 Number of permutations of {1,2,...,n} (n>=2) having a single run of even entries. For example, the permutation 513284679 has a single run of even entries: 2846.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A318198 Simple continued fraction expansion of BesselI(1,2).

Views

Author

Keywords

Comments

Crossrefs