Generating functions for descents over permutations which avoid sets of consecutive patterns

Abstract: We extend the reciprocity method of Jones and Remmel to study generating functions of the form

sum_{n geq 0} frac{t^n}{n!} sum_{sigma in mathcal{NM}_n(Gamma)}x^{mathrm{LRmin}(sigma)}y^{1+mathrm{des}(sigma)}

where

G a m m a

is a set of permutations which start with 1 and have at most one descent,

m a t h c a l {N M}_{n} (G a m m a)

is the set of permutations

s i g m a

in the symmetric group

m a t h f r a k S_{n}

which have no

G a m m a

-matches,

m a t h r m d e s (s i g m a)

is the number of descents of

s i g m a

and

m a t h r m L R m i n (s i g m a)

is the number of left-to-right minima of

s i g m a

. We show that this generating function is of the form

l e f t (f r a c 1 U_{G a m m a} (t, y) i g h t)^{x}

where

U_{G a m m a} (t, y) = s u m_{n g e q 0} U_{G a m m a, n} (y) f r a c t^{n} n!

and the coefficients

U_{G a m m a, n} (y)

satisfy some simple recursions in the case where

G a m m a

equals

1324, 123

,

1324 c d o t s p, 12 c d o t s (p - 1)

for

p g e q 5

, or

G a m m a

is the set of permutations

s i g m a = s i g m a_{1} c d o t s s i g m a_{n}

of length

n = k_{1} + k_{2}

where

k_{1}, k_{2} g e q 2

,

s i g m a_{1} = 1

,

s i g m a_{k_{1} + 1} = 2

, and

m a t h r m d e s (s i g m a) = 1

.

Recommendations

Cited in

(11)

Describes a project that uses

Uses Software

This page was built for publication: Generating functions for descents over permutations which avoid sets of consecutive patterns