login
This site is supported by donations 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

Alois P. Heinz, Rows n = 0..140, flattened

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

Adjacent sequences:  A100746 A100747 A100748 * A100750 A100751 A100752

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 23 02:48 EDT 2017. Contains 288633 sequences.