A271212 -id:A271212 - cp's OEIS frontend

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i

1, 0, 2, 2, 8, 14, 54, 128, 498, 1426, 5736, 18814, 78886, 287296, 1258018, 4986402, 22789000, 96966318, 461790998, 2088374592, 10343408786, 49343711666, 253644381032, 1268995609502, 6756470362374, 35285321738624, 194220286045506, 1054759508543554

Offset: 0

Alois P. Heinz, May 19 2023

nonn

Number of permutations p of [n] such that each element in p has at least one neighbor whose value is smaller or larger by one.

Number of permutations of [n] having n occurrences of the 1-box pattern.

			a(0) = 1: (), the empty permutation.
a(1) = 0.
a(2) = 2: 12, 21.
a(3) = 2: 123, 321.
a(4) = 8: 1234, 1243, 2134, 2143, 3412, 3421, 4312, 4321.
a(5) = 14: 12345, 12354, 12543, 21345, 21543, 32145, 32154, 34512, 34521, 45123, 45321, 54123, 54312, 54321.
a(6) = 54: 123456, 123465, 123654, 124356, 124365, 125634, 125643, 126534, 126543, 213456, 213465, 214356, 214365, 215634, 215643, 216534, 216543, 321456, 321654, 341256, 341265, 342156, 342165, 345612, 345621, 346512, 346521, 431256, 431265, 432156, 432165, 435612, 435621, 436512, 436521, 456123, 456321, 561234, 561243, 562134, 562143, 563412, 563421, 564312, 564321, 651234, 651243, 652134, 652143, 653412, 653421, 654123, 654312, 654321.

Alois P. Heinz, Table of n, a(n) for n = 0..803
FindStat, St000064: The number of one-box pattern of a permutation.
S. Kitaev, J. Remmel, The 1-box pattern on pattern avoiding permutations, arXiv:1305.6970 [math.CO], 2013.

Main diagonal of A346462.

Cf. A002464, A003274, A011655, A095816, A127697, A179957, A229730, A271212, A211694, A333833, A363236.

a:= proc(n) option remember; `if`(n<4, [1, 0, 2$2][n+1],
      3/2*a(n-1)+(n-3/2)*a(n-2)-(n-5/2)*a(n-3)+(n-4)*a(n-4))
    end:
seq(a(n), n=0..30);

a(n) = A346462(n,n).
a(n)/2 mod 2 = A011655(n-1) for n>=1.
a(n) ~ sqrt(Pi) * n^((n+1)/2) / (2 * exp(n/2 - sqrt(n)/2 + 7/16)) * (1 - 119/(192*sqrt(n))). - Vaclav Kotesovec, May 26 2023

A271214 Number of reduced rearrangement patterns with n blocks.

Original entry on oeis.org

1, 1, 2, 10, 71, 653, 7638, 104958, 1664083, 29740057, 591645738, 12959409010, 309898317151, 8032551265957, 224316415082750, 6714021923017318, 214415538303362411, 7277133405318569009, 261560966377901961810, 9925178291099012783322, 396498148141095399675511

Offset: 0

Jonathan Burns, Apr 13 2016

a(n) is the number of reduced rearrangement patterns, i.e., the number of reduced rearrangement map equivalence classes formed from the two rotation involutions.

			For n=0 the a(0)=1 solution is { ∅ }
For n=1 the a(1)=1 solution is { +1 }
For n=2 the a(2)=2 solutions are { +2+1, +1-2 }
For n=3 the a(3)=10 solutions are { +3-2+1, +1+3-2, +2-3+1, +1+3+2, +2+1-3, +3+1-2, +1-3+2, +3+2+1, +3+2-1, +1-2+3 }

J. Burns, Counting a Class of Signed Permutations and Chord Diagrams related to DNA Rearrangement, Preprint.

G. C. Greubel, Table of n, a(n) for n = 0..400
J. Burns, Table of Rearrangement Maps and Patterns for n = 1, 2, and 3.

Cf. A271212, A271217.

Table[(Round[2^n*Exp[-1/2]*(n + 1/2)*(n - 1)!] + Round[2^n*Exp[ -1/4]*(1 - (1 + (-1)^n)/(4 n))*Floor[n/2]!])/4, {n,  1, 20}]

a(n) = ( round( 2^n e^(-1/2) (n+1/2) (n-1)! ) + round( 2^n e^(-1/4) (1-(1+(-1)^n)/4n)) floor(n/2)! ) / 4.
a(n) ~ sqrt( Pi*n / 8*e) * (2n / e)^n.
a(n) = (A271212(n) + A271217(n)) / 4.

