Printer Friendly

Enumeration of derangements with descents in prescribed positions.

1 Introduction

In a permutation [pi] [member of] [[??].sub.n], a descent is a position i such that [[pi].sub.i] > [[pi].sub.i] + 1, and an ascent is a position where [[pi].sub.i] < [[pi].sub.i] + 1. A fixed point is a position i where [[pi].sub.i] = i. If [[pi].sub.i] > i, then i is called an excedance, while if [[pi].sub.i] < i, i is a deficiency. Richard Stanley (11) conjectured that permutations in [[??].sub.2n] with descents at and only at odd positions (commonly known as alternating permutations) and n fixed points are equinumerous with permutations in [[??].sub.n] without fixed points, commonly known as derangements.

The conjecture was given a bijective proof by Chapman and Williams in 2007 (1). The solution is quite straightforward: Assume [pi] [member of] [[??].sub.2n] is alternating and F [subset equal to] [2n] is the set of fixed points, [absolute value of F] = n. Then removing the fixed points gives a permutation [tau] in [[??].sub.[2n]\F] without fixed points, and [pi] can be easily reconstructed from [tau].

For instance, removing the fixed points in [pi] = 326451 gives [tau] = 361 or [tau] = 231 if we reduce it to [[??].sub.3]. To recover [pi], we note that the fixed points in the first two descending blocks must be at the respective second positions, 2 and 4, since both [[tau].sub.1] and [[tau].sub.2] are excedances, that is above the fixed point diagonal [[tau].sub.i] = i. On the other hand, since [[tau].sub.3] < 3, the fixed point in the third descending block comes in its first position, 5. With this information, we immediately recover [pi].

Alternating permutations are permutations which fall in and only in blocks of length two. A natural generalisation comes by considering permutations which fall in blocks of lengths [a.sub.1], [a.sub.2], ..., [a.sub.k] and have k fixed points (this is obviously the maximum number of fixed points, since each descending block can have at most one). These permutations are in bijection with derangements which descend in blocks of length [a.sub.1] - 1, [a.sub.2] - 1, ..., [a.sub.k] - 1, and possibly also between them, a fact which was proved by Guo-Niu Han and Guoce Xin (9).

In this article we compute the number of derangements which have descents in prescribed blocks and possibly also between them. A generating function was given by Han and Xin using a representation theory argument. We start by computing the generating function using simple combinatorial arguments (Section 3), and then proceed to extract a closed formula in Section 4.

Interestingly, this formula, which is a combination of factorials, can also be written as the same combination of an infinite family of other numbers, including the derangement numbers. We give a combinatorial interpretation of these families as the number of fixed point [lambda]-coloured permutations.

For a uniformly chosen permutation, the events that it is a derangement and that its descent set is included in a given set are not independent. We prove that except for the permutations of odd length with no ascents, these events are positively correlated. In fact, we prove that the number of permutations which are derangements when sorted decreasingly in each block is larger when there are few and large blocks, compared to many small blocks. The precise statement is found in Section 7.

Finally, in Section 8, we generalise some results concerning Euler's difference triangles from (10) to fixed point [lambda]-coloured permutations, using a new combinatorial interpretation. This interpretation is in line with the rest of this article, counting permutations having an initial descending segment and [lambda]-coloured fixed points to the right of the initial segment. In addition, we also derive a relation between difference triangles with different values of [lambda].

There are many papers devoted to counting permutations with prescribed descent sets and fixed points, see for instance (6; 8) and references therein. More recent related papers include (4), where Corteel et al. considered the distribution of descents and major index over permutations without descents on the last i positions, and (2), where Chow considers the problem of enumerating the involutions with prescribed descent set.

This paper is an extended abstract, with some proofs missing. These can be found in the full paper (7).

2 Definitions and examples

Let [i, j] = {i, i + 1, ..., j} and [n] = [1, n]. We think of [n] as being decomposed into blocks of lengths [a.sub.1], ..., [a.sub.k], and we will consider permutations that decrease within these blocks. The permutations are allowed to decrease or increase in the breaks between the blocks.

