کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423879 1632593 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Permutations with few internal points
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Permutations with few internal points
چکیده انگلیسی

Let the records of a permutation σ be its left-right minima, right-left minima, left-right maxima and right-left maxima. Conversely let a point (i,j) with j=σ(i) be an internal point of σ if it is not a record. Permutations without internal points have recently attracted attention under the name square permutations. We consider here the enumeration of permutations with a fixed number of internal points.We show that for each fixed i the generating function of permutations with i internal points with respect to the size is algebraic of degree 2. More precisely it is a rational function in the Catalan generating function. Our approach is constructive, yielding a polynomial uniform random sampling algorithm, and it can be refined to enumerate permutations with respect to each of the four types of records.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 291-296
نویسندگان
, , , ,