The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A262480 Number of trivial c-Wilf equivalence classes in the symmetric group S_n. 4
1, 1, 1, 2, 8, 32, 192, 1272, 10176, 90816, 908160, 9980160, 119761920, 1556766720, 21794734080, 326918753280, 5230700052480, 88921859604480, 1600593472880640, 30411275148656640, 608225502973132800, 12772735543856332800, 281000181964839321600, 6463004184741681561600, 155112100433800357478400, 3877802510833236993638400 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
A permutation pattern is c-Wilf equivalent to its complement and reverse and therefore we can get trivial equivalence classes based on complement and reverse. a(3) = 2 because there are two trivial c-Wilf equivalence classes {123, 321} and {132, 231, 213, 321}.
a(n) is an upper bound of c-Wilf equivalence classes in the symmetric group S_n.
The numbers of c-Wilf equivalence classes in S_n are still unknown for large n. Up to 6, they are 1, 1, 2, 7, 25, 92.
LINKS
Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, arXiv:2312.07716 [math.CO], 2023.
Adrian Duane and Jeffrey Remmel, Minimal overlapping patterns in colored permutations, Electron. J. Combin. 18 (2011) #P25.
Brian Koichi Nakamura, Computational methods in permutation patterns, Ph. D. dissertation at Rutgers University, 2013.
FORMULA
a(0) = a(1) = 1, a(2*n) = ((2*n)!+(2*n)!!)/4, a(2*n+1) = ((2*n+1)!+(2*n)!!)/4, for n >= 1.
D-finite with recurrence: -(n-3)*a(n) + n*(n-3)*a(n-1) + (n-1)^2*a(n-2) - (n-2)*(n-1)^2*a(n-3) = 0 for n >= 5. - Georg Fischer, Nov 25 2022
MAPLE
a := proc(n) option remember; if n < 5 then return [1, 1, 1, 2, 8][n+1] fi;
(n*(n-3)*a(n-1) + (n-1)^2*a(n-2) - (n-2)*(n-1)^2*a(n-3))/(n-3) end:
seq(a(n), n = 0..25); # Peter Luschny, Nov 25 2022
MATHEMATICA
Join[{1, 1}, RecurrenceTable[{-(n-3)*a[n] + n*(n-3)*a[n-1] + (n-1)^2*a[n-2] - (n-2)*(n-1)^2*a[n-3] == 0, a[2]==1, a[3]==2, a[4]==8}, a, {n, 2, 25}]] (* Georg Fischer, Nov 25 2022 *)
PROG
(PARI) a(n) = if(n<=1, 1, if (n%2, n=(n-1)/2; ((2*n+1)!+2^n*n!)/4, n=n/2; ((2*n)!+2^n*n!)/4)); \\ Michel Marcus, Nov 25 2022
CROSSREFS
Sequence in context: A294506 A206303 A048855 * A062797 A369645 A134751
KEYWORD
nonn
AUTHOR
Ran Pan, Sep 24 2015
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 14 12:37 EDT 2024. Contains 373400 sequences. (Running on oeis4.)