login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A249563 Number of length n permutations avoiding (132,{2},{}) and (123,{},{1}). 4
1, 1, 2, 4, 9, 22, 57, 156, 447, 1335, 4140, 13290, 44055, 150494, 528860, 1909010, 7068879, 26820161, 104156616, 413634176, 1678323602, 6952182325, 29378908664, 126568357635, 555540596435, 2482857618713, 11292588202568, 52241502972732, 245700673227652, 1174263543570678, 5700387781450739 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

(132,{2},{}) is a vincular pattern. It has underlying classical pattern 132 and the extra requirement that the 3 and the 2 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

Table of n, a(n) for n=0..30.

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, 2015

FORMULA

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

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

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

if i = 1 and l <= 1: adown(n,k,i,l) = sum( adown(n-1,k,j,l) for j in [i+1..k] ) + sum( a(n-1,k-1,j,l-1) for j in [1..k-1] )

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

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

a(n,k,i,l) = aup(n,k,i,l) + adown(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 where if l = 0 there is no ceiling point (notice positions are in relation the position of the left to right minima).

aup implies the maximum is a ceiling point and adown implies the maximum is not a ceiling point.

Initial Conditions: if k > n or i > k or i > l then aup(n,k,i,l) - adown(n,k,i,l) = 0, if i > l then aup(n,k,i,l) = 0, and finally aup(n,n-1,i,l) = 1.

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

CROSSREFS

Cf. A249560, A249561, A249562.

Sequence in context: A249561 A099241 A337067 * A124380 A176084 A192576

Adjacent sequences:  A249560 A249561 A249562 * A249564 A249565 A249566

KEYWORD

nonn

AUTHOR

Christian Bean, Nov 01 2014

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 06:24 EDT 2021. Contains 345358 sequences. (Running on oeis4.)