Generating Functions for Permutations Avoiding a Consecutive Pattern

Given a permutation τ of length j, we say that a permutation σ has a τ-match starting at position i, if the elements in positions i, i+1, . . . , i+j−1 in σ have the same relative order as the elements of τ. We have been able to take advantage of the results of Mendes and Remmel [1] to obtain a generating function for the number of permutations with no τ-matches for several new classes of permutations. These new classes include a large class of permutations which are shuffles of an increasing sequence 1 2 · · · n with an arbitrary permutation σ of the integers {n + 1, . . . , n + m}. Finally we give a formula for the generating function for the number of permutations which have no 1 3 2 4-matches.     

The Joint Distribution of Descent and Major Index over Restricted Sets of Permutations

We compute the joint distribution of descent and major index over permutations of {1,..., n} with no descents in positions {n − i, n − i + 1, ... , n − 1} for fixed i ≥ 0. This was motivated by the problem of enumerating symmetrically constrained compositions and generalizes Carlitz’s q-Eulerian polynomial. Received December 19, 2006     

Forest-Like Permutations

Given a permutation , construct a graph G _π on the vertex set {1, 2,..., n} by joining i to j if (i) i < j and π(i) < π(j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π(j). We say that π is forest-like if G _π is a forest. We first characterize forest-like permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties). We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which G _π is a tree, or a path, and recover the known generating function of smooth permutations. Received March 27, 2006     

Jagged Partitions

By jagged partitions we refer to an ordered collection of non-negative integers (n₁, n₂,..., n_m) with n_m≥ p for some positive integer p, further subject to some weakly decreasing conditions that prevent them for being genuine partitions. The case analyzed in greater detail here corresponds to p = 1 and the following conditions n_i≥ n_i+1−1 and n_i≥ n_i+2. A number of properties for the corresponding partition function are derived, including rather remarkable congruence relations. An interesting application of jagged partitions concerns the derivation of generating functions for enumerating partitions with special restrictions, a point that is illustrated with various examples. 2000 Mathematics Subject Classification: Primary—05A15, 05A17, 05A19     

A Five Color Zero-Sum Generalization

Let g_zs(m, 2k) (g_zs(m, 2k+1)) be the minimal integer such that for any coloring Δ of the integers from 1, . . . , g_zs(m, 2k) by (the integers from 1 to g_zs(m, 2k+1) by ) there exist integers such that 1. there exists j_x such that Δ(x_i) ∈ for each i and ∑_i=1^m Δ(x_i) = 0 mod m (or Δ(x_i)=∞ for each i); 2. there exists j_y such that Δ(y_i) ∈ for each i and ∑_i=1^m Δ(y_i) = 0 mod m (or Δ(y_i)=∞ for each i); and 1. 2(x_m−x₁)≤y_m−x₁. In this note we show g_zs(m, 2)=5m−4 for m≥2, g_zs(m, 3)=7m+−6 for m≥4, g_zs(m, 4)=10m−9 for m≥3, and g_zs(m, 5)=13m−2 for m≥2. Supported by NSF grant DMS 0097317     

The <Emphasis Type="Italic">f</Emphasis>-Vector of the Descent Polytope

For a positive integer n and a subset S⊆[n−1], the descent polytope DP  _S is the set of points (x ₁,…,x _n ) in the n-dimensional unit cube [0,1] ⁿ such that x _i ≥x _i+1 if i∈S and x _i ≤x _i+1 otherwise. First, we express the f-vector as a sum over all subsets of [n−1]. Second, we use certain factorizations of the associated word over a two-letter alphabet to describe the f-vector. We show that the f-vector is maximized when the set S is the alternating set {1,3,5,…}∩[n−1]. We derive a generating function for F _S (t), written as a formal power series in two non-commuting variables with coefficients in ℤ[t]. We also obtain the generating function for the Ehrhart polynomials of the descent polytopes.     

Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1 and <Emphasis Type="Italic">a</Emphasis><Subscript>1</Subscript> = 0 < <Emphasis Type="Italic">a</Emphasis><Subscript>2</Subscript>

