|
Search: id:A100749
|
|
|
| A100749 |
|
Triangle read by rows: T(n,k)=number of 231- and 312-avoiding permutations of [n] having k fixed points. |
|
+0
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; listen)
|
|
|
OFFSET
|
0,8
|
|
|
COMMENT
|
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).
|
|
REFERENCES
|
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-tz-2z^2).
|
|
EXAMPLE
|
T(4,2)=5 because we have 1432, 1243, 1324, 2134 and 3214.
Triangle begins:
1;
0,1;
1,0,1;
0,3,0,1;
2,0,5,0,1;
0,8,0,7,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
|
|
CROSSREFS
|
Cf. A000079.
Sequence in context: A065718 A025428 A021336 this_sequence A124027 A097610 A161556
Adjacent sequences: A100746 A100747 A100748 this_sequence A100750 A100751 A100752
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 14 2005
|
|
|
Search completed in 0.002 seconds
|
