login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A100749
Triangle read by rows: T(n,k)=number of 231- and 312-avoiding permutations of [n] having k fixed points.
1
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, 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, 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
OFFSET
0,8
COMMENTS
Also number of compositions of n having k odd parts. Example: T(3,1)=3 because we have 3=2+1=1+2.
Row n has n+1 terms.
Sum of row n is 2^(n-1) (A000079(n-1)) for n>0.
LINKS
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Annals of Combinatorics, 6, 2002, 407-418 (Theorem 2.8).
FORMULA
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.
G.f.: (1-z^2)/(1-t*z-2*z^2).
G.f. for column k: x^k*(1-x^2)/(1 - 2*x^2)^(k+1). - Geoffrey Critzer, Mar 31 2014
EXAMPLE
T(4,2) = 5 because we have 1432, 1243, 1324, 2134 and 3214.
Triangle begins:
00: 1,
01: 0, 1,
02: 1, 0, 1,
03: 0, 3, 0, 1,
04: 2, 0, 5, 0, 1,
05: 0, 8, 0, 7, 0, 1,
06: 4, 0, 18, 0, 9, 0, 1,
07: 0, 20, 0, 32, 0, 11, 0, 1,
08: 8, 0, 56, 0, 50, 0, 13, 0, 1,
09: 0, 48, 0, 120, 0, 72, 0, 15, 0, 1,
10: 16, 0, 160, 0, 220, 0, 98, 0, 17, 0, 1,
11: 0, 112, 0, 400, 0, 364, 0, 128, 0, 19, 0, 1,
12: 32, 0, 432, 0, 840, 0, 560, 0, 162, 0, 21, 0, 1,
13: 0, 256, 0, 1232, 0, 1568, 0, 816, 0, 200, 0, 23, 0, 1,
14: 64, 0, 1120, 0, 2912, 0, 2688, 0, 1140, 0, 242, 0, 25, 0, 1,
15: 0, 576, 0, 3584, 0, 6048, 0, 4320, 0, 1540, 0, 288, 0, 27, 0, 1,
...
MAPLE
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
# second Maple program
T:= proc(n) option remember; local j; if n=0 then 1
else []; for j to n do zip((x, y)-> x+y, %,
[`if`(irem(j, 2)=1, 0, [][]), T(n-j)], 0) od; %[] fi
end:
seq (T(n), n=0..20); # Alois P. Heinz, Nov 06 2012
MATHEMATICA
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 *)
CROSSREFS
Cf. A000079.
Sequence in context: A025428 A199176 A021336 * A124027 A097610 A161556
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jan 14 2005
STATUS
approved