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!)
A249561 Number of length n permutations avoiding (123,{1},{}) and (231,{},{2}). 4
1, 1, 2, 4, 9, 22, 57, 155, 440, 1299, 3977, 12596, 41181, 138711, 480548, 1709714, 6238685, 23319998, 89199763, 348799322, 1393087403, 5678298218, 23603135064, 99984420371, 431347901729, 1894074165622, 8460557754681, 38424506440883, 177342850025592, 831413025268569, 3957592646327463 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

These can be counted recursively in the following way. If you let n be the length, r be the number of left to right minima and i be the position of the leftmost point with respect to the left to right minima then we get that

a(n,r,1) = a(n-1,r,r) + a(n-1,r,1) + a(n-1,r-1,r-1)

a(n,r,r) = sum( a(n-1,r,j) for j in [1..r] )

a(n,r,i) = a(n-1,r,r) + sum( a(n-1,r,j) for j in [1..i] )

which with the initial conditions that n must be greater than or equal to r and r greater than or equal to i and a(n,1,1) = 1.

Then a(n) = sum( sum( a(n,r,i) for i in [1..r] ) for r in [1..n] ).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..400

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

Yan X Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318 [math.CO], 2015. See Fig. 8.

FORMULA

G.f: 1 + x/(1-x) * sum( sum( x^(i+k) * F_n+1,k(1/(1-x)) for k in [0..n+1] ) for n >= 0 ) where F_n,k(q) = q^n * q^C(k,2) * [n-1,k-1] and [a,b] is the q-binomial. - Christian Bean, Jun 03 2015

MATHEMATICA

a[n_, r_, i_] := a[n, r, i] = Which[n<r || r<i, 0, r == 1, 1, i == r, Sum[a[n-1, r, j], {j, 1, r}], i == 1, a[n-1, r, r]+a[n-1, r, 1]+a[n-1, r-1, r-1], True, a[n-1, r, r]+Sum[a[n-1, r, j], {j, 1, i}]]; a[n_, r_] := Sum[a[n, r, i], {i, 1, r}]; a[n_] := Sum[a[n, r], {r, 1, n}]; a[0] = 1; Table[a[i], {i, 0, 30}] (* Jean-Fran├žois Alcover, Dec 02 2014, translated and adapted from Sage code *)

CROSSREFS

Cf. A249560, A249562, A249563.

Sequence in context: A287709 A196161 A333069 * A099241 A337067 A249563

Adjacent sequences:  A249558 A249559 A249560 * A249562 A249563 A249564

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 May 13 14:47 EDT 2021. Contains 343860 sequences. (Running on oeis4.)