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     

Successions in integer partitions

A partition of an integer n is a representation n=a ₁+a ₂+⋅⋅⋅+a _k , with integer parts 1≤a ₁≤a ₂≤…≤a _k . For any fixed positive integer p, a p-succession in a partition is defined to be a pair of adjacent parts such that a _i+1−a _i =p. We find generating functions for the number of partitions of n with no p-successions, as well as for the total number of such successions taken over all partitions of n. In the process, various interesting partition identities are derived. In addition, the Hardy-Ramanujan asymptotic formula for the number of partitions is used to obtain an asymptotic estimate for the average number of p-successions in the partitions of n. This material is based upon work supported by the National Research Foundation under grant number 2053740.     

Disagreement point axioms and the egalitarian bargaining solution

We provide new characterizations of the egalitarian bargaining solution on the class of strictly comprehensive n-person bargaining problems. The main axioms used in all of our results are Nash’s IIA and disagreement point monotonicity—an axiom which requires a player’s payoff to strictly increase in his disagreement payoff. For n = 2 these axioms, together with other standard requirements, uniquely characterize the egalitarian solution. For n > 2 we provide two extensions of our 2-person result, each of which is obtained by imposing an additional axiom on the solution. Dropping the axiom of anonymity, strengthening disagreement point monotonicity by requiring player i’s payoff to be a strictly decreasing function of the disagreement payoff of every other player j ≠ i, and adding a “weak convexity” axiom regarding changes of the disagreement point, we obtain a characterization of the class of weighted egalitarian solutions. This “weak convexity” axiom requires that a movement of the disagreement point in the direction of the solution point should not change the solution point. We also discuss the so-called “transfer paradox” and relate it to this axiom.     

Approximation Schemes for Functional Optimization Problems

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. Marcello Sanguineti was partially supported by a PRIN grant from the Italian Ministry for University and Research (project “Models and Algorithms for Robust Network Optimization”).     

Topology of spaces of hyperbolic polynomials and combinatorics of resonances

In this paper we study the topology of the strata, indexed by number partitions λ, in the natural stratification of the space of monic hyperbolic polynomials of degreen. We prove stabilization theorems for removing an independent block or an independent relation in λ. We also prove contractibility of the ‘one-point compactifications of the strata indexed by a large class of number partitions, including λ=(k ^m , 1 ^r ), form≥2. Furthermore, we study the maps between the homology groups of the strata, induced by imposing additional relations (resonances) on the number partition λ, or by merging some of the blocks of λ.     

Generalizations of Schur's partition theorem

Schur's partition theorem states that the number of partitions ofn into distinct parts ≡ 1,2 (mod 3) is equal to the number of partitions ofn into parts with minimal difference 3 and no consecutive multiples of 3. A three-parameter generalization of Gleissberg's refinement of Schur's theorem is obtained by showing that is equal to the numerator of a certain continued fraction. Two proofs are presented, one completely combinatorial, and one using generating functions. This article was processed by the author using the Springer-Verlag T_EX mamath macro package 1990.     

Analytic proof of the partition identity A 5,3,3(n)=B 5,3,3 0 (n)

In this paper we give an analytic proof of the identity A _5,3,3(n)=B _5,3,3⁰(n), where A _5,3,3(n) counts the number of partitions of n subject to certain restrictions on their parts, and B _5,3,3⁰(n) counts the number of partitions of n subject to certain other restrictions on their parts, both too long to be stated in the abstract. Our proof establishes actually a refinement of that partition identity. The original identity was first discovered by the first author jointly with M. Ruby Salestina and S.R. Sudarshan in [Proceedings of the International Conference on Analytic Number Theory with Special Emphasis on L-functions, Ramanujan Math. Soc., Mysore, 2005, pp. 57–70], where it was also given a combinatorial proof, thus answering a question of Andrews. Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe.”     

Tensor products and dimensions of simple modules for symmetric groups

LetK be an algebraically closed field of characteristic,p>0 and letD ^λ be the simple modules of the symmetric groupS _r overK where λ is a p-regular partition ofr. The dimensions ofD ^λ for λ with at mostn parts are the same as the multiplicities of direct summands ofD ^⊗r whereE is the natural module for the groupGL _n (K). Whenn=2 we determine generating functions for these multiplicities and hence for the dimensions ofD ^λ for all partitions λ with two parts. These can be expressed as rational functions of Chebyshev polynomials; and we obtain explicit formulae for the coefficients.     

Weighted Rogers–Ramanujan partitions and Dyson crank

In this paper, we refine a weighted partition identity of Alladi. We write formulas for generating functions for the number of partitions grouped with respect to a partition statistic other than the norm. We tie our weighted results as well as the different statistics with the crank of a partition. In particular, we prove that the number of partitions into even number of distinct parts whose odd-indexed parts’ sum is n is equal to the number of partitions of n with non-negative crank.     

Nilpotent Ranks of Semigroups of Partial Transformations

A subset U of a semigroup S is a generating set for S if every element of S may be written as a finite product of elements of U. The rank of a finite semigroup S is the size of a minimal generating set of S, and the nilpotent rank of S is the size of a minimal generating set of S consisting of nilpotents in S. A partition of a q-element subset of the set X_n = {1,2,..., n} is said to be of type τ if the sizes of its classes form the partition τ of the positive integer q ≤ n. A non-trivial partition τ of q consists of k < q elements. For a non-trivial partition τ of q < n, the semigroup S(τ), generated by all the transformations with kernels of type τ, is nilpotent-generated. We prove that if τ is a non-trivial partition of q < n, then the rank and the nilpotent rank of S(τ) are both equal to the number of partitions X_n of type τ.     

New series of weakly implicative selector sets

In this paper we specify classes of weakly implicative selector sets and describe their interconnections for the case when the number of variables n does exceed 3 (see A. N. Degtev and D. I. Ivanov, “Weakly Implicative Selector Sets of Dimension 3” Diskretn. Matem. 11 (3), 126–132 (1999)).     

The f(q) mock theta function conjecture and partition ranks

In 1944, Freeman Dyson initiated the study of ranks of integer partitions. Here we solve the classical problem of obtaining formulas for N_e(n) (resp. N_o(n)), the number of partitions of n with even (resp. odd) rank. Thanks to Rademacher’s celebrated formula for the partition function, this problem is equivalent to that of obtaining a formula for the coefficients of the mock theta function f(q), a problem with its own long history dating to Ramanujan’s last letter to Hardy. Little was known about this problem until Dragonette in 1952 obtained asymptotic results. In 1966, G.E. Andrews refined Dragonette’s results, and conjectured an exact formula for the coefficients of f(q). By constructing a weak Maass-Poincaré series whose “holomorphic part” is q^-1f(q²⁴), we prove the Andrews-Dragonette conjecture, and as a consequence obtain the desired formulas for N_e(n) and N_o(n). Mathematics Subject Classification (2000) 11P82, 05A17     

Signed words and permutations, IV: Fixed and pixed points

The flag-major index “fmaj” and the classical length function “ℓ” are used to construct two q-analogs of the generating polynomial for the hyperoctahedral group B _n by number of positive and negative fixed points (resp., pixed points). Specializations of those q-analogs are also derived dealing with signed derangements and desarrangements, as well as several classical results that were previously proved for the symmetric group. To Volker Strehl, a dedication à la Goethe, on the occasion of his sixtieth birthday.     

Adapted complex structures and the geodesic flow

In this paper, we give a new construction of the adapted complex structure on a neighborhood of the zero section in the tangent bundle of a compact, real-analytic Riemannian manifold. Motivated by the “complexifier” approach of T. Thiemann as well as certain formulas of V. Guillemin and M. Stenzel, we obtain the polarization associated to the adapted complex structure by applying the “imaginary-time geodesic flow” to the vertical polarization. Meanwhile, at the level of functions, we show that every holomorphic function is obtained from a function that is constant along the fibers by “composition with the imaginary-time geodesic flow.” We give several equivalent interpretations of this composition, including a convergent power series in the vector field generating the geodesic flow.     

Asymptotic formulas for some retricted partition functions

We use Rademacher’s method to obtain asymptotic expressions for some restricted partition functions. For fixed positive integers m > 1 and l, we consider the number p _m (n) of partitions of n into summands not divisible by m, and the number p _m ^l (n) of partitons of n with the further restriction that any integer occurs at most l times as a summand. 2000 Mathematics Subject Classification Primary—11P82; Secondary—11P83     

A Unified Approach to Algorithms Generating Unrestricted and Restricted Integer Compositions and Integer Partitions

An original algorithm is presented that generates both restricted integer compositions and restricted integer partitions that can be constrained simultaneously by (a) upper and lower bounds on the number of summands (“parts”) allowed, and (b) upper and lower bounds on the values of those parts. The algorithm can implement each constraint individually, or no constraints to generate unrestricted sets of integer compositions or partitions. The algorithm is recursive, based directly on very fundamental mathematical constructs, and given its generality, reasonably fast with good time complexity. A general, closed form solution to the open problem of counting the number of integer compositions doubly restricted in this manner also is presented; its formulaic link to an analogous solution for counting doubly-restricted integer partitions is shown to mirror the algorithmic link between these two objects.     

Quasi-symmetric functions and up–down compositions

Carlitz (1973) [5] and Rawlings (2000) [13] studied two different analogues of up–down permutations for compositions with parts in {1,…,n}. Cristea and Prodinger (2008/2009) [7] studied additional analogues for compositions with unbounded parts. We show that the results of Carlitz, Rawlings, and Cristea and Prodinger on up–down compositions are special cases of four different analogues of generalized Euler numbers for compositions. That is, for any s≥2, we consider classes of compositions that can be divided into an initial set of blocks of size s followed by a block of size j where 0≤j≤s−1. We then consider the classes of such compositions where all the blocks are strictly increasing (weakly increasing) and there are strict (weak) decreases between blocks. We show that the weight generating functions of such compositions w=w₁?w_m, where the weight of w is , are always the quotients of sums of quasi-symmetric functions. Moreover, we give a direct combinatorial proof of our results via simple involutions.     

Irreducible characters of the group S n that are semiproportional on A n

Previously, we dubbed the conjecture that the alternating group A_n has no semiproportional irreducible characters for any natural n [1]. This conjecture was then shown to be equivalent to the following [3]. Let α and β be partitions of a number n such that their corresponding characters χ^α and χ^β in the group S_n are semiproportional on A_n. Then one of the partitions α or β is self-associated. Here, we describe all pairs (α, β) of partitions satisfying the hypothesis and the conclusion of the latter conjecture. Supported by RFBR (grant No. 07-01-00148) and by RFBR-NSFC (grant No. 05-01-39000). __________ Translated from Algebra i Logika, Vol. 47, No. 2, pp. 135–156, March–April, 2008.     

q-Numbers of quantum groups, Fibonacci numbers, and orthogonal polynomials

We obtain algebraic relations (identities) for q-numbers that do not contain q ^α-factors. We derive a formula that expresses any q-number [x] in terms of the q-number [2]. We establish the relationship between the q-numbers [n] and the Fibonacci numbers, Chebyshev polynomials, and other special functions. The sums of combinations of q-numbers, in particular, the sums of their powers, are calculated. Linear and bilinear generating functions are found for “natural” q-numbers. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 8, pp. 1055–1063, August, 1998.