login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
1, 0, 0, 1, 10, 99, 1146, 15422, 237135, 4106680, 79154927, 1681383864, 39034539488, 983466451011, 26728184505750, 779476074425297, 24281301468714902, 804688068731837874, 28269541494090294129, 1049450257149017422000, 41050171013933837206545 (list; graph; refs; listen; history; text; internal format)
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

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

FORMULA

a(n) = (2n+2)a(n-1) - (6n-10)a(n-2) + (6n-16)a(n-3) - (2n-8)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[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] (* 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 *)

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 17:59 EST 2020. Contains 331999 sequences. (Running on oeis4.)