Let Γ be a distance-regular graph of diameter d ≥ 3 with c ₂ > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:

Su una questione di statica proposta dal Malfatti

Riassunto Si considera un corpo pesante appoggiato inm punti ad un piano orizzontale; è noto che le equazioni cardinali della statica, salvo nel casom≤3, non sono sufficienti, in generale, per determinare le reazioni Φ_i (i=1, 2, …,m) degli appoggi. Valendosi di analogia col casom=3Malfatti (1731–1807) ha proposto formule [4] per Φ_i valide per ognim. Queste formule soddisfano l'equazione per il risultante, ma non sembra che Malfatti verifichi quella per il momento, verifica che non risulta immediata. In questa nota, scritte le formule di Malfatti in forma moderna, si osserva che esse si possono suddividere in due parti ε₁ ed ε₂ (ε₂ fino a 4 lati), e si dimostra che i termini di ε₁ soddisfano per ognim anche l'equazione dei momenti mentre, per i termini di ε₂ (meno intuitivi dal punto di vista fisico) si è limitata la verifica al caso del pentagono e dell'esagono. In sostanza, almeno considerando i corpi rigidi, si conferma la intuizione di Malfatti.

---

Summary We consider a heavy body leaned against a horizontal plane onm pointsA _i; it is known that the statics equations, except the casem≤3, are not sufficient in general to determine the reaction forces reazioni Φ_i(i=1,…,m) at pointsA _i. Generalizing the casem=3,Malfatti (1731–1807) have the formulas [4] to obtain ε_i for everym. He proves that these formulas verify the resultant equation, but he does not show clearly that the moment equation is fulfilled too. In this paper we write the Malfatti formulas in a modern form, and we observe that it is possible to decompose them in two parts ε₁ and ε₂ (ε₂ form→-4). Moreover we demonstrate that ε₁ satisfies also the moment equation for everym, while we show that ε_i is solution also of this equation when one consider the pentagon and hexagon cases.

---

---

Ricerca svolta con i fondi del M.P.I.—quota 40%. Gruppo di ricerca: Problemi di evoluzione nei solidi e nei fluidi.     

Generating-Tree Isomorphisms for Pattern-Avoiding Involutions

We show that for k ≥ 5 and the permutations τ _k = (k − 1)k(k − 2). . .312 and J _k = k(k − 1). . .21, the generating tree for involutions avoiding the pattern τ _k is isomorphic to the generating tree for involutions avoiding the pattern J _k . This implies a family of Wilf equivalences for pattern avoidance by involutions.     

Interpolation of rational functions by simple partial fractions

We study a generalized interpolation of a rational function at n nodes by a simple partial fraction of degree n and reduce the consideration to the solvability question for a special difference equation. We construct explicit interpolation formulas in the case where the equation order is equal to 1. We show that for functions A(x − a) ^m , m ? \mathbbN m \in \mathbb{N} , it is possible to reduce the consideration to a system of m + 1 independent first order equations and construct explicit interpolation formulas. Bibliography: 6 titles.     

Existence of singular solutions of a degenerate equation in R 2

Let a₁,a₂, . . . ,a_m ∈ ℝ², 2≤f ∈ C([0,∞)), g_i ∈ C([0,∞)) be such that 0≤g_i(t)≤2 on [0,∞) ∀i=1, . . . ,m. For any p>1, we prove the existence and uniqueness of solutions of the equation u_t=Δ(logu), u>0, in satisfying and logu(x,t)/log|x|→−f(t) as |x|→∞, logu(x,t)/log|x−a_i|→−g_i(t) as |x−a_i|→0, uniformly on every compact subset of (0,T) for any i=1, . . . ,m under a mild assumption on u₀ where We also obtain similar existence and uniqueness of solutions of the above equation in bounded smooth convex domains of ℝ² with prescribed singularities at a finite number of points in the domain.     

