login
Number of length n permutations avoiding (123,{2},{}) and (123,{},{1}).
4

%I #27 Nov 11 2019 18:36:38

%S 1,1,2,5,14,43,143,509,1921,7631,31725,137412,617822,2874819,13809305,

%T 68331089,347657464,1815839759,9722708061,53301771604,298854490602,

%U 1712023130016,10011533550216,59714205975048,363008132101658,2247599137530241,14164805684388087,90810818671081267,591921142070249872

%N Number of length n permutations avoiding (123,{2},{}) and (123,{},{1}).

%C (123,{2},{}) is a vincular pattern. It has underlying classical pattern 123 and the extra requirement that the 2 and the 3 are adjacent in the permutation.

%C (123,{},{1}) is a co-vincular pattern. It has underlying classical pattern 123 and the extra requirement that the 1 and 2 are exactly one apart in the permutation.

%H Christian Bean, <a href="/A249562/a249562.txt">Sage code</a>

%H Christian Bean, A Claesson, H Ulfarsson, <a href="http://arxiv.org/abs/1512.03226">Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3</a>, arXiv preprint arXiv:1512.03226 [math.CO], 2015.

%H Zhicong Lin, Sherry H. F. Yan, <a href="https://doi.org/10.1016/j.amc.2019.124672">Vincular patterns in inversion sequences</a>, Applied Mathematics and Computation (2020), Vol. 364, 124672.

%F If x appears after x-1 in the permutation then we say that x is a ceiling point.

%F if i = 1: aup(n,k,i,l) = sum( abar(n,k,i,l) for m in [0..k] )

%F otherwise: aup(n,k,i,l) = sum( abar(n-1,k,1,m) for m in [l..k] ) + sum( sum( adown(n-1,k,j,m) for m in [i..k]) for j in [1..i-1] )

%F abar(n,k,i,l) = sum( a(n-1,k-1,j,l-1) for j in [1..k-1] )

%F adown(n,k,i,l) = sum( aup(n-1,k,j,l) + adown(n-1,k,j,l) for j in [i..k] )

%F a(n,k,i,l) = aup(n,k,i,l) + adown(n,k,i,l) + abar(n,k,i,l)

%F where n is the length, k is the number of left to right minima, i is the position of the maximum, l is the position of the first ceiling point

%F aup implies that max is a ceiling point, abar implies that max is a left to right minimum and adown implies max is neither.

%F Initial conditions: if i > l or k > n or i > k or l > k then aup(n,k,i,l) = adown(n,k,i,l) = 0, if i < l or l <= 0 then aup(n,k,i,l) = 0, if n - k = 1 then a(n,k,i,l) = 1, if i does not equal 1 the abar(n,k,i,l) = 0, abar(n,n,1,0) = 1.

%F a(n) = sum( sum( sum( a(n,k,j,m) for m in [0..k] ) for j in [1..k] ) for k in [1..n] )

%Y Cf. A249560, A249561, A249563.

%K nonn

%O 0,3

%A _Christian Bean_, Nov 01 2014