login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:34 EDT 2024. Contains 370952 sequences. (Running on oeis4.)