Refined enumerations of alternating sign matrices: monotone (<Emphasis Type="Italic">d</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-trapezoids with prescribed top and bottom row

Monotone triangles are plane integer arrays of triangular shape with certain monotonicity conditions along rows and diagonals. Their significance is mainly due to the fact that they correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the array. We define monotone (d,m)-trapezoids as monotone triangles with m rows where the d−1 top rows are removed. (These objects are also equivalent to certain partial alternating sign matrices.) It is known that the number of monotone triangles with bottom row (k ₁,…,k _n ) is given by a polynomial α(n;k ₁,…,k _n ) in the k _i ’s. The main purpose of this paper is to show that the number of monotone (d,m)-trapezoids with prescribed top and bottom row appears as a coefficient in the expansion of a specialisation of α(n;k ₁,…,k _n ) with respect to a certain polynomial basis. This settles a generalisation of a recent conjecture of Romik et al. (Adv. Math. 222:2004–2035, 2009). Among other things, the result is used to express the number of monotone triangles with bottom row (1,2,…,i−1,i+1,…,j−1,j+1,…,n) (which is, by the standard bijection, also the number of n×n alternating sign matrices with given top two rows) in terms of the number of n×n alternating sign matrices with prescribed top and bottom row, and, by a formula of Stroganov for the latter numbers, to provide an explicit formula for the first numbers. (A formula of this type was first derived by Karklinsky and Romik using the relation of alternating sign matrices to the six-vertex model.)     

The increase of sums and products dependent on (y 1, …,y n ) by rearrangement of this set

LetF(u, v) be a symmetric real function defined forα<u, v<β and assume thatG(u, v, w)=F(u, v)+F(u, w)−F(v, w) is decreasing inv andw foru≦min (u, v). For any set (y)=(y ₁, …,y _n ),α<y _i <β, given except in arrangement Σ _i ^=1/n F(y _i ,y _i+1) wherey _n+1=y ₁) is maximal if (and under some additional assumptions only if) (y) is arranged in circular symmetrical order. Examples are given and an additional result is proved on the productΠ _i ^=1/n [(y2i−1y2i) ^m +α ₁(y _2i−1 y _2i ) ^m−1+ … +a _m ] wherea _k ≧0 and where the set (y)=(y ₁, ..,y _n ),y _i ≧0 is given except in arrangement. The problems considered here arose in connection with a theorem by A. Lehman [1] and a lemma of Duffin and Schaeffer [2]. This paper is part of the author’s Master of Science dissertation at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Professor E. Jabotinsky for their help in the preparation of this paper.     

Smooth convex bodies with proportional projection functions

For a convex body K ⊂ ℝⁿ and i ∈ {1, …, n − 1}, the function assigning to any i-dimensional subspace L of ℝⁿ, the i-dimensional volume of the orthogonal projection of K to L, is called the i-th projection function of K. Let K, K ₀ ⊂ ℝⁿ be smooth convex bodies with boundaries of class C ² and positive Gauss-Kronecker curvature and assume K ₀ is centrally symmetric. Excluding two exceptional cases, (i, j) = (1, n − 1) and (i, j) = (n − 2, n − 1), we prove that K and K ₀ are homothetic if their i-th and j-th projection functions are proportional. When K ₀ is a Euclidean ball this shows that a convex body with C ² boundary and positive Gauss-Kronecker with constant i-th and j-th projection functions is a Euclidean ball. The second author was supported in part by the European Network PHD, FP6 Marie Curie Actions, RTN, Contract MCRN-511953.     

Large sample nonparametric rejection of outlying observations

1. Summary Letx ₁≦, ..., ≦x _n be independent observations from continuous populations. The null hypothesis,H ₀, is that these observations are a sample. The alternative hypothesis is that thei smallest observations are too small (or that thei largest observations are too large) to be consistent withH ₀. Herei is a small number and should be specified without knowledge of the observation values. The common population hypothesized for the null case is assumed to be well-behaved but no specific assumptions are made about its shape. The alternative that thei smallest observations are too small is accepted if a statistic of the formx _i−(1+A)x _i+1+Ax _k is negative, whereA>0,k is the largest integer contained ini+√2n, andn is sufficiently large. Similarly, the alternative that thei largest observations are too large is accepted ifx _n+1−i −(1+A)x _n−i+Ax _n+1−k is positive. Two-sided tests are obtained as combinations of these one-sided tests. ForA suitably chosen, an approximate upper bound for the significance level of a test is evaluated from Techebycheff’s inequality. Using this relation, the value ofA is expressed as a function ofi, n, and the significance level upper bound. For fixed population shapes, these tests have powers that tend to unity for the case wheren−i of the populations are the same and the minimum difference between the median of this common population and the medians of the other populations increases in the appropriate direction The results of this paper may be useful in population statistics, operations research, and other applied fields.     