Consider a sequence a = ([a.sub.1], [a.sub.2], ..., [a.sub.k]) of nonnegative integers, with [[summation].sub.j] [a.sub.i] = n, and let [c.sub.j] = [[summation].sup.j.sub.i=1] [a.sub.i]. We denote by [A.sub.j] the j:th block of a, that is the set [A.sub.j] = [[c.sub.j-1] + 1, [c.sub.j]] [subset equal to] [n]. Throughout the paper, k will denote the number of blocks in a given composition. We let [[??].sub.a] [subset equal to] [[??].sub.n] be the set of permutations that have descents at every place within the blocks, and may or may not have descents in the positions [c.sub.j]. In particular we have [[??].sub.n] = [[??].sub.(1,1, ..., 1)].

Example 2.1 If n = 6 and a = (4,2), then we consider permutations that are decreasing in [1,4] and in [5,6]. Such a permutation is uniquely determined by the partition of the numbers 1-6 into these blocks, so the total number of such permutations is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Of these 15 permutations, those that are derangements are

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We define D(a) to be the subset of [[??].sub.a] consisting of derangements, and our objective is to enumerate this set. For simplicity, we also define [D.sub.n] = D(1, ..., 1).

For every composition a of n, there is a natural map [[PI].sub.a] : [[??].sub.n] [right arrow] [[??].sub.a], given by simply sorting the entries in each block in decreasing order. For example, if [sigma] = 25134, we have [[PI].sub.(3,2)]([sigma]) = 52143. Clearly each fiber of this map has [a.sub.i]! ... [a.sub.k]! elements.

The following maps on permutations will be used frequently in the paper.

Definition 2.1 For [sigma] [member of] [[??].sub.n], let [[phi].sub.j,k]([sigma]) = [[tau].sub.1] ... [[tau].sub.j- 1]k[[tau].sub.j] ... [[tau].sub.n], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly, let [[psi].sub.j]([sigma]) = [[tau].sub.1] ... [[tau].sub.j-1][[tau].sub.j+1] ... [[tau].sub.n], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, [[phi].sub.j,k] inserts the element k at position j, increasing elements larger than k by one and shifting elements to the right of position j one step further to the right. The map [[psi].sub.j] removes the element at position j, decreasing larger elements by one and shifting those to its right one step left.

We will often use the map [[phi].sub.j] = [[phi].sub.j,j] which inserts a fixed point at position j. The generalisations to a set F of fixed points to be inserted or removed are denoted [[phi].sub.F]([sigma]) and [[psi].sub.F]([sigma]), inserting elements in increasing order and removing them in decreasing order.

The maps [phi] and [psi] are perhaps most obvious in terms of permutation matrices. For a permutation [sigma] [member of] [[??].sub.n], we get [[phi].sub.j,k]([sigma]) by adding a new row below the k:th one, a new column before the j:th one, and an entry at their intersection. Similarly, [[psi].sub.j](a) is obtained by deleting the j:th column and the [[sigma].sub.j]:th row.

Example 2.2 We illustrate by showing some permutation matrices. For [pi] = 21 and F = {1,3}, we get

[ILLUSTRATION OMITTED]

where inserted points are labeled with an extra circle.

3 A generating function

Guo-Niu Han and Guoce Xin gave a generating function for D(a) ((9), Theorem 9). In fact they proved this generating function for another set of permutations, equinumerous to D(a) by ((9), Theorem 1). What they proved was the following:

Theorem 3.1 The number [absolute value of D(a)] is the coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the expansion of

1/(1 + [x.sub.1]) ... (1 + [x.sub.k])(1 - [x.sub.1] - ... - [x.sub.k]).

The proof uses scalar products of symmetric functions. We give a more direct proof, with a combinatorial flavour. The proof uses the following definition, and the bijective result of Lemma 3.2.

