|
%I #27 Dec 19 2023 13:39:52
%S 1,1,1,2,8,32,192,1272,10176,90816,908160,9980160,119761920,
%T 1556766720,21794734080,326918753280,5230700052480,88921859604480,
%U 1600593472880640,30411275148656640,608225502973132800,12772735543856332800,281000181964839321600,6463004184741681561600,155112100433800357478400,3877802510833236993638400
%N Number of trivial c-Wilf equivalence classes in the symmetric group S_n.
%C 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}.
%C a(n) is an upper bound of c-Wilf equivalence classes in the symmetric group S_n.
%C 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.
%H Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://arxiv.org/abs/2312.07716">Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding</a>, arXiv:2312.07716 [math.CO], 2023.
%H Adrian Duane and Jeffrey Remmel, <a href="https://doi.org/10.37236/2021">Minimal overlapping patterns in colored permutations</a>, Electron. J. Combin. 18 (2011) #P25.
%H Brian Koichi Nakamura, <a href="http://dx.doi.org/10.7282/T3C24V02">Computational methods in permutation patterns</a>, Ph. D. dissertation at Rutgers University, 2013.
%F 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.
%F 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
%p a := proc(n) option remember; if n < 5 then return [1, 1, 1, 2, 8][n+1] fi;
%p (n*(n-3)*a(n-1) + (n-1)^2*a(n-2) - (n-2)*(n-1)^2*a(n-3))/(n-3) end:
%p seq(a(n), n = 0..25); # _Peter Luschny_, Nov 25 2022
%t 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 *)
%o (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
%Y Cf. A000165, A000142.
%K nonn
%O 0,4
%A _Ran Pan_, Sep 24 2015
|