A271217 Number of symmetric reduced rearrangement maps.

Original entry on oeis.org

1, 2, 2, 6, 22, 50, 274, 598, 4486, 9570, 90914, 191398, 2201078, 4593554, 62012978, 128619510, 1993602406, 4115824322, 72026925634, 148169675590, 2889308674006

Offset: 0

Jonathan Burns, Apr 13 2016

a(n) is the number of reduced rearrangement maps on n blocks. A rearrangement map is a signed permutation, e.g., +2 -1 -3. If the permutation contains (i)(i+1) or -(i+1)-(i) for any i, then it is not reduced. The map a is symmetric if a=a^(AI) and a^A = a^I where A and I are the rotation involutions.

			For n=0 the a(0)=1 solution is { ∅ }
For n=1 the a(1)=2 solutions are { +1, -1 }
For n=2 the a(2)=2 solutions are { +2+1, -1-2 }
For n=3 the a(3)=6 solutions are { +3-2+1, -1+2-3, +3+2+1, -1-2-3, +1-2+3, -3+2-1 }

J. Burns, Counting a Class of Signed Permutations and Chord Diagrams related to DNA Rearrangement, Preprint.

J. Burns, Table of Rearrangement Maps and Patterns for n = 1, 2, and 3.

A271217 / A271216 ~ e^(-1/4).

Cf. A271212, A271214

Table[Round[2^n*Exp[-1/4]*(1-(1+(-1)^n)/(4 n))*Floor[n/2]!],{n,1,20}]

a(n) = round( 2^n * e^(-1/4) * ( 1 - (1 + (-1)^n)/(4n) ) * floor(n/2)! )
a(2k+1) = 2*a(2k) + a(2k-1) and a(2k) = (2k-1)*a(2k-1)+(2k-2)*a(2k-3)
a(n) ~ e^(-1/4) * 2^n * floor(n/2)!.
Conjecture: (-2*n+9)*a(n) -4*a(n-1) +(2*n-3)*(2*n-7)*a(n-2) -4*a(n-3) +2*(2*n-5)*(n-4)*a(n-4)=0. - R. J. Mathar, Jan 04 2017

A319536 Number of signed permutations of length n where numbers occur in consecutive order.

Original entry on oeis.org

0, 2, 14, 122, 1278, 15802, 225886, 3670074, 66843902, 1349399162, 29912161758, 722399486074, 18881553923326, 531063524702778, 15993786127174238, 513533806880120762, 17512128958240460286, 632099987274779910394, 24076353238897830158302

Offset: 1

Leigh Foster, Sep 22 2018

nonn

a(n) also represents the number of reducible signed permutations of length n. A permutation is reducible when an adjacency occurs in the permutation.

The first 8 terms of this sequence were found by exhaustive search of all signed permutations.

			Of the 8 signed permutations of length 2: {[1,2], [-1,2], [1,-2], [-1,-2], [2,1], [-2,1], [2,-1], [-2,-1]} only two are reducible: [1,2] and [-2,-1]. Thus a(2) = 2.

Manaswinee Bezbaruah, Henry Fessler, Leigh Foster, Marion Scheepers, George Spahn, Context Directed Sorting: Robustness and Complexity, draft.

Leigh Foster, Table of n, a(n) for n = 1..50

Cf. A000165, A271212.

Table[(2 n)!!, {n, 1, 20}] - RecurrenceTable[{a[n]==(2n-1)*a[n-1]+2(n-2)*a[n-2], a[0]==1, a[1]==2}, a[n], {n, 1, 20}]

from ast import literal_eval
def checkFunc(n):
    p = SignedPermutations(n)
    permlist = p.list()
    permset = set(permlist)
    for perm in permlist:
        perm_literal = literal_eval(str(perm))
        for i in range(n-1):
            a = perm_literal[i]
            if perm_literal[i + 1] == a + 1:
                permset.remove(perm)
                break
    print(factorial(n)*(2^n)-len(permset))
# usage: checkFunc({desired permutation length})

a(n) = A000165(n) - A271212(n).

cp's OEIS Frontend

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A271214 Number of reduced rearrangement patterns with n blocks.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A271217 Number of symmetric reduced rearrangement maps.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A319536 Number of signed permutations of length n where numbers occur in consecutive order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

SageMath

Formula