Definition 3.1 We denote by [D.sub.j] (a) the set of permutations in [[??].sub.a] that have no fixed points in blocks [A.sub.1], ..., [A.sub.j]. Thus, D(a) = [D.sub.k](a).

Moreover, let [D.sup.*.sub.j](a) be the set of permutations in [[??].sub.a] that have no fixed points in the first j - 1 blocks, but have a fixed point in [A.sub.j].

Lemma 3.2 There is a bijection between [D.sub.j]([a.sub.1], ..., [a.sub.k]) and [D.sup.*.sub.j]([a.sub.1], ..., [a.sub.j-1], [a.sub.j] + 1, [a.sub.j+1], ..., [a.sub.k]).

Proof: Let [sigma] = [[sigma].sub.1] ... [[sigma].sub.n] be a permutation in [D.sub.j]([a.sub.1], ..., [a.sub.k]), and consider the block [A.sub.j] = {p, p + 1, ..., q}. Then there is an index r such that [[sigma].sub.p] ... [[sigma].sub.r-1] are excedances, and [[sigma].sub.r] ... [[sigma].sub.q] are deficiencies.

Now [[phi].sub.r]([sigma]) is a permutation of [n + 1]. It is easy to see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

All the fixed points of [sigma] are shifted one step to the right, and one new is added in the j:th block, so

[phi]([sigma]) [member of] [D.sup.*.sub.j]([a.sub.1], ..., [a.sub.j-1], [a.sub.j] + 1, [a.sub.j+1], ..., [a.sub.k]).

We see that [[psi].sub.r]([[phi].sub.r]([sigma])) = [sigma], so the map [sigma] [??] [[phi].sub.r]([sigma]) is injective.

Similarily, for a permutation [tau] [member of] [D.sup.*.sub.j]([a.sub.1], ..., [a.sub.j-1],[a.sub.j] + 1,[a.sub.j+1], ..., [a.sub.k]), let r be the fixed point in [A.sub.j]. Then [[psi].sub.r]([tau]) [member of] [D.sub.j]([a.sub.1], ..., [a.sub.k]) and [[phi].sub.r]([[psi].sub.r]([sigma])) = [sigma]. Thus, [sigma] [??] [[phi].sub.r]([sigma]) is a bijection.

We now obtain a generating function for [absolute value of D(a)], with a purely combinatorial proof. In fact, we even strengthen the result to give generating functions for [absolute value of Dj(a)], j = 0, ..., k. Theorem 3.1 then follows by letting j = k.

Theorem 3.3 The number [absolute value of [D.sub.j](a)] is the coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the expansion of

1/(1 + [x.sub.1]) ... (1 + [x.sub.j])(1 - [x.sub.1] - ... - [x.sub.k]). (1)

Proof: Let [F.sub.j](x) be the generating function for [absolute value of Dj(a)], so that [absolute value of Dj([a.sub.1], ..., [a.sub.k])] is the coefficient for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [F.sub.j](x). We want to show that [F.sub.j](x) is given by (1).

By definition, [absolute value of [D.sub.0](a)] = [absolute value of [[??].sub.a]]. But a permutation in [[??].sub.a] is uniquely determined by the set of [a.sub.1] numbers in the first block, the set of [a.sub.2] numbers in the second, etc. So [absolute value of [D.sub.0]] is the multinomial coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This is also the coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the expansion of 1 + ([summation][x.sub.i]) + ([summation][[x.sub.i]).sup.2] + ..., since any such term must come from the [([summation][x.sub.i]).sup.n]-term. Thus,

[F.sub.0](x) = 1 + ([summation][x.sub.i]) + [([summation][x.sub.i]).sup.2] + ... = 1/(1 - [x.sub.1] - ... - [x.sub.k]). (2)

Note that for any j, [D.sub.j-1](a) = [D.sub.j](a) [union] [D.sup.*.sub.j](a), and the two latter sets are disjoint. Indeed, a permutation in [D.sub.j-1] either does or does not have a fixed point in the j:th block. Hence by Lemma 3.2, we have the identity

