A190823 - OEIS

%I #46 Dec 03 2023 01:44:36

%S 1,0,0,1,10,99,1146,15422,237135,4106680,79154927,1681383864,

%T 39034539488,983466451011,26728184505750,779476074425297,

%U 24281301468714902,804688068731837874,28269541494090294129,1049450257149017422000,41050171013933837206545

%N 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.

%C From _Gus Wiseman_, Feb 27 2019: (Start)

%C 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:

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

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

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

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

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

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

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

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

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

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

%C (End)

%H Alois P. Heinz, <a href="/A190823/b190823.txt">Table of n, a(n) for n = 0..404</a>

%H Dmitry Efimov, <a href="https://arxiv.org/abs/2101.09722">Hafnian of two-parameter matrices</a>, arXiv:2101.09722 [math.CO], 2021.

%H Everett Sullivan, <a href="https://arxiv.org/abs/1611.02771">Linear chord diagrams with long chords</a>, arXiv preprint arXiv:1611.02771 [math.CO], 2016.

%F 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

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

%e All solutions for n=4 (read downwards):

%e   1    1    1    1    1    1    1    1    1    1

%e   2    2    2    2    2    2    2    2    2    2

%e   3    3    3    3    3    3    3    3    3    3

%e   4    4    4    4    1    4    4    1    4    4

%e   1    1    2    1    4    2    1    4    2    2

%e   3    3    1    2    2    3    2    3    1    3

%e   2    4    4    4    3    4    3    2    3    1

%e   4    2    3    3    4    1    4    4    4    4

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

%t dtui[{}]:={{}};dtui[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@dtui[Complement[set,s]]]/@Table[{i,j},{j,Select[set,#>i+2&]}];

%t Table[Length[dtui[Range[n]]],{n,0,12,2}] (* _Gus Wiseman_, Feb 27 2019 *)

%o (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

%o (SageMath)

%o @CachedFunction

%o def a(n): # a = A190823

%o     if (n<6): return (1,0,0,1,10,99)[n]

%o     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)

%o [a(n) for n in range(41)] # _G. C. Greubel_, Dec 03 2023

%Y Distance of 1 instead of 2 gives |A000806|.

%Y Column k=3 of A293157.

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

%K nonn,easy

%O 0,5

%A _R. H. Hardin_, May 21 2011

%E a(16)-a(20) (using _Everett Sullivan_'s formula) from _Giovanni Resta_, Mar 20 2017

%E a(0)=1 prepended by _Alois P. Heinz_, Oct 17 2017