A100749 - OEIS

%I #24 Mar 31 2014 19:08:40

%S 1,0,1,1,0,1,0,3,0,1,2,0,5,0,1,0,8,0,7,0,1,4,0,18,0,9,0,1,0,20,0,32,0,

%T 11,0,1,8,0,56,0,50,0,13,0,1,0,48,0,120,0,72,0,15,0,1,16,0,160,0,220,

%U 0,98,0,17,0,1,0,112,0,400,0,364,0,128,0,19,0,1,32,0,432,0,840,0,560,0,162,0,21,0,1

%N Triangle read by rows: T(n,k)=number of 231- and 312-avoiding permutations of [n] having k fixed points.

%C Also number of compositions of n having k odd parts. Example: T(3,1)=3 because we have 3=2+1=1+2.

%C Row n has n+1 terms.

%C Sum of row n is 2^(n-1) (A000079(n-1)) for n>0.

%H Alois P. Heinz, <a href="/A100749/b100749.txt">Rows n = 0..140, flattened</a>

%H T. Mansour and A. Robertson, <a href="http://dx.doi.org/10.1007/s000260200013">Refined restricted permutations avoiding subsets of patterns of length three</a>, Annals of Combinatorics, 6, 2002, 407-418 (Theorem 2.8).

%F T(n, k)=2^[(n-k-2)/2]*[(n+3k)/(n-k)]*binomial((n+k-2)/2, k) if k<n and n-k=0 (mod 2); T(n, n)=1.

%F G.f.: (1-z^2)/(1-t*z-2*z^2).

%F G.f. for column k: x^k*(1-x^2)/(1 - 2*x^2)^(k+1). - _Geoffrey Critzer_, Mar 31 2014

%e T(4,2) = 5 because we have 1432, 1243, 1324, 2134 and 3214.

%e Triangle begins:

%e 00: 1,

%e 01: 0, 1,

%e 02: 1, 0, 1,

%e 03: 0, 3, 0, 1,

%e 04: 2, 0, 5, 0, 1,

%e 05: 0, 8, 0, 7, 0, 1,

%e 06: 4, 0, 18, 0, 9, 0, 1,

%e 07: 0, 20, 0, 32, 0, 11, 0, 1,

%e 08: 8, 0, 56, 0, 50, 0, 13, 0, 1,

%e 09: 0, 48, 0, 120, 0, 72, 0, 15, 0, 1,

%e 10: 16, 0, 160, 0, 220, 0, 98, 0, 17, 0, 1,

%e 11: 0, 112, 0, 400, 0, 364, 0, 128, 0, 19, 0, 1,

%e 12: 32, 0, 432, 0, 840, 0, 560, 0, 162, 0, 21, 0, 1,

%e 13: 0, 256, 0, 1232, 0, 1568, 0, 816, 0, 200, 0, 23, 0, 1,

%e 14: 64, 0, 1120, 0, 2912, 0, 2688, 0, 1140, 0, 242, 0, 25, 0, 1,

%e 15: 0, 576, 0, 3584, 0, 6048, 0, 4320, 0, 1540, 0, 288, 0, 27, 0, 1,

%e ...

%p T:=proc(n,k) if k=n then 1 elif k<n and n-k mod 2 =0 then 2^((n-k-2)/2)*(n+3*k)*binomial((n+k-2)/2,k)/(n-k) else 0 fi end: for n from 0 to 13 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

%p # second Maple program

%p T:= proc(n) option remember; local j; if n=0 then 1

%p       else []; for j to n do zip((x, y)-> x+y, %,

%p       [`if`(irem(j,2)=1, 0, [][]), T(n-j)], 0) od; %[] fi

%p     end:

%p seq (T(n), n=0..20);  # _Alois P. Heinz_, Nov 06 2012

%t t[n_, k_] := Which[k == n, 1, k<n && Mod[n-k, 2] == 0, 2^((n-k-2)/2)*(n+3*k)*Binomial[(n+k-2)/2, k]/(n-k), True, 0]; Table[t[n, k], {n, 0, 20}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jan 17 2014 *)

%Y Cf. A000079.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Jan 14 2005