Nonuniqueness ing-functions

We give an example of two distinct stationary processes {X _n} and {X′ _n} on {0, 1} for whichP[X₀=1|X₋₁=a₋₁,X₋₂=a₋₂, …]=P[X′₀=1|X′₋₁=a₋₁,X′₋₂=a₋₂, …] for all {a _i},i=−1, −2, …, even though these probabilities are bounded away from 0 and 1, and are continuous in {a _i}. Supported in part by NSF Grant DMS 89-01545. Supported in part by the US Army Research Office.     

On the Waiting Time for the First Success Run

Let k and m are positive integers with k ≥ m. The probability generating function of the waiting time for the first occurrence of consecutive k successes in a sequence of m-th order Markov dependent trials is given as a function of the conditional probability generating functions of the waiting time for the first occurrence of consecutive m successes. This provides an efficient algorithm for obtaining the probability generating function when k is large. In particular, in the case of independent trials a simple relationship between the geometric distribution of order k and the geometric distribution of order k−1 is obtained. This research was partially supported by the ISM Cooperative Research Program(2004-ISM-CRP-2006) and by a Grant-in-Aid for Scientific Research (C) of the JSPI (Grant Number 16500183)     

A Higman inequality for regular near polygons

The inequality of Higman for generalized quadrangles of order (s,t) with s>1 states that t≤s ². We generalize this by proving that the intersection number c _i of a regular near 2d-gon of order (s,t) with s>1 satisfies the tight bound c _i ≤(s ²ⁱ −1)/(s ²−1), and we give properties in case of equality. It is known that hemisystems in generalized quadrangles meeting the Higman bound induce strongly regular subgraphs. We also generalize this by proving that a similar subset in regular near 2d-gons meeting the bounds would induce a distance-regular graph with classical parameters (d,b,α,β)=(d,−q,−(q+1)/2,−((−q) ^d +1)/2) with q an odd prime power.     

Absolutely continuous invariant measures for piecewise expandingC 2 transformations inR N

LetS be a bounded region inR ^N and let ℊ={S _i} _i ^=1/m be a partition ofS into a finite number of subsets having piecewiseC ² boundaries. We assume that whereC ² segments of the boundaries meet, the angle subtended by tangents to these segments at the point of contact is bounded away from 0. Letτ:S →S be piecewiseC ² on ℊ and expanding in the sense that there exists 0<σ< 1 such that for anyi=1, 2, ...,m, ‖Dτ _i ⁻¹ ‖<σ, whereDτ _i ⁻¹ is the derivative matrix ofτ _i ⁻¹ and ‖ ‖ is the euclidean matrix norm. The main result provides an upper bound onσ which guarantees the existence of an absolutely continuous invariant measure forτ. The research of the second author was supported by NSERC and FCAR grants.     

The Existence and Uniqueness of Nash Equilibrium Point in an m-player Game “Shoot Later, Shoot First!”

We consider the following “silent duel” of m players with a possible economic interpretation. Each player has one “bullet”, which she can shoot at any time during the time interval [0,1]. The probability that the i-th player hits the “target” at moment t is given by an increasing accuracy function f _i (t). The winner is the player who hits the target first. Under natural assumptions on the functions f _i (t) we prove the existence and uniqueness of a Nash equilibrium point in this game, and we provide an explicit construction of this equilibrium. This construction allows us to obtain exact solutions for many specific examples. Some of them are presented.This work was partly supported by RBRF grants 03-01-00479.