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

1, 0, 0, 1, 10, 99, 1146, 15422, 237135, 4106680, 79154927, 1681383864, 39034539488, 983466451011, 26728184505750, 779476074425297, 24281301468714902, 804688068731837874, 28269541494090294129, 1049450257149017422000, 41050171013933837206545

Offset

0,5

Comments

From Gus Wiseman, Feb 27 2019: (Start)

Also the number of 2-uniform set partitions of {1..2n} such that no block has its two vertices differing by less than 3. For example, the a(4) = 10 set partitions are:

{{1,4}, {2,6}, {3,7}, {5,8}}

{{1,4}, {2,7}, {3,6}, {5,8}}

{{1,5}, {2,6}, {3,7}, {4,8}}

{{1,5}, {2,6}, {3,8}, {4,7}}

{{1,5}, {2,7}, {3,6}, {4,8}}

{{1,5}, {2,8}, {3,6}, {4,7}}

{{1,6}, {2,5}, {3,7}, {4,8}}

{{1,6}, {2,5}, {3,8}, {4,7}}

{{1,7}, {2,5}, {3,6}, {4,8}}

{{1,8}, {2,5}, {3,6}, {4,7}}

(End)

Links

Alois P. Heinz, Table of n, a(n) for n = 0..404

Dmitry Efimov, Hafnian of two-parameter matrices, arXiv:2101.09722 [math.CO], 2021.

Everett Sullivan, Linear chord diagrams with long chords, arXiv preprint arXiv:1611.02771 [math.CO], 2016.

Formula

a(n) = 2*(n+1)*a(n-1) - 2*(3*n-5)*a(n-2) + 2*(3*n-8)*a(n-3) - 2*(n-4)*a(n-4) - a(n-5) (proved). - Everett Sullivan, Mar 16 2017

a(n) ~ 2^(n+1/2) * n^n / exp(n+2), based on Sullivan's formula. - Vaclav Kotesovec, Mar 21 2017

Example

All solutions for n=4 (read downwards):
  1    1    1    1    1    1    1    1    1    1
  2    2    2    2    2    2    2    2    2    2
  3    3    3    3    3    3    3    3    3    3
  4    4    4    4    1    4    4    1    4    4
  1    1    2    1    4    2    1    4    2    2
  3    3    1    2    2    3    2    3    1    3
  2    4    4    4    3    4    3    2    3    1
  4    2    3    3    4    1    4    4    4    4

Mathematica

a[0]=1; a[1]=0; a[2]=0; a[3]=1; a[4]=10; a[5]=99; a[n_] := a[n] = (2*n+2) a[n-1] - (6*n-10) a[n-2] + (6*n-16) a[n-3] - (2*n-8) a[n-4] - a[n-5]; Array[a, 20, 0] (* based on Sullivan's formula, Giovanni Resta, Mar 20 2017 *)
dtui[{}]:={{}}; dtui[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@dtui[Complement[set, s]]]/@Table[{i, j}, {j, Select[set, #>i+2&]}];
Table[Length[dtui[Range[n]]], {n, 0, 12, 2}] (* Gus Wiseman, Feb 27 2019 *)

Prog

(Magma) I:=[1, 0, 0, 1, 10, 99]; [n le 5 select I[n] else 2*n*Self(n-1) -2*(3*n-8)*Self(n-2) +2*(3*n-11)*Self(n-3) -2*(n-5)*Self(n-4) -Self(n-5): n in [1..40]]; // G. C. Greubel, Dec 03 2023
(SageMath)
@CachedFunction
def a(n): # a = A190823
    if (n<6): return (1, 0, 0, 1, 10, 99)[n]
    else: return 2*(n+1)*a(n-1) - 2*(3*n-5)*a(n-2) + 2*(3*n-8)*a(n-3) - 2*(n-4)*a(n-4) - a(n-5)
[a(n) for n in range(41)] # G. C. Greubel, Dec 03 2023

Crossrefs

Distance of 1 instead of 2 gives |A000806|.

Column k=3 of A293157.

Cf. A000699, A001147 (2-uniform set partitions), A003436, A005493, A011968, A170941, A278990 (distance 2+ version), A306386 (cyclical version).

Sequence in context: A213454 A000456 A138365 * A187019 A292429 A145644

Adjacent sequences: A190820 A190821 A190822 * A190824 A190825 A190826

Keyword

nonn,easy

Author

R. H. Hardin, May 21 2011

Extensions

a(16)-a(20) (using Everett Sullivan's formula) from Giovanni Resta, Mar 20 2017

a(0)=1 prepended by Alois P. Heinz, Oct 17 2017

Status

approved