<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue3" %>
Coloured Permutations Containing and Avoiding Certain Patterns
Toufik Mansour
Department of Mathematics, Chalmers University of Technology, 412 96 Göteborg, Sweden
toufik@math.chalmers.se
Annals of Combinatorics 7 (3) p.349-355 September, 2003
AMS Subject Classification: 05A05, 05A15
Abstract:
Let be the set of all coloured permutations on the symbols 1, 2, ..., n with colours 1, 2, ..., r, which is the analogous of the symmetric group when r = 1, and the hyperoctahedral group when r = 2. Let I {1, 2, ..., r} be a subset of d colours; we define to be the set of all coloured permutations such that where c I. We prove that the number of -avoiding coloured permutations in equals for n k where hj = (r-d)j+(k-1)d. We then prove that for any (or any ), the number of coloured permutations in which avoid all patterns in (or in ) except for and contain exactly once equals for n k. Finally, for any , 2mk-1, this number equals for n k+1. These results generalize recent results due to Mansour, Mansour and West, and Simion.
Keywords: alternating permutations, restricted permutations, generating functions, Chebyshev polynomials

References:

1. D.A. Beck, The combinatorics of symmetric functions and permutation enumeration of the hyperoctahedral group, Discrete Math. 163 (1997) 13每45.

2. S. Billey and T. Kailam, Vexillary elements in hyperoctahedral group, J. Algebraic Combin. 8 (1998) 139每152.

3. S.C. Billey, Pattern avoidance and rational smoothness of Schubert varieties, Adv. Math. 139 (1998) 141每156.

4. M. Bona and R. Simion, A self-dual poset on objects counted by the Catalan numbers and a Type-B analogue, Discrete Math. 220 (2000) 35每49.

5. F. Brenti,Combinatorial properties of the Kazhdan-Lusztig R-polynomials for Sn, Adv. Math. 126 (1997) 21每51.

6. T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discrete Math. 204 (1999) 119每128.

7. S. Fomin and A.N. Kirillov, Combinatorial Bn-analogies of Schubert polynomials, Trans. Amer. Math. Soc. 348 (9) (1996) 3591每3620.

8. D.E. Knuth, The Art of Computer Programming, 2nd Ed., Addison Wesley, Reading, MA, 1973.

9. C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001) 510每530.

10. V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in Sl(n)/B, Proc. Indian Acad. Sci. 100 (1990) 45每52.

11. C. Montenegro, The fixed point non-crossing partition lattices, manuscript, 1993.

12. T. Mansour, Permutations containing and avoiding certain patterns, In: Proc. 12th Conference on Formal Power Series and Algebraic Combinatorics, Moscow, 2000.

13. T. Mansour, Pattern avoidance in coloured permutations, Sémi. Lothar. Combin. B46g (2001).

14. T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Elect. J. Combin. 7 (2000) #R17.

15. T. Mansour and A. Vainshtein, Layered restrictions and Chebyshev polynomials, Ann. Combin. 5 (2001) 451每458.

16. T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math. 26 (2001) 258每269.

17. T. Mansour and A. Vainshtein, Avoiding maximal parabolic subgroups of Sk, Discrete Math. Theoret. Comput. Sci. 4 (2000) 67每77.

18. T. Mansour and J. West, Avoiding 2-letter signed patterns, Sémi. Lothar. Combin. B49a (2002).

19. V. Reiner, >Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997) 195每222.

20. R. Simion, Combinatorial statistics on type-B analogies of noncrossing partitions and restricted permutations, Elect. J. Combin. 7 (2000) #R9.

21. R. Simion and F. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985) 383每406.

22. E. Steingrimsson, Permutation statistics of indexed permutations, Europ. J. Combin. 15 (1994) 187每205.

23. J. West, Permutations with forbidden subsequences and stacksortable permutations, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, 1990.

24. R. Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach. 19 (1972) 341每346.