Reviews of of Rodica Simion's Papers from MathSciNet

                                      

5.
     _________________________________________________________________
   
   98b:52010 52A38 (05A10 60D05)
   Schmidt, Frank(1-GWU); Simion, Rodica(1-GWU)
   Some geometric probability problems involving the Eulerian numbers.
   (English. English summary)
   The Wilf Festschrift (Philadelphia, PA, 1996).
   Electron. J. Combin. 4 (1997), no. 2, Research Paper 18, approx. 13
   pp. (electronic). [ORIGINAL ARTICLE] 
     _________________________________________________________________
   
   The authors deal with a set of probability problems that lead to the
   computation of volumes of regions obtained by dissecting a polytope
   $P$ with hyperplanes. They consider in particular the case where $P$
   is an $n$-dimensional simplex or an $n$-dimensional cube. For
   instance, the regions formed by dissecting a simplex by certain
   pencils of hyperplanes through a point have volumes proportional to
   the Eulerian numbers $A(m,j)$ = the number of permutations of
   $\{1,2,{\cdots},m\}$ having exactly $j$ descents. The corresponding
   areas of the cross sections are also shown to be proportional to the
   Eulerian numbers. This result is used to derive an expression for
   partial sums of Eulerian numbers. The case of a cube cut perpendicular
   to a main diagonal by equally spaced parallel hyperplanes leads to
   Eulerian numbers and also to Eulerian numbers associated with signed
   permutations. The form of the expressions for the volumes suggests
   that each region can itself be partitioned into images of simplices
   under a measure-preserving transformation, where the simplices have
   equal volume and their number is the Eulerian number corresponding to
   that region. Adapting an idea of R. Stanley, the authors construct
   such transformations. The last section of the paper lists a variety of
   open problems and avenues for further investigation.
   

6.
     _________________________________________________________________
   
   98b:33038 33D45 (05A15 05A30 05E35)
   Simion, R.(1-GWU); Stanton, D.(1-MN-SM)
   Octabasic Laguerre polynomials and permutation statistics. (English.
   English summary)
   J. Comput. Appl. Math. 68 (1996), no. 1-2, 297--329. [To journal home
   page] 
     _________________________________________________________________
   
   In view of P. Flajolet's combinatorial theory of continued fractions
   [Discrete Math. 41 (1982), no. 2, 145--153; MR 84f:05005], the
   bijection found by J. Francon and G. Viennot [Discrete Math. 28
   (1979), no. 1, 21--35; MR 81a:05002] can be considered as a
   combinatorial proof of the simple fact that the $n$th moment for the
   Laguerre polynomials is $n!$, the number of the permutations on $\{1,
   2,\cdots, n\}$. Based on the above two papers, Viennot later
   established his combinatorial theory of orthogonal polynomials [in
   Orthogonal polynomials and applications (Bar-le-Duc, 1984), 139--157,
   Lecture Notes in Math., 1171, Springer, Berlin, 1985; MR 87g:42046].
   In a previous paper [SIAM J. Math. Anal. 25 (1994), no. 2, 712--719;
   MR 94m:05013], the authors of the paper under review noted that the
   bijection of Francon-Viennot keeps track of eight independent
   statistics of each permutation in $S\sb n$, which leads to a set of
   orthogonal polynomials with independent "$q$'s" which generalizes the
   Laguerre polynomials. In other words, the moments of the measure for
   these polynomials are generating functions for permutations according
   to eight different statistics.
   
   In the paper under review, the authors find eight different statistics
   on permutations whose generating function is the same as the above one
   by applying a recent bijection of P. Biane [European J. Combin. 14
   (1993), no. 4, 277--284; MR 95b:05019]. Specializing these statistics
   gives many other well-known sets of combinatorial objects and relevant
   statistics. The specializations are studied, with applications to
   classical orthogonal polynomials and equidistribution theorems for
   statistics.
   
   Note that D. C. Foata and D. Zeilberger [Stud. Appl. Math. 83 (1990),
   no. 1, 31--59; MR 91h:05016] also gave a bijection similar to that of
   Biane. Their relations to the bijection of Francon-Viennot have been
   recently found by R. J. Clarke, E. Steingrimsson and the reviewer
   [Adv. in Appl. Math. 18 (1997), no. 3, 237--270; MR 97m:05008].
   
                           Reviewed by Jiang Zeng
                                      
   Cited in: 99g:05190

