A249562 -id:A249562 - cp's OEIS frontend

A249560 Number of length n permutations avoiding (231,{1},{}) and (132,{},{2}).

1, 1, 2, 4, 9, 22, 58, 163, 485, 1519, 4985, 17077, 60871, 225152, 862150, 3410641, 13913800, 58440010, 252348913, 1118802690, 5086910935, 23693925911, 112947299251, 550527774738, 2741489275969, 13936841789100, 72277551806634, 382134348251357, 2058420014680378

Offset: 0

Christian Bean, Nov 01 2014

nonn

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

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

Alois P. Heinz, Table of n, a(n) for n = 0..300
Christian Bean, A Claesson, H Ulfarsson, Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3, arXiv preprint arXiv:1512.03226, 2015

Cf. A249561, A249562, A249563.

if i = 1: a(n,k,i) = sum( a(n-1,k,j) for j in [1..k] )
if i = k: a(n,k,i) = sum( a(n-1,k-1,j) + a(n-1,k,j) for j in [1..k-1] )
otherwise: a(n,k,i) = sum( a(n-1,k,j) for j in [1..i-1] )
where n is the length, k is the number of right to left minima and i is the position of the maximum in relation to the right to left minima.
Initial Conditions: if k > n or i > k then a(n,k,i) = 0, if k = 1 then a(n,k,i) = 1.
Then a(n) = sum( sum( a(n,k,i) for i in [1..k]) for k in [1..n] ).
G.f: 1 + x * sum(x^n * F_n(1+x) for n >= 0) where F_n(q) = sum( [n,m] for m in [0..n] ). Note [n,m] is the q-binomial. - Christian Bean, Jun 03 2015

More terms from Alois P. Heinz, Nov 01 2014

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

Original entry on oeis.org

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

Offset: 0

Christian Bean, Nov 01 2014

nonn

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

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.

Cf. A249560, A249562, A249563.

a[n_, r_, i_] := a[n, r, i] = Which[nJean-François Alcover, Dec 02 2014, translated and adapted from Sage code *)

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

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

Original entry on oeis.org

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

Offset: 0

Christian Bean, Nov 01 2014

nonn

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

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

Cf. A249560, A249561, A249562.

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

cp's OEIS Frontend

A249560 Number of length n permutations avoiding (231,{1},{}) and (132,{},{2}).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula