A Partition-Based Generating Function for Row-Convex Polyominoes

• URL: http://arxiv.org/abs/2605.03203v1
• Date: Mon, 04 May 2026 22:46:19 GMT
• Title: A Partition-Based Generating Function for Row-Convex Polyominoes
• Abstract summary: An alternative generating function is proposed to enumerate polyominoes without internal holes on a grid.<n>Potential applications include shape priors in discrete image analysis, grid-based modeling, and generation of convex structures.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An alternative generating function is proposed to enumerate row-convex polyominoes without internal holes on a discrete grid. The approach is based on integer partitions of the total area, where each partition corresponds to a sequence of row lengths, and the product of all permutations of the parts accounts for all possible horizontal alignments of consecutive rows. Summing over the products yields a formula for the total number of convex polyominoes of a given size. Numerical examples are provided for small areas, and the exact generating function is derived via a transfer series argument, establishing the asymptotic growth S(N) as A2^(N) cos(N*theta) + phi) with theta = arctan(sqrt(7)/3). The method establishes a direct connection between integer partitions and polyomino enumeration, offering a simple yet effective framework for both exact and asymptotic combinatorial analysis. Potential applications include shape priors in discrete image analysis, grid-based modeling, and combinatorial generation of convex structures.

Related papers

• Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications [0.0]
  We establish closed-form enumeration formulas for feature vectors of 2-trees under the bichromatic triangle constraint.<n>These efficiently computable structural features derive from constrained graph colorings where each triangle uses exactly two colors.
  arXiv  Detail & Related papers  (2025-12-08T03:01:50Z)
• Smooth Integer Encoding via Integral Balance [0.0]
  We introduce a novel method for encoding using smooth real-valued functions.<n>Our approach encodes the number N in the set of natural numbers through the cumulative balance of a smooth function f_N(t)<n>The total integral I(N) converges to zero as N tends to infinity, and the integer can be recovered as the minimal point of near-cancellation.
  arXiv  Detail & Related papers  (2025-04-28T20:23:53Z)
• Exact Sequence Interpolation with Transformers [0.0]
  We prove that transformers can exactly interpolate datasets of finite input sequences in $mathbbRd$, $dgeq 2$, with corresponding output sequences of smaller or equal length.<n>Specifically, given $N$ sequences of arbitrary but finite lengths in $mathbbRd$ and output sequences of lengths $m1, dots, mN in mathcalN$, we construct a transformer with $mathcalO(sum_j=1N mj)$ blocks and $
  arXiv  Detail & Related papers  (2025-02-04T12:31:00Z)
• A Multiple Parameter Linear Scale-Space for one dimensional Signal Classification [0.0]
  We construct a maximal set of kernels for a multi- parameter linear scale-space that allow us to construct trees for classification and recognition of one-dimensional continuous signals. A number of useful properties of the maximal set of kernels are derived. A new topologically invariant method of constructing trees is introduced.
  arXiv  Detail & Related papers  (2023-05-22T17:14:45Z)
• Orthogonal Polynomials Approximation Algorithm (OPAA):a functional analytic approach to estimating probability densities [0.0]
  We present the new Orthogonal Polynomials Approximation Algorithm (OPAA) OPAA estimates probability distributions using functional analytic approach. It can be applied to estimating the normalizing weight of the posterior.
  arXiv  Detail & Related papers  (2022-11-16T00:51:00Z)
• Enumeration of max-pooling responses with generalized permutohedra [39.58317527488534]
  Max-pooling layers are functions that downsample input arrays by taking the maximum over shifted windows of input coordinates. We characterize the faces of such polytopes and obtain generating functions and closed formulas for the number of vertices and facets in a 1D max-pooling layer depending on the size of the pooling windows and stride.
  arXiv  Detail & Related papers  (2022-09-29T17:45:54Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  We present a scalable algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We propose a novel primal coupled with a Lagrange dual problem that is several orders of magnitudes faster than previous solvers.
  arXiv  Detail & Related papers  (2022-04-27T09:47:47Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  This paper introduces a class of mixed-integer formulations for trained ReLU neural networks. At one extreme, one partition per input recovers the convex hull of a node, i.e., the tightest possible formulation for each node.
  arXiv  Detail & Related papers  (2021-02-08T17:27:34Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Graph Gamma Process Generalized Linear Dynamical Systems [60.467040479276704]
  We introduce graph gamma process (GGP) linear dynamical systems to model real multivariate time series. For temporal pattern discovery, the latent representation under the model is used to decompose the time series into a parsimonious set of multivariate sub-sequences. We use the generated random graph, whose number of nonzero-degree nodes is finite, to define both the sparsity pattern and dimension of the latent state transition matrix.
  arXiv  Detail & Related papers  (2020-07-25T04:16:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.