7.
     _________________________________________________________________
   
   97h:06011 06A08 (05A30 05E25)
   Simion, Rodica(1-GWU)
   On $q$-analogues of partially ordered sets. (English. English summary)
   J. Combin. Theory Ser. A 72 (1995), no. 1, 135--183. [To journal home
   page] 
     _________________________________________________________________
   
   Summary: "We define the notion of an $f$-$q$-analogue of a poset $P$,
   where $f$ is a function in the incidence algebra of $P$. In this
   settting, for given $f$ and $q$, all $f$-$q$-analogues have the same
   zeta and characteristic polynomials, and the same Mobius invariants
   for rank selections. These are $q$-analogues of the corresponding
   entities for the poset $P$. We describe conditions under which $P$
   being shellable implies that its $f$-$q$-analogues are also shellable.
   In such situations, the analogues admit a shelling pulled back in a
   natural way from one of $P$, revealing a natural projection from the
   homology of analogues to that of $P$. As a by-product we obtain the
   non-negativity of the coefficients of the Betti polynomial for the
   analogues and their rank-selected subposets. We discuss the behavior
   of $f$-$q$ analogues with respect to several operations on the
   function $f$, the value $q$ and the poset $P$. Examples include posets
   of set partitions, posets of shuffles, semimodular and distributive
   lattices, and products of chains in particular. This work is an
   attempt to unify recent approaches to order analogues, and integrates
   cases studied by L. M. Butler [Adv. Math. 121 (1996), no. 1, 62--79;
   MR 97h:06006; MR 97h:06006], A. Bjorner [in Matroid applications,
   226--283, Cambridge Univ. Press, Cambridge, 1992; MR 94a:52030], R. P.
   Stanley [Enumerative combinatorics. Vol. I, Wadsworth & Brooks/Cole
   Adv. Books Software, Monterey, CA, 1986; MR 87j:05003], and C. D.
   Bennett, K. J. Dempsey and B. E. Sagan [J. Algebraic Combin. 3 (1994),
   no. 3, 261--283; MR 95h:05014]."
   


10.   
   96e:05010 05A15
   Denise, Alain(F-BORD-LB); Simion, Rodica(1-GWU)
   Two combinatorial statistics on Dyck paths. (English. English summary)
   Discrete Math. 137 (1995), no. 1-3, 155--176. [To journal home page] 
     _________________________________________________________________
   
   A Dyck path is one that starts at the origin, takes steps $x=(1,1)$ or
   $\overline x=(1,-1)$, never goes below the $x$-axis and ends on the
   $x$-axis. In this paper generating functions are found for Dyck paths
   of prescribed pyramid weight and (dually) of prescribed number of
   exterior pairs. A pyramid of height $h$ is a factor of a Dyck word of
   the form $x\sp h\overline x\sp h$ and the pyramid weight of a Dyck
   path $p$ is the sum of the heights of all maximal pyramids contained
   in the path. We denote the pyramid weight $P(p)$.
   
   The major result in this paper is that if $F(q,t)\coloneq\sum\sb {p\in
   D}q\sp {P(p)}t\sp {l(p)}$ then $$F(q,t)={1+t-2qt-\sqrt{(1-4t)(1-qt)\sp
   2+t(1-q)(2+t-3qt)}\over2t(1-qt)}$$ where $l(p)$ is the length of $p$
   and $D$ is the set of all Dyck paths. Note that when $q=1$ the Catalan
   numbers resurface.
   
   First the authors give a proof by generating functions using the DSV
   method. Enough explanation and examples are given to make this
   self-contained. Then an elaborate but direct combinatorial proof is
   provided using noncrossing partitions and "filler" points.
   
                         Reviewed by Louis Shapiro
                                      

11.
   
   95f:05012 05A18 (06A07 06B99)
   Edelman, Paul H.(1-MN); Simion, Rodica(1-GWU)
   Chains in the lattice of noncrossing partitions. (English. English
   summary)
   Discrete Math. 126 (1994), no. 1-3, 107--119. [To journal home page] 
     _________________________________________________________________
   
   A partition of the set $\bold n=\{0,1,\cdots,n\}$ is called
   noncrossing if for every $aC(P)$, then $E(P)/C(P)\ge 3/2$.
   The author also characterizes those posets where equality holds.
   
                        Reviewed by Dean Sturtevant
                                      
