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

1, 1, 2, 5, 14, 43, 143, 509, 1921, 7631, 31725, 137412, 617822, 2874819, 13809305, 68331089, 347657464, 1815839759, 9722708061, 53301771604, 298854490602, 1712023130016, 10011533550216, 59714205975048, 363008132101658, 2247599137530241, 14164805684388087, 90810818671081267, 591921142070249872

Offset: 0

Author

Christian Bean, Nov 01 2014

Keywords

• nonn

Comments

(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.

(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.

Links

• Christian Bean, Sage code
• Christian Bean, A Claesson, H Ulfarsson, Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3, arXiv preprint arXiv:1512.03226 [math.CO], 2015.
• Zhicong Lin, Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.

Crossrefs

Cf. A249560, A249561, A249563.

Formula

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

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

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] )

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

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

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

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

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

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.

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] )