Lecture Hall Partitions

We prove a finite version of the well-known theorem that says that the number of partitions of an integer N into distinct parts is equal to the number of partitions of N into odd parts. Our version says that the number of lecture hall partitions of length n of N equals the number of partitions of N into small odd parts: 1,3,5, ldots, 2n-1 . We give two proofs: one via Bott's formula for the Poincaré series of the affine Coxeter group , and one direct proof.     

Lecture Hall Partitions II

For a non-decreasing integer sequence a=(a₁,...,a_n) we define L_a to be the set of n-tuples of integers = (₁,...,_n) satisfying . This generalizes the so-called lecture hall partitions corresponding to a_i=i and previously studied by the authors and by Andrews. We find sequences a such that the weight generating function for these a-lecture hall partitions has the remarkable form In the limit when n tends to infinity, we obtain a family of identities of the kind the number of partitions of an integer m such that the quotient between consecutive parts is greater than is equal to the number of partitions of m into parts belonging to the set P, for certain real numbers and integer sets P. We then underline the connection between lecture hall partitions and Ehrhart theory and discuss some reciprocity results.     

A Note on Partitions into Distinct Parts and Odd Parts

Bousquet-Mélou and Eriksson showed that the number of partitions of n into distinct parts whose alternating sum is k is equal to the number of partitions of n into k odd parts, which is a refinement of a well-known result by Euler. We give a different graphical interpretation of the bijection by Sylvester on partitions into distinct parts and partitions into odd parts, and show that the bijection implies the above statement.     

Partitions and Compositions Defined by Inequalities

We consider sequences of integers (₁,..., _k) defined by a system of linear inequalities _{i j>i}a_ijj with integer coefficients. We show that when the constraints are strong enough to guarantee that all _i are nonnegative, the generating function for the integer solutions of weight n has a finite product form , where the b_i are positive integers that can be computed from the coefficients of the inequalities. The results are proved bijectively and are used to give several examples of interesting identities for integer partitions and compositions. The method can be adapted to accommodate equalities along with inequalities and can be used to obtain multivariate forms of the generating function. We show how to extend the technique to obtain the generating function when the coefficients a_i,i+1 are allowed to be rational, generalizing the case of lecture hall partitions. Our initial results were conjectured thanks to the Omega package (G.E. Andrews, P. Paule, and A. Riese, European J. Comb. 22(7) (2001), 887–904).Research supported by NSA grants MDA 904-00-1-0059 and MDA 904-01-0-0083.     

关于整数集分拆的一个猜测的证明

设n为正整数,记rn=m ax{正整数m:可将集合{1,2,…,m}分为n个子集,使得在每一子集中方程xy=z(x>1,y>1)均无解}.高楠和刘红艳(数学的实践与认识,2005,35(5):151—152)给出了rn的一个下界估计rn n9,并猜测对任意给定的正整数k,当n充分大时有rn nk.本文对此猜测给以肯定回答,并证明了如下更强的结论:对任意给定的正整数k 4,当n>3k时有rn n2k+1.     

On a Problem of Lehmer on Partitions into Squares

In 1948, D.H.Lehmer published a brief work discussing the difference between representations of the integer n as a sum of squares and partitions of n into square summands. In this article, we return to this topic and consider four partition functions involving square parts and prove various arithmetic properties of these functions. These results provide a natural extension to the work of Lehmer.     

On the Postprojective Partitions and Components of the Auslander-Reiten Quivers

In this article, we shall investigate further the connections between the postprojective partition of an algebra and its Auslander–Reiten quiver.     

Jean-Louis Nicolas and the Partitions

A survey of Jean-Louis Nicolas’s papers on partitions is given.Dedicated to Jean-Louis Nicolas on the occasion of his 60th birthdayPartially supported by the Hungarian National Foundation for Scientific Research, Grant No. T 029759.2000 Mathematics Subject Classification: Primary—11P81     

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     

乘法分拆的计数函数的估值

设f(n)表示自然数n的乘法分拆数。对于所有奇数，较大地改进了n的系数，证明了：若n为奇数，则f(n)≤n/15 7/5。     

Arithmetic Properties of Summands of Partitions

Let d d, d2 2. We prove that for almost all partitions of an integer the parts are well distributed in residue classes mod d. The limitations of the uniformity of this distribution are also studied.     

An Application of Polya's Enumeration Theorem to Partitions of Subsets of Positive Integers

Let S be a non-empty subset of positive integers. A partition of a positive integer n into S is a finite nondecreasing sequence of positive integers a ₁, a ₂,...,a _r in S with repetitions allowed such that . Here we apply Polya's enumeration theorem to find the number P(n; S) of partitions of n into S, and the number DP(n; S) of distinct partitions of n into S. We also present recursive formulas for computing P(n; S) and DP(n; S).     

Cylindric Partitions

A new object is introduced into the theory of partitions that generalizes plane partitions: cylindric partitions. We obtain the generating function for cylindric partitions of a given shape that satisfy certain row bounds as a sum of determinants of -binomial coefficients. In some special cases these determinants can be evaluated. Extending an idea of Burge (J. Combin. Theory Ser. A 63 (1993), 210-222), we count cylindric partitions in two different ways to obtain several known and new summation and transformation formulas for basic hypergeometric series for the affine root system . In particular, we provide new and elementary proofs for two basic hypergeometric summation formulas of Milne (Discrete Math. 99 (1992), 199-246).

     

Arithmetic Properties of Summands of Partitions II

Let d∈ℕ, d ≥ 2. We prove that a positive proportion of partitions of an integer n satisfies the following : for all 1≤ a < b≤ d, the number of the parts congruent to a (mod d) is greater than the number of the parts congruent to b (mod d). We also show that for almost all partitions the rate of the number of square free parts is . 2000 Mathematics Subject Classification: Primary—11P82     

Partitions of finite vector spaces into subspaces

Let V_n(q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V_n(q) is a partition of V_n(q) if every nonzero element of V_n(q) is contained in exactly one element of . Suppose there exists a partition of V_n(q) into x_i subspaces of dimension n_i, 1 ≤ i ≤ k. Then x₁, …, x_k satisfy the Diophantine equation . However, not every solution of the Diophantine equation corresponds to a partition of V_n(q). In this article, we show that there exists a partition of V_n(2) into x subspaces of dimension 3 and y subspaces of dimension 2 if and only if 7x + 3y = 2ⁿ ? 1 and y ≠ 1. In doing so, we introduce techniques useful in constructing further partitions. We also show that partitions of V_n(q) induce uniformly resolvable designs on qⁿ points. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 329–341, 2008     

Equitable Partitions of Flat Association Schemes

Let (X, G) be an association scheme. We say that (X, G) is flat if it is homogeneous and if any two distinct points have at most one common g-neighbor for each g ∈ G. In this paper we prove that any nondiscrete equitable partition of (X, G) has at most one singleton if (X, G) is flat, and {X} is the unique equitable partition without any singleton if (X, G) is flat and |X| is a prime. This work was supported for two years by Korea Research Foundation Grant (KRF-2006-003-C00010) and Pusan National University Research Grant. Received: January 31, 2007. Final version received: Novmeber 14, 2007.     

Popularity of Sets Represented by the Partitions of n

Let us say that a partition of the positive integer n represents a, 0 a n, if there is a submultiset of the multiset of the parts whose sum is a. Erd os and Szalay have proved that almost all partitions of n represent all integers a, 0 a n. If is a finite set of positive integers, let us denote by p~(n, ) the number of partitions of n which represent all integers a, 0 a n, a , n – a but do not represent a for a . For instance, p~(n,) is the number of partitions of n which represent all integers between 0 and n; the result of Erd os and Szalay can be reformulated as p~(n,) p(n), where p(n) is the total number of partitions of n. The aim of this paper is the study of p~(n, ): we shall compare the values of p~(n, ) for small sets and we shall give a close formula for p~(n, ) when is the set of the first k integers.     

关于乘法分拆数的一个猜想和上界

本文证明了乘法分拆数的一个上界,由此证明了Hughes-Shallit的第二猜想,同时证明了对任意的正数a,存在一个自然数N,当n≥N时,n的乘法分拆数f(n)0,使这个集合中的自然数的乘法分拆数≤n~a。     

On the Maximal Multiplicity of Parts in a Random Integer Partition

We study the asymptotic behavior of the maximal multiplicity μ_n = μ_n(λ) of the parts in a partition λ of the positive integer n, assuming that λ is chosen uniformly at random from the set of all such partitions. We prove that πμ_n/(6n)^1/2 converges weakly to max _jX_j/j as n→∞, where X₁, X₂, … are independent and exponentially distributed random variables with common mean equal to 1.2000 Mathematics Subject Classification: Primary—05A17; Secondary—11P82, 60C05, 60F05