[absolute value of [D.sub.j-1](a)] = [absolute value of [D.sub.j](a)] + [absolute value of [D.sub.j]([a.sub.1], ..., [a.sub.j-1], [a.sub.j - 1], [a.sub.j+1], ..., [a.sub.k])]. (3)

This holds also if [a.sub.j] = 0, if the last term is interpreted as 0 in that case.

In terms of generating functions, this gives the recursion [F.sub.j-1](x) = (1 + [x.sub.j])[F.sub.j](x). Hence [F.sub.0](x) = [F.sub.j](x) [[PI].sub.i[less than or equal to]j] (1 + [x.sub.i]). Thus,

[F.sub.j](x) = [F.sub.0](x)/(1 + [x.sub.1]) ... (1 + [x.sub.j]) = 1 + ([summation][x.sub.i]) + [([summation][x.sub.i]).sup.2] + .../(1 + [x.sub.1]) ... (1 + [x.sub.j]), (4)

and [absolute value of [D.sub.j](a)] is the coefficient for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the expansion of [F.sub.j].

Proof of Theorem 3.1: The set of derangements in [[??].sub.a] is just D(a) = [D.sub.k](a). Letting j = k in Theorem 3.3 gives the generating function for [absolute value of D(a)].

4 An explicit enumeration

It is not hard to explicitly calculate the numbers [absolute value of D(a)] from here. We will use [x.sup.a] as shorthand for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Every term [x.sup.a] in the expansion of F(x) is obtained by choosing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from the factor

1/1 + [x.sub.i] = [summation over (j[greater than or equal to]0)][(-[x.sub.i]).sup.j],

for some 0 [less than or equal to] [b.sub.i] [less than or equal to] [a.sub.i]. This gives us a coefficient of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For each choice of [b.sub.1], ..., [b.sub.k] we should multiply by [x.sup.a-b] from the factor

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

But every occurence of [x.sup.a-b] in this expression comes from the term [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus the coefficient of [x.sup.a-b] is the multinomial coefficient

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

Now since [absolute value of D(a)] is the coefficient of [x.sup.a] in [F.sub.k](x), we conclude that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

While the last expression in Equation (5) seems a bit more involved than necessary, it turns out to generalise in a nice way.

5 Fixed point coloured permutations

A fixed point coloured permutation in [lambda] colours, or a fixed point [lambda]-coloured permutation, is a permutation where we require each fixed point to take one of [lambda] colours. More formally it is a pair ([pi], C) with [pi] [member of] [[??].sub.n] and C : [F.sub.[pi]] [right arrow] [[lambda]], where [F.sub.[pi]] is the set of fixed points of [pi]. When there can be no confusion, we denote the coloured permutation ([pi], C) by [pi]. Thus, fixed point 1-coloured permutatations are simply ordinary permutations and fixed point 0-coloured permutations are derangements. The set of fixed point [lambda]-coloured permutations on n elements is denoted [[??].sup.[lambda].sub.n].

For the number of [lambda]-fixed point coloured permutations on n elements, we use the notation [absolute value of [[??].sup.[lambda].sub.n]] = [f.sub.[lambda]](n), the [lambda]-factorial of n. Of course, we have [f.sub.0](n) = [D.sub.n] and [f.sub.1](n) = n!. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where fix([pi]) is the number of fixed points in [pi], and we use this formula as the definition of [f.sub.[lambda]](n) for [lambda] [not equal to] N.

Lemma 5.1 For v, [lambda] [member of] C and n [member of] N, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: It suffices to show this for v, [lambda], n [member of] N, since the identity is polynomial in v and [lambda], so if it holds on N x N it must hold on all of C x C.

We divide the proof into three parts. First, assume v = [lambda]. Then all terms in the sum vanish except for j = 0, when we get [f.sub.v](n) = [f.sub.[lambda]](n).

Secondly, assuming v > [lambda], we let j denote the number of fixed points in [pi] [member of] [[??].sup.v.sub.n] which are coloured with colours from [[lambda] + 1, v]. These fixed points can be chosen in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ways, there are [f.sub.[lambda]](n - j) ways to permute and colour the remaning elements, and the colours of the high coloured fixed points can be chosen in [(v - [lambda]).sup.j] ways. Thus, the equality holds.

Finally, assuming v < [lambda], we prescribe j fixed points in [pi] [member of] [[??].sup.[lambda].sub.n] which only get to choose their colours from [v + 1, [lambda]]. These fixed points can be chosen in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ways, the remaining elements can be permuted in [f.sub.[lambda]](n - j) ways and the chosen fixed points can be coloured in [([lambda] - v).sup.j] ways, so by the principle of inclusion-exclusion, the equality holds.

With [lambda] = 1 and replacing v by [lambda], we find that

[f.sub.[lambda]](n) = n! (1 + ([lambda] - 1)/1! + [([lambda] - 1).sup.2]/2! + ... + [([lambda] - 1).sup.n]/n!) = n! [exp.sub.n]([lambda] - 1). (6)

Here we use [exp.sub.n] to denote the truncated series expansion of the exponential function. In fact, [lim.sub.n[right arrow][infinity]]n![e.sup.([lambda]-1)] - [f.sub.[lambda]](n) = 0 for all [lambda] [member of] [-1,1], although we cannot in general approximate [f.sub.[lambda]](n) by the nearest integer of n![e.sup.[lambda]-1] as for derangements.

The formula (6) also shows that

[f.sub.[lambda]](n) = n[f.sub.[lambda]](n - 1) + [([lambda] - 1).sup.n], [f.sub.[lambda]](0) = 1 (7)

which generalises the well known recursions [absolute value of [D.sub.n]] = n[absolute value of [D.sub.n-1]] + [(- 1).sup.n] and n! = n(n - 1)!.

6 Enumerating D(a) using fixed point coloured permutations

Another consequence of Equation (6) is that the [lambda]-factorial satisfies the following rule for differentiation, which is similar to the rule for differentiating powers of [lambda]:

d/d[lambda] f[lambda](n) = n x f[lambda] (n - 1). (8)

Regarding n as the cardinality of a set X, the differentiation rule (8) translates to

d/d[lambda] f[lambda] ([absolute value of X]) = [summation over (x[member of]X)]f[lambda] ([absolute value of X \ {x}]). (9)

Products of [lambda]-factorials can of course be differentiated by the product formula. This implies that if [X.sub.1], ... [X.sub.k] are disjoint sets, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now consider the expression

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

This is obtained from the right-hand side of Equation (5) by deleting the factor 1/[[PI].sub.i] [a.sub.i]! and replacing the other factorials by [lambda]-factorials. For [lambda] = 1, the expression (10) is therefore [absolute value of [[PI].sup.-1.sub.a](D(a))], the number of permutations that, when sorted in decreasing order within the blocks, have no fixed points. We want to show that (10) is independent of [lambda]. The derivative of (10) is, by the rule (9) of differentiation,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

Here each product of [lambda]-factorials occurs once with x [member of] B and once with x [not member of] B. Because of the sign [(-1).sup.[absolute value of B]], these terms cancel. Therefore (11) is identically zero, which means that (10) is independent of [lambda]. Hence we have proven the following theorem:

Theorem 6.1 For any [lambda] [member of] C, the identity

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

holds.

A particularly interesting special case is when we put [lambda] = 0. In this case, [f.sub.0](n) = [D.sub.n], so

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

This equation has some advantages over Equation (5). It has a clear main term, the one with b = 0. Moreover, since [D.sub.1] = 0, the number of terms does not increase if blocks of length 1 are added.

It should be pointed out that Theorem 6.1 can be proven directly for all [lambda] in a recursive manner, using neither the differentiation rule 8, nor the generating function in Theorem 3.3. This alternative proof is rather lengthy, and can be found in (7).

We also note that Theorem 6.1 can be used to enumerate permutations in [[??].sub.a] with [mu] allowed fixed point colours, and even [[mu].sub.i] fixed point colours in block [A.sub.i].

Corollary 6.2 For any [lambda] [member of] C and natural numbers [[mu].sub.i], 1 [less than or equal to] i [less than or equal to] k, the number of permutations ([pi], C) where [pi] [member of] [[??].sub.a] and (j [member of] [A.sub.i], [pi](j) = j) [??] C(j) = [[[mu].sub.i]] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: The numbers [c.sub.i] are one if [A.sub.i] contains a fixed point and zero otherwise. We may remove these fixed points and consider a fixed point free permutation, enumerated above. We then reinsert the fixed points and colour them in every allowed combination.

7 A correlation result

Taking a permutation at uniformly random in [[??].sub.n], the chances are about 1/e that it is a derangement, since there are n![exp.sub.n](-1) derangements in [[??].sub.n]. Moreover, there are n!/a! permutations in [[??].sub.a].

If belonging to [[??].sub.a] and being fixed point free were two independent events, we would have n![exp.sub.n](-1) permutations in [[PI].sup.-1](D(a)). This is not the case, although the main term in Equation (13) is this very number. The special case b =(1, 1, ..., 1) of Theorem 7.1 says, that belonging to [??].sub.a] and being a derangement are almost always positively correlated events. The sole exception is when a is a single block of odd length, in which case every permutation gets a fixed point when sorted.

For two compositions a and b of n, we say that a [greater than or equal to] b if, when sorted decreasingly, [[summation].sub.i[less than or equal to]j] [a.sub.i] [greater than or equal to] [[summation].sub.i[less than or equal to]j] [b.sub.i] for all j. Then we get the following monotonicity theorem.

Theorem 7.1 If a [greater than or equal to] b and a is not a single block of odd size, then

[absolute value of [[PHI].sup.-1.sub.a](D(a))] [greater than or equal to] [absolute value of [[PHI].sup.- 1.sub.a](D(b))]].

The theorem follows from a series of lemmata, all included in (7). The main point is proving that shifting any position from a smaller block to a larger one almost never decreases the number [absolute value of [[PHI].sup.-1.sub.a](D(a))]. Equivalently, for fixed [a.sub.3], ... [a.sub.k], and a = [a.sub.1] + [a.sub.2] fixed, the function [absolute value of [[PHI].sup.-1.sub.a](D(a))] is unimodal in [a.sub.1] (with the trivial exception).

A weaker, but perhaps more natural version of the correlation result is the following.

Corollary 7.2 Let n [greater than or equal to] 2 and let [pi] [member of] [[??].sub.n] be chosen uniformly at random. Then the number of descents in [pi] is positively correlated with the event that [pi] is a derangement.

Proof: For any i let [X.sub.i] be the indicator variable of the event that i is a descent of [pi]. Let Der([pi]) be the event that [pi] is a derangement. With a = (1, ..., 1,2,1, ..., 1) and b = (1,..., 1) in Theorem 7.1, we see that each [x.sub.i] is positively correlated with Der([pi]).

The number of descents in [pi] is just [[summation].sub.i][x.sub.i], and thus also has positive correlation with Der([pi]).

8 Euler's difference tables fixed point coloured

Leonard Euler introduced the integer table [([e.sup.k.sub.n]).sub.0[less than or equal to]k[less than or equal to]n] by defining [e.sup.n.sub.n] = n! and [e.sup.k-1.sub.n] = [e.sup.k.sub.n] - [e.sup.k-1.sub.n-1] for 1 [less than or equal to] k [less than or equal to] n. Apparently, he never gave a combinatorial interpretation, but a simple one was given by Dumont and Randrianarivony in (5). Indeed, [e.sup.k.sub.n] gives the number of permutations [pi] [member of] [[??].sub.n] such that there are no fixed points on the last n - k positions. Thus, [e.sup.0.sub.n] = [D.sub.n]. A q-analogue of the same result was given in (3).