25.
   
   [CURR_LIST] Item: 25 of 34 [FIRST_DOC] [PREV_DOC] [NEXT_DOC]
   [LAST_DOC] Go To Item: ____
   Retrieve this document in [PDF........] format.
     _________________________________________________________________
   
   88a:05006 05A05 (05A15)
   Simion, Rodica(1-SIL); Schmidt, Frank W.(1-SIL)
   Restricted permutations. 
   European J. Combin. 6 (1985), no. 4, 383--406. [To journal home page] 
     _________________________________________________________________
   
   Summary: "This paper is concerned with counting permutations which do
   not contain certain subsequences. The number of even and odd such
   permutations is found and the involutions among them are counted.
   Bijections are determined between sets of such permutations and other
   combinatorial objects. A discussion is given of lattices whose maximum
   length chains correspond to restricted permutations. The results in
   this paper complement previous work by Knuth, Lovasz, Rotem and
   Stanley."
     _________________________________________________________________
   
26.
   87h:68030 68P99
   Simion, Rodica(1-SIL); Wilf, Herbert S.(1-PA)
   The distribution of prefix overlap in consecutive dictionary entries. 
   SIAM J. Algebraic Discrete Methods 7 (1986), no. 3, 470--475.
     _________________________________________________________________
   
   Summary: "We consider the family $\Delta({m}; {\scr A})$ of all
   dictionaries, over an alphabet ${\scr A}$, that have given numbers
   $m\sb i$ of words of each length $i=1, 2,\cdots$. We find the
   probability distribution of the length of the maximal common prefix of
   two consecutive words in dictionaries ${\scr D}\in\Delta$, and the
   asymptotic behavior of the average length of those common prefixes. In
   the case of dictionaries of $D$ words, all of the same length, the
   size of the average prefix overlap is `near' $\log\sb AD$ $(A=\vert
   {\scr A}\vert )$."
   
27.
   
   87h:05026a 05A17 (20C30)
   Schmidt, Frank W.(1-SIL); Simion, Rodica(1-SIL)
   On a partition identity. 
   J. Combin. Theory Ser. A 36 (1984), no. 2, 249--252.
     _________________________________________________________________
   
   87h:05026b 05A17 (20C30)
   Schmidt, Frank W.(1-SIL); Simion, Rodica(1-SIL)
   Addendum to: "On a partition identity". 
   J. Combin. Theory Ser. A 40 (1985), no. 2, 456--458. [To journal home
   page] 
     _________________________________________________________________
   
   Two proofs are given, one combinatorial, the other by character
   theory, for the identity $$\prod\sb \lambda a(1)!a(2)!\cdots
   a(n)!=\prod\sb \lambda 1\sp {a(1)}2\sp {a(2)}\cdots n\sp {a(n)},$$
   where $\lambda$ ranges over all partitions $\lambda=(1\sp {a(1)}2\sp
   {a(2)}\cdots n\sp {a(n)})$ of $n$. The novelty lies in the
   character-theoretic proof. The two demonstrations yield a simple proof
   of the known formula, $\det\sp 2T(n)=(\prod\sb \lambda 1\sp {a(1)}2\sp
   {a(2)}\cdots n\sp {a(n)})\sp 2$, where $T(n)$ is the matrix formed by
   the character table of the symmetric group on $n$ elements. A
   sufficient condition is given so that the permanent of $T(n)$ is zero,
   along with a brief discussion of this problem.
   
   In the addendum it is shown that the sufficient condition for $T(n)$
   to be zero holds infinitely often. This condition is that $l(n)$ be
   odd, where $l(n)$ is the number of partitions of $n$ having an odd
   number of even summands. In addition the authors show that $l(n)$ is
   even infinitely often.
   
28.
   
   86f:05053 05C05 (05C70)
   Simion, Rodica(1-SIL)
   Trees with a $1$-factor: degree distribution. 
   Proceedings of the fifteenth Southeastern conference on combinatorics,
   graph theory and computing (Baton Rouge, La., 1984).
   Congr. Numer. 45 (1984), 147--159.
     _________________________________________________________________
   
   A matched tree is one with a 1-factor. A condition is given for a
   sequence to be realizable as the degree sequence of a matched tree.
   The number of labelled matched trees on $2n$ vertices is computed. If
   a vertex $x$ is chosen at random from a randomly selected labelled
   matched tree on $2n$ vertices, then the limit as $n\rightarrow\infty$
   of the probability that $x$ has degree $d$ is shown to be $(2d-1)/
   (2\sp d(d-1)!{\sqrt e}\,)$. Labelled matched trees on $2n$ vertices
   with a given number of endpoints are then counted, and for each $n$ it
   is shown that the resulting sequence of numbers is unimodal.
   
                      Reviewed by Charles H. C. Little

30.
     _________________________________________________________________
   
   85i:05022 05A17
   Simion, Rodica(1-SIL)
   The lattice automorphisms of the dominance ordering. 
   Discrete Math. 49 (1984), no. 1, 89--93. [To journal home page] 
     _________________________________________________________________
   
   The dominance ordering of partitions of $n$ is defined as follows. A
   partition $a$ dominates $b$ if, with both partitions written as
   sequences of integers in decreasing order, the partial sums of $a$ are
   at least as big as the corresponding partial sums of $b$. The author
   shows that for $n$ other than six and seven, this order has no
   nontrivial automorphisms. By a characterization of join irreducibles
   given by T. H. Brylawski [same journal 6 (1973), 201--219; MR 48
   #3752; MR errata, EA48], one can show that an automorphism must act
   trivially on these, from which the result follows.
   
                         Reviewed by D. J. Kleitman
                                      
31.
     _________________________________________________________________
   
   85f:05033 05B20 (15A15)
   Simion, Rodica(1-SIL); Schmidt, Frank W.(1-SIL)
   On $(+1,-1)$-matrices with vanishing permanent. 
   Discrete Math. 46 (1983), no. 1, 107--108. [To journal home page] 
     _________________________________________________________________
   
   Authors' summary: "We show that if $A$ is an $n\times n$ ($+1,
   -1)$-matrix and if $n=2\sp m-1$ for some positive integer $m$, then
   ${\rm per}(A)\ne0$. This partially answers a question raised by E.
   T.-H. Wang [Israel J. Math. 18 (1974), 353--361; MR 50 #13077]."
32.
     _________________________________________________________________
   
   85e:05015 05A17 (05A15 11B75)
   Simion, Rodica(1-SIL)
   A multi-indexed Sturm sequence of polynomials and unimodality of
   certain combinatorial sequences. 
   J. Combin. Theory Ser. A 36 (1984), no. 1, 15--22. [To journal home
   page] 
     _________________________________________________________________
   
   For any multiset ${n}$, the numbers ${\cal O}({n}, k)$ of
   decompositions of ${n}$ into exactly $k$ parts are considered. Here,
   ${\cal O}({0}, 0)=1$ and ${\cal O}({n}, 0)=0$ if ${n} \ne{0}$ by
   convention. The results ${\cal O}({n}, k)=\binom{N-1} {k-1}$ and
   ${\cal O}({n}, k)=k!S(N, k)$ for the cases ${n}=(N)$ and ${n}=(1,
   1,\cdots,1)$ with $\vert {n}\vert =N$, respectively, are well known.
   Here, the $S(N, k)$ are Stirling numbers of the second kind.
   
   With ${n}+e\sb j$ denoting the multiset obtained from ${n}$ by
   adjoining one (additional) copy of the $j$th type element, the
   recurrence relation $(n\sb j+1){\cal O}({n}+e\sb j; k)=(n\sb j+k)
   {\cal O}({n}, k)+k{\cal O} ({n}, k+1)$ is used to obtain a second
   recurrence relation, $(n\sb j+1)f\sb {{n}+e\sb j}(x)=(n\sb j+x)f\sb
   {{n}}(x)+x(x+1)f\sb {{n}}(x)$ involving the ordinary generating
   function $f\sb m(x)=\sum\sb {k\ge0}{\cal O} ({m}, k)x\sp k$ for the
   ${\cal O}({m}, k)$'s.
   
   This second relation, together with the result that the multiplicity
   of $-1$ as a root of $f\sb {{n}}(x)$ is $\max\sb i\{n\sb i-1\}$ for
   ${n}\ne0$, and Rolle's theorem, is then used to obtain the main result
   of the paper, which establishes that the polynomial $f\sb {{n}}(x)$
   has all its roots in the interval $[-1, 0]$, and that, furthermore,
   $f\sb {{n}}(x)$ and $f\sb {{n}+e\sb j}(x)$ have interlaced roots over
   the interval $(-1, 0)$.
   
   The strong logarithmic concavity of the following sequences of
   numbers, and hence their unimodality, for every multiset ${n}$, is a
   direct consequence of the main result: (i) the sequence $\{{\cal
   O}({n}, k)\} \sb k$; (ii) the sequence $\{a({n}, d)\}\sb d$, where
   (the generalized Eulerian number) $a({n}, d)$ denotes the number of
   permutations of $n$ that have precisely $d$ descents; (iii) the
   sequence $\{{\cal O}\sb s({n}, k)\}\sb k$, where ${\cal O}\sb s({n},
   k)$ is the number of decompositions of ${n}$ into $k$ sets; in
   particular, the sequence $\{S(n, k)\}\sb k$ of Stirling numbers of the
   second kind is strongly log-concave, and hence, unimodal; (iv) the
   sequence of decompositions of ${n}$ with certain restrictions on the
   parts.
   
                        Reviewed by Nguyen-Huu-Bong