cp's OEIS Frontend

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.

%I A190823 #46 Dec 03 2023 01:44:36
%S A190823 1,0,0,1,10,99,1146,15422,237135,4106680,79154927,1681383864,
%T A190823 39034539488,983466451011,26728184505750,779476074425297,
%U A190823 24281301468714902,804688068731837874,28269541494090294129,1049450257149017422000,41050171013933837206545
%N 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.
%C A190823 From _Gus Wiseman_, Feb 27 2019: (Start)
%C A190823 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 A190823   {{1,4}, {2,6}, {3,7}, {5,8}}
%C A190823   {{1,4}, {2,7}, {3,6}, {5,8}}
%C A190823   {{1,5}, {2,6}, {3,7}, {4,8}}
%C A190823   {{1,5}, {2,6}, {3,8}, {4,7}}
%C A190823   {{1,5}, {2,7}, {3,6}, {4,8}}
%C A190823   {{1,5}, {2,8}, {3,6}, {4,7}}
%C A190823   {{1,6}, {2,5}, {3,7}, {4,8}}
%C A190823   {{1,6}, {2,5}, {3,8}, {4,7}}
%C A190823   {{1,7}, {2,5}, {3,6}, {4,8}}
%C A190823   {{1,8}, {2,5}, {3,6}, {4,7}}
%C A190823 (End)
%H A190823 Alois P. Heinz, <a href="/A190823/b190823.txt">Table of n, a(n) for n = 0..404</a>
%H A190823 Dmitry Efimov, <a href="https://arxiv.org/abs/2101.09722">Hafnian of two-parameter matrices</a>, arXiv:2101.09722 [math.CO], 2021.
%H A190823 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 A190823 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 A190823 a(n) ~ 2^(n+1/2) * n^n / exp(n+2), based on Sullivan's formula. - _Vaclav Kotesovec_, Mar 21 2017
%e A190823 All solutions for n=4 (read downwards):
%e A190823   1    1    1    1    1    1    1    1    1    1
%e A190823   2    2    2    2    2    2    2    2    2    2
%e A190823   3    3    3    3    3    3    3    3    3    3
%e A190823   4    4    4    4    1    4    4    1    4    4
%e A190823   1    1    2    1    4    2    1    4    2    2
%e A190823   3    3    1    2    2    3    2    3    1    3
%e A190823   2    4    4    4    3    4    3    2    3    1
%e A190823   4    2    3    3    4    1    4    4    4    4
%t A190823 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 A190823 dtui[{}]:={{}};dtui[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@dtui[Complement[set,s]]]/@Table[{i,j},{j,Select[set,#>i+2&]}];
%t A190823 Table[Length[dtui[Range[n]]],{n,0,12,2}] (* _Gus Wiseman_, Feb 27 2019 *)
%o A190823 (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 A190823 (SageMath)
%o A190823 @CachedFunction
%o A190823 def a(n): # a = A190823
%o A190823     if (n<6): return (1,0,0,1,10,99)[n]
%o A190823     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 A190823 [a(n) for n in range(41)] # _G. C. Greubel_, Dec 03 2023
%Y A190823 Distance of 1 instead of 2 gives |A000806|.
%Y A190823 Column k=3 of A293157.
%Y A190823 Cf. A000699, A001147 (2-uniform set partitions), A003436, A005493, A011968, A170941, A278990 (distance 2+ version), A306386 (cyclical version).
%K A190823 nonn,easy
%O A190823 0,5
%A A190823 _R. H. Hardin_, May 21 2011
%E A190823 a(16)-a(20) (using _Everett Sullivan_'s formula) from _Giovanni Resta_, Mar 20 2017
%E A190823 a(0)=1 prepended by _Alois P. Heinz_, Oct 17 2017