It is clear from the recurrence that k! divides [e.sup.k.sub.n]. Thus, we can define the integers [d.sup.k.sub.n] = [e.sup.k.sub.n]/k!. These have recently been studied by Fanja Rakotondrajao (10), and the combinatorial interpretation of [d.sup.k.sub.n] given there was that they count the number of permutations [pi] [member of] [[??].sub.n] such that there are no fixed points on the last n - k positions and such that the first k elements are all in different cycles.

We will now generalise these integer tables to any number [lambda] of fixed point colours, and give a combinatorial interpretation that is more in line with the context of this article. The relations in (10) generalise nicely to the case with general [lambda].

Let [e.sup.k.sub.n]([lambda]) be defined by [e.sup.n.sub.n]([lambda]) = n! and [e.sup.k-1.sub.n]([lambda]) = [e.sup.k.sub.n]([lambda]) + ([lambda] - 1)[e.sup.k-1.sub.n-1]([lambda]). Then, a natural combinatorial interpretation for non-negative integer [lambda] is that [e.sup.k.sub.n]([lambda]) count the number of permutations [pi] [member of] [[??].sub.n] such that fixed points on the last n - k positions may be coloured in any one of [lambda] colours.

Similarly, we can define [d.sup.k.sub.n]([lambda]) = [e.sup.k.sub.n]([lambda])/k! and interpret these numbers as counting the number of permutations [pi] [member of] [[??].sub.(k,1,1, ...,1)] [subset equal to] [[??].sub.n] such that fixed points on the last n - k positions may be coloured in any one of [lambda] colours. The set of these permutations is denoted [D.sup.k.sub.n]([lambda]). Thus, our intepretation for [lambda] = 0 states that apart from forbidding fixed points at the end, we also demand that the first k elements are in descending order. Equivalently, we could have considered permutations ending with k - 1 ascents and having [lambda] fixed point colours in the first n - k positions, to be closer to the setting in (4).

There are a couple of relations that can proven bijectively with this interpretation, generalising the results with [lambda] = 0 from (10). The following propositions are all given bijective proofs in (7).

Proposition 8.1 For integers 1 [less than or equal to] k [less than or equal to] n and [lambda] [member of] C we have

[d.sup.k-1.sub.n]([lambda]) = k[d.sup.k.sub.n]([lambda]) + ([lambda] - 1)[d.sup.k-1.sub.n-1]([lambda]).

Proposition 8.2 For integers 0 [less than or equal to] k [less than or equal to] n - 1 and [lambda] [member of] C we have

[d.sup.k.sub.n]([lambda]) = n[d.sup.k.sub.n-1]([lambda]) + ([lambda] - 1)[d.sup.k-1.sub.n-2]([lambda]).

Proposition 8.3 For integers 0 [less than or equal to] k [less than or equal to] n - 1 and [lambda] [member of] C we have

[d.sup.k.sub.n]([lambda]) = (n + ([lambda] - 1)) [d.sup.k.sub.n-1]([lambda]) - ([lambda] - 1)(n - k - 1) [d.sup.k.sub.n-2]([lambda]).

These formulae allow us to once again deduce the recursion for the [lambda]-factorials. Using Proposition 8.3 extended to k = -1 and [d.sup.-1.sub.-1]([lambda]) = 1, we get by induction [d.sup.-1.sub.n] = ([lambda] - 1)[d.sup.-1.sub.n-1] and hence [d.sup.-1.sub.n] = [([lambda] - 1).sup.n+1]. Thus, by Proposition 8.2 we have [f.sub.[lambda]](n) = [d.sup.0.sub.n] = n[d.sup.0.sub.n-1] + ([lambda] - 1)n. We can also use Proposition 8.3 to obtain, using (7) and [f.sub.[lambda]](n) = [d.sup.0.sub.n], that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which specialises to the well-known

[D.sub.n] = (n - 1)([D.sub.n-1] + [D.sub.n-2])

and n! = (n - 1)((n - 1)! + (n - 2)!).

We close this section by noting that Lemma 5.1 can be generalised to [d.sup.k.sub.n]([lambda]) as follows. The proof is completely analogous.

Proposition 8.4 For v, [lambda] [member of] C and 0 [less than or equal to] k [less than or equal to] n [member of] N, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

9 Open problems

While many of our results have been shown bijectively, there are a few that still seek their combinatorial explanation. The most obvious are these.

Problem 9.1 Give a combinatorial proof, using the principle of inclusion-exclusion, of Theorem 6.1.

Problem 9.2 Give a bijection f : [[??].sub.n] [right arrow] [[??].sub.n] such that [pi] [member of] D([a.sub.1], [a.sub.2], ... [a.sub.k]) [??] f([pi]) [member of] D([a.sub.1] + 1, [a.sub.2] - 1, [a.sub.3], ..., [a.sub.k]) whenever [a.sub.1] [greater than or equal to] [a.sub.2] and a [not equal to] (2m, 1).

We would also like the rearrangement of blocks in D(a) to get a simple description.

Problem 9.3 For any ([a.sub.1], ..., [a.sub.k]) and any [sigma] [member of] [[??].sub.k], give a simple bijection [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Instead of specifying descents, we could specify spots where the permutation must not descend. This would add some new features to the problem, as ascending blocks can contain several fixed points, whereas descending blocks can only contain one.

Problem 9.4 Given a composition a, find the number of derangements that ascend within the blocks.

References

[1] Robin Chapman and Lauren K. Williams. A conjecture of Stanley on alternating permutations. The Electronic Journal of Combinatorics, 14:#N16, 2007.

[2] Chak-On Chow. On the Eulerian enumeration of involutions. The Electronic Journal of Combinatorics, 15:#R71, 2008.

[3] Robert J. Clarke, Guo-Niu Han, and Jiang Zeng. A combinatorial interpretation of seidel generation of q-derangement numbers. Annals of Combinatorics, 4:313-327, 1997.

[4] Sylvie Corteel, Ira M. Gessel, Carla D. Savage, and Herbert S. Wilf. The joint distribution of descent and major index over restricted sets of permutations. Annals of Combinatorics. to appear.

[5] Dominique Dumont and Arthur Randrianarivony. Derangements et nombres de Genocchi. Discrete Mathematics, 132:37-49, 1994.

[6] Jacques Desarmenien and Michelle L. Wachs. Descent classes of permutations with a given number of fixed points. Journal of Combinatorial Theory, Series A, 64:311-328, 1993.

[7] Niklas Eriksen, Ragnar Freij, and Johan Wastlund. Enumeration of derangements with descents in prescribed positions. The Electronic Journal of Combinatorics, 16:#R32, 2009.

[8] Ira M. Gessel and Christophe Reutenauer. Counting permutations with given cycle structure and descent sets. Journal of Combinatorial Theory, Series A, 64:189-215, 1993.

[9] Guo-Niu Han and Guoce Xin. Permutations with extremal number of fixed points. Journal of Combinatorial Theory, Series A, 116:449-459, 2009.

[10] Fanja Rakotondrajao. k-fixed-points-permutations. INTEGERS: Electronic Journal of Combinatorial Number Theory, 7:#A36, 2007.

[11] Richard Stanley. Alternating permutations and symmetric functions. Journal of Combinatorial Theory, Series A, 114:436-460, 2006.

Niklas Eriksen, Ragnar Freij and Johan Wastlund

Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg, S-412 96 Goteborg, Sweden
COPYRIGHT 2009 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Eriksen, Niklas; Freij, Ragnar; Wastlund, Johan
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUSW
Date:Jan 1, 2009
Words:5531
Previous Article:Median clouds and a fast transposition median solver.
Next Article:Bisections between noncrossing and nonnesting partitions for classical reflection groups.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |