Partitions weighted by the parity of the crank

The ‘crank’ is a partition statistic which originally arose to give combinatorial interpretations for Ramanujan's famous partition congruences. In this paper, we establish an asymptotic formula and a family of Ramanujan type congruences satisfied by the number of partitions of n with even crank Me(n) minus the number of partitions of n with odd crank Mo(n). We also discuss the combinatorial implications of q-series identities involving Me(n)−Mo(n). Finally, we determine the exact values of Me(n)−Mo(n) in the case of partitions into distinct parts. These values are at most two, and zero for infinitely many n.     

On the largest prime factor of the partition function of n

Let p(n) be the function that counts the number of partitions of n. For a positive integer m, let P(m) be the largest prime factor of m. Here, we show that P(p(n)) tends to infinity when n tends to infinity through some set of asymptotic density 1. In fact, we show that the inequality P(p(n))>loglogloglogloglogn holds for almost all positive integers n. Features of the proof are the first term in Rademacher??s formula for p(n), Gowers?? effective version of Szemerédi??s theorem, and a classical lower bound for a nonzero homogeneous linear form in logarithms of algebraic numbers due to Matveev.     

A generalization of the symmetry between complete and elementary symmetric functions

A generalization for the symmetry between complete symmetric functions and elementary symmetric functions is given. As corollaries we derive the inverse of a triangular Toeplitz matrix and the expression of the Toeplitz-Hessenberg determinant. A very large variety of identities involving integer partitions and multinomial coefficients can be generated using this generalization. The partitioned binomial theorem and a new formula for the partition function p(n) are obtained in this way.     

On a problem of rota

Let S(n, k) denote Stirling numbers of the second kind; for each n, let K_n be such that S(n, K_n) ? S(n, k) for all k. Also, let P(n) denote the lattice of partitions of an n-element set. Say that a collection of partitions from P(n) is incomparable if no two are related by refinement. Rota has asked if for all n, the largest possible incomparable collection in P(n) contains S(n, K_n) partitions. In this paper, we construct for all n sufficiently large an incomparable collection in P(n) containing strictly more than S(n, K_n) partitions. We also estimate how large n must be for this construction to work.     

Complete description of invariant Einstein metrics on the generalized flag manifold SO(2n)/U(p)?× U(n ? p)

We find the precise number of non-K?hler SO(2n)-invariant Einstein metrics on the generalized flag manifold M = SO(2n)/U(p)×U(n−p) with n ≥ 4 and 2 ≤ p ≤ n−2. We use an analysis on parametric systems of polynomial equations and we give some insight towards the study of such systems. We also examine the isometric problem for these Einstein metrics.     

On representations by determinants of P(n) and Pm(n)

P(n) and P_m(n) denote the number of (unordered) partitions of n and the number of partitions of n into m parts, respectively. For P(n), there exists a recursion formula which is shown in Eq. (3) and a complicated formula indicated in J. L. Doob et al. (“Hans Rademacher: Topic Analytic Number Theory,” Springer-Verlag, Berlin/New York, 1973, p. 275, which is accompanied with the error term. For P_m(n), there is no general rule known covering all m (Doob et al., p. 222). In this article, P(n) and P_m(n) are represented by determinants. Note that the determinant of the former agrees with the above recursion formula and the finite product of binomials analogous to Euler identity, which is indicated in (5), leads to the representation of the latter. The computation of determinant is a little troublesome, but it is very important that the representations themselves of the number of partitions are simple, if we make use of the determinant.     

The p-Regular Partition Function Modulo p

Let b_?(n) denote the number of ?-regular partitions of n, where ? is a positive power of a prime p. We study in this paper the behavior of b_?(n) modulo powers of p. In particular, we prove that for every positive integer j, b_?(n) lies in each residue class modulo p^j for infinitely many values of n.     

Generating effective symmetry-breaking predicates for search problems

Consider the problem of testing for existence of an n-node graph G satisfying some condition P, expressed as a Boolean constraint among the n×n Boolean entries of the adjacency matrix M. This problem reduces to satisfiability of P(M). If P is preserved by isomorphism, P(M) is satisfiable iff P(M)∧SB(M) is satisfiable, where SB(M) is a symmetry-breaking predicate—a predicate satisfied by at least one matrix M in each isomorphism class. P(M)∧SB(M) is more constrained than P(M), so it is solved faster by backtracking than P(M)—especially if SB(M) rules out most matrices in each isomorphism class. This method, proposed by Crawford et al., applies not just to graphs but to testing existence of a combinatorial object satisfying any property that respects isomorphism, as long as the property can be compactly specified as a Boolean constraint on the object's binary representation.We present methods for generating symmetry-breaking predicates for several classes of combinatorial objects: acyclic digraphs, permutations, functions, and arbitrary-arity relations (direct products). We define a uniform optimality measure for symmetry-breaking predicates, and evaluate our constraints according to this measure. Results indicate that these constraints are either optimal or near-optimal for their respective classes of objects.     

The crank of partitions mod 13

Let M(r,m,n) be the number of unrestricted partitions of n with crank congruent to r modulo m. Here the relations between the numbers M(r,13,13n+k) when 0≤r<13 are given. All of the results are proved by elementary methods.     

A method of constructing Krall's polynomials

We propose a method of constructing orthogonal polynomials P_n(x) (Krall's polynomials) that are eigenfunctions of higher-order differential operators. Using this method we show that recurrence coefficients of Krall's polynomials P_n(x) are rational functions of n. Let P_n^(a,b;M)(x) be polynomials obtained from the Jacobi polynomials P_n^(a,b)(x) by the following procedure. We add an arbitrary concentrated mass M at the endpoint of the orthogonality interval with respect to the weight function of the ordinary Jacobi polynomials. We find necessary conditions for the parameters a,b in order for the polynomials P_n^(a,b;M)(x) to obey a higher-order differential equation. The main result of the paper is the following. Let a be a positive integer and b⩾−1/2 an arbitrary real parameter. Then the polynomials P_n^(a,b;M)(x) are Krall's polynomials satisfying a differential equation of order 2a+4.     

Periodicities of partition functions and stirling numbers modulo p

If p(n, k) is the number of partitions of n into parts ≤k, then the sequence {p(k, k), p(k + 1, k),…} is periodic modulo a prime p. We find the minimum period Q = Q(k, p) of this sequence. More generally, we find the minimum period, modulo p, of {p(n; T)}_{n ≥ 0}, the number of partitions of n whose parts all lie in a fixed finite set T of positive integers. We find the minimum period, modulo p, of {S(k, k), S(k + 1, k),…}, where these are the Stirling numbers of the second kind. Some related congruences are proved. The methods involve the use of cyclotomic polynomials over Z_p[x].     

Infinite families of infinite families of congruences for k-regular partitions

Let k∈{10,15,20}, and let b _k (n) denote the number k-regular partitions of n. We prove for half of all primes p and any t≥1 that there exist p?1 arithmetic progressions modulo p ^2t such that b _k (n) is a multiple of 5 for each n in one of these progressions.     

Enumerating set partitions according to the number of descents of size d or more

Let P(n, k) denote the set of partitions of {1, 2, ..., n} having exactly k blocks. In this paper, we find the generating function which counts the members of P(n, k) according to the number of descents of size d or more, where d????1 is fixed. An explicit expression in terms of Stirling numbers of the second kind may be given for the total number of such descents in all the members of P(n, k). We also compute the generating function for the statistics recording the number of ascents of size d or more and show that it has the same distribution on P(n, k) as the prior statistics for descents when d????2, by both algebraic and combinatorial arguments.     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

Total palindrome complexity of finite words

The palindrome complexity function pal_w of a word w attaches to each n∈N the number of palindromes (factors equal to their mirror images) of length n contained in w. The number of all the nonempty palindromes in a finite word is called the total palindrome complexity of that word. We present exact bounds for the total palindrome complexity and construct words which have any palindrome complexity between these bounds, for binary alphabets as well as for alphabets with the cardinal greater than 2. Denoting by M_q(n) the average number of palindromes in all words of length n over an alphabet with q letters, we present an upper bound for M_q(n) and prove that the limit of M_q(n)/n is 0. A more elaborate estimation leads to .     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

A Formula for the Partition Function That “Counts”

We derive a combinatorial multisum expression for the number D(n, k) of partitions of n with Durfee square of order k. An immediate corollary is therefore a combinatorial formula for p(n), the number of partitions of n. We then study D(n, k) as a quasipolynomial. We consider the natural polynomial approximation \({\tilde{D}(n, k)}\) to the quasipolynomial representation of D(n, k). Numerically, the sum \({\sum_{1\leq k \leq \sqrt{n}} \tilde{D}(n, k)}\) appears to be extremely close to the initial term of the Hardy-Ramanujan-Rademacher convergent series for p(n).     

Cells in any simple polygon formed by a planar point set

Let P be a finite point set in general position in the plane. We consider empty convex subsets of P such that the union of the subsets constitute a simple polygon S whose dual graph is a path, and every point in P is on the boundary of S. Denote the minimum number of the subsets in the simple polygons S's formed by P by f_p(P), and define the maximum value of f_p(P) by F_p(n) over all P with n points. We show that ⌈(4n-17)/15⌉?F_p(n)?⌊n/2⌋.     

A Hardy field extension of Szemerédi's theorem

In 1975 Szemerédi proved that a set of integers of positive upper density contains arbitrarily long arithmetic progressions. Bergelson and Leibman showed in 1996 that the common difference of the arithmetic progression can be a square, a cube, or more generally of the form p(n) where p(n) is any integer polynomial with zero constant term. We produce a variety of new results of this type related to sequences that are not polynomial. We show that the common difference of the progression in Szemerédi's theorem can be of the form [nδ] where δ is any positive real number and [x] denotes the integer part of x. More generally, the common difference can be of the form [a(n)] where a(x) is any function that is a member of a Hardy field and satisfies a(x)/xk→∞ and a(x)/xk+1→0 for some non-negative integer k. The proof combines a new structural result for Hardy sequences, techniques from ergodic theory, and some recent equidistribution results of sequences on nilmanifolds.     

Asymptotic estimates of sums involving the Moebius function

Let p(n) denote the smallest prime factor of an integer n>1 and let p(1)=∞. We study the asymptotic behavior of the sum M(x,y)=Σ_{1≤n≤x,p(n)>y}μ(n) and use this to estimate the size of A(x)=max_|f|≤1|Σ_2≤n<xμ(n)f(p(n))|, where μ(n) is the Moebius function. Applications of bounds for A(x), M(x,y) and similar quantities are discussed.