An S-restricted composition of a positive integer n is an ordered partition of n where each summand is drawn from a given subset S of positive integers. There are various problems regarding such compositions which have received attention in recent years. This paper is an attempt at finding a closed- form formula for the number of S-restricted compositions of n. To do so, we reduce the problem to finding solutions to corresponding so-called interpreters which are linear homogeneous recurrence relations with constant coefficients. Then, we reduce interpreters to Diophantine equations. Such equations are not in general solvable. Thus, we restrict our attention to those S-restricted composition problems whose interpreters have a small number of coefficients, thereby leading to solvable Diophantine equations. The formalism developed is then used to study the integer sequences related to some well-known cases of the S-restricted composition problem.
Many applied problems involve variants of the integer composition problem where different kinds of constraints are placed on the structure or parts of the composition. We briefly review earlier research on integer compositions with such constraints. As the first example, we can refer to those considering palindromic compositions which read the same from the left and the right @cite_45 . Another example is the problem of locally restricted compositions in which every @math successive parts meet particular constraints @cite_10 @cite_36 @cite_26 . Compositions whose parts are from a given set and successive parts of a given length avoid particular patterns are also investigated in the literature @cite_41 @cite_2 . The research on the same has also led to the generating functions that yield a closed-form solution to the problem in special cases @cite_22 . Generating functions have also been derived for the number of compositions where the swap of two parts of the composition is not relevant @cite_46 . Compositions avoiding some partially ordered patterns have also been studied @cite_14 . Partially ordered patterns define a partial order relation on parts of a composition.
@cite_26 @cite_14 @cite_22 @cite_36 @cite_41 @cite_45 @cite_2 @cite_46 @cite_10
2146489966 1968754505 2963986064 2020282424
We study compositions of the integer @math in which the first part, successive differences, and the last part are constrained to lie in prescribed sets @math , respectively. A simple condition on @math guarantees that the generating function @math has only a simple pole on its circle of convergence and this at @math , a function independent of @math and @math . Thus the number of compositions is asymptotic to @math for a suitable constant @math . We prove a multivariate central and local limit theorem and apply it to various statistics of random locally restricted compositions of @math , such as number of parts, numbers of parts of given sizes, and number of rises. The first and last parts are shown to have limiting distributions and to be asymptotically independent. If @math has only finitely many positive elements @math , or finitely many negative elements @math , then the largest part and number of distinct part sizes are almost surely @math . On the other hand, when both @math and @math have a positive asymptotic lower "local log-density", we prove that the largest part and number of distinct part sizes are almost surely @math , and we give sufficient conditions for the largest part to be almost surely asymptotic to @math . Stylistic composition is a creative musical activity, in which students as well as renowned composers write according to the style of another composer or period. We describe and evaluate two computational models of stylistic composition, called Racchman-Oct2010 (random constrained chain of Markovian nodes, October 2010) and Racchmaninof-Oct2010 (Racchman with inheritance of form). The former is a constrained Markov model, and the latter embeds this model in an analogy based design system. Racchmaninof-Oct2010 applies a pattern discovery algorithm called SIACT and a perceptually validated formula for rating pattern importance, to guide the generation of a new target design from an existing source design. A listening study is reported concerning human judgments of music excerpts that are, to varying degrees, in the style of mazurkas by Frederic Chopin (1810–1849). The listening study acts as an evaluation of the two computational models and a third, benchmark system, called Experiments in Musical Intelligence. Judges’ responses indicate that some aspects of musical style, such as phrasing and rhythm, are being modeled effectively by our algorithms. Judgments are also used to identify areas for future improvements. We discuss the broader implications of this work for the fields of engineering and design, where there is potential to make use of our models of hierarchical repetitive structure. We consider positive covering integer programs, which generalize set cover and which have attracted a long line of research developing (randomized) approximation algorithms. Srinivasan (2006) gave a rounding algorithm based on the FKG inequality for systems which are "column-sparse." This algorithm may return an integer solution in which the variables get assigned large (integral) values; Kolliopoulos & Young (2005) modified this algorithm to limit the solution size, at the cost of a worse approximation ratio. We develop a new rounding scheme based on the Partial Resampling variant of the Lovasz Local Lemma developed by Harris & Srinivasan (2013). This achieves an approximation ratio of 1 + ln([EQUATION]), where amin is the minimum covering constraint and Δ1 is the maximum e1-norm of any column of the covering matrix (whose entries are scaled to lie in [0, 1]); we also show nearly-matching inapproximability and integrality-gap lower bounds. Our approach improves asymptotically, in several different ways, over known results. First, it replaces Δ0, the maximum number of nonzeroes in any column (from the result of Srinivasan) by Δ1 which is always - and can be much - smaller than Δ0; this is the first such result in this context. Second, our algorithm automatically handles multi-criteria programs; we achieve improved approximation ratios compared to the algorithm of Srinivasan, and give, for the first time when the number of objective functions is large, polynomial-time algorithms with good multi-criteria approximations. We also significantly improve upon the upper-bounds of Kolliopoulos & Young when the integer variables are required to be within (1 + e) of some given upper-bounds, and show nearly-matching inapproximability. Abstract We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax − by ⩽ z + c , where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U . The solution is obtained from a minimum cut on a graph with O( nU ) nodes and O( mU ) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions. Nonmonotone integer programs are optimization problems with constraints of the type ax + by ⩽ z + c without restriction on the signs of a and b . Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe. The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover. Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality.