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

Author

R. H. Hardin, May 21 2011

Keywords

• nonn
• easy

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)

Examples

			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
		

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.

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).

Programs

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

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 *)

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

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

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