|
%I #39 Sep 27 2016 14:18:18
%S 1,1,2,4,9,22,57,155,440,1299,3977,12596,41181,138711,480548,1709714,
%T 6238685,23319998,89199763,348799322,1393087403,5678298218,
%U 23603135064,99984420371,431347901729,1894074165622,8460557754681,38424506440883,177342850025592,831413025268569,3957592646327463
%N Number of length n permutations avoiding (123,{1},{}) and (231,{},{2}).
%C (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.
%C (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.
%C 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
%C a(n,r,1) = a(n-1,r,r) + a(n-1,r,1) + a(n-1,r-1,r-1)
%C a(n,r,r) = sum( a(n-1,r,j) for j in [1..r] )
%C a(n,r,i) = a(n-1,r,r) + sum( a(n-1,r,j) for j in [1..i] )
%C 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.
%C Then a(n) = sum( sum( a(n,r,i) for i in [1..r] ) for r in [1..n] ).
%H Alois P. Heinz, <a href="/A249561/b249561.txt">Table of n, a(n) for n = 0..400</a>
%H Christian Bean, <a href="/A249561/a249561_2.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, 2015
%H Yan X Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015. See Fig. 8.
%F 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
%t 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 *)
%Y Cf. A249560, A249562, A249563.
%K nonn
%O 0,3
%A _Christian Bean_, Nov 01 2014
|
