Search

It is known that the following five counting problems lead to the same integer sequence f t (n) : the number of nonequivalent compact Huffman codes of length n over an alphabet of t letters, the number of "nonequivalent" complete rooted t-ary trees (level-greedy trees) with n leaves, the number of "proper" words (in the sense of Even and Lempel), the number of bounded degree sequences (in the sense of Komlós, Moser, and Nemetz), and the number of ways of writing 1 = 1 t x 1 + ⋯ + 1 t x n with integers 0 ≤ x 1 ≤ x 2 ≤ ⋯ ≤ x n . In this work, we show that one can compute this sequence for all n < N with essentially one power series division. In total we need at most N 1 + ε additions and multiplications of integers of cN bits (for a positive constant c < 1 depending on t only) or N 2 + ε bit operations, respectively, for any ε > 0 . This improves an earlier bound by Even and Lempel who needed O (N 3) operations in the integer ring or O (N 4) bit operations, respectively. [ABSTRACT FROM AUTHOR]

In 1974, Carlitz and Scoville introduced the Stirling–Eulerian polynomial A n (x , y | α , β) as the enumerator of permutations by descents, ascents, left-to-right maxima and right-to-left maxima. Recently, Ji considered a refinement of A n (x , y | α , β) , denoted P n (u 1 , u 2 , u 3 , u 4 | α , β) , which is the enumerator of permutations by valleys, peaks, double ascents, double descents, left-to-right maxima and right-to-left maxima. Using Chen's context-free grammar calculus, Ji proved a formula for the generating function of P n (u 1 , u 2 , u 3 , u 4 | α , β) , generalizing the work of Carlitz and Scoville. Ji's formula has many nice consequences, one of which is an intriguing γ -positivity expansion for A n (x , y | α , β) . In this paper, we prove a q-analog of Ji's formula by using Gessel's q-compositional formula and provide a combinatorial approach to her γ -positivity expansion of A n (x , y | α , β) . [ABSTRACT FROM AUTHOR]

There is a well-known bijection between finite binary sequences and integer partitions. Sequences of length r correspond to partitions of perimeter r + 1 . Motivated by work on rational numbers in the Calkin–Wilf tree, we classify partitions whose corresponding binary sequence is a palindrome. We give a generating function that counts these partitions, and describe how to efficiently generate all of them. Atypically for partition generating functions, we find an unusual significance to prime degrees. Specifically, we prove there are nontrivial palindrome partitions of n except when n = 3 or n + 1 is prime. We find an interesting new "branching diagram" for partitions, similar to Young's lattice, with an action of the Klein four group corresponding to natural operations on the binary sequences. [ABSTRACT FROM AUTHOR]

A permutation is said to be cycle-alternating if it has no cycle double rises, cycle double falls or fixed points; thus each index i is either a cycle valley ( σ - 1 (i) > i < σ (i) ) or a cycle peak ( σ - 1 (i) < i > σ (i) ). We find Stieltjes-type continued fractions for some multivariate polynomials that enumerate cycle-alternating permutations with respect to a large (sometimes infinite) number of simultaneous statistics that measure cycle status, record status, crossings and nestings along with the parity of the indices. Our continued fractions are specializations of more general continued fractions of Sokal and Zeng. We then introduce alternating Laguerre digraphs, which are generalization of cycle-alternating permutations, and find exponential generating functions for some polynomials enumerating them. We interpret the Stieltjes–Rogers and Jacobi–Rogers matrices associated to some of our continued fractions in terms of alternating Laguerre digraphs. [ABSTRACT FROM AUTHOR]

AbstractInversion sequences of length n are positive integer sequences e1 e2 …en such that 1 ≤ ei ≤ i for all 1 ≤ i ≤ n. These sequences are in bijection with the permutations of [n]. This paper focuses on the polyomino or barpgraph representation of the inversion sequences. More precisely, we study the distribution of lattice points on these polyominoes. We find the generating functions respect to the length, the number of interior vertices, corners, and vertices of a given degree. We also give simple explicit formulas for the total values of these parameters over all polyominoes of inversion sequences of length n. Throughout this work, we use symbolic computer algebra to facilitate the computations. [ABSTRACT FROM AUTHOR]

The limit theorem for the estimator G 59 {G_{59}} for the regularized solution of the Kolmogorov–Wiener filter is proved. [ABSTRACT FROM AUTHOR]

The main objective of this paper is to analyze symmetric and asymmetric peaks in Dyck paths with air pockets (DAPs). These paths are formed by combining each maximal run of down-steps in ordinary Dyck paths into a larger, single down-step. To achieve this, we present a trivariate generating function that counts the number of DAPs based on their length and the number of symmetric and asymmetric peaks they contain. We determine the total numbers of symmetric and asymmetric peaks across all DAPs, providing an asymptotic for the ratio of these two quantities. Recursive relations and closed formulas are provided for the number of DAPs of length n, as well as for the total number of symmetric peaks, weight of symmetric peaks, and height of symmetric peaks. Furthermore, a recursive relation is established for the overall number of DAPs, similar to that for classic Dyck paths. A DAP is said to be non-decreasing if the sequence of ordinates of all local minima forms a non-decreasing sequence. In the last section, we focus on the sets of non-decreasing DAPs and examine their symmetric and asymmetric peaks. [ABSTRACT FROM AUTHOR]

We present what we call a "motivated proof" of the Bressoud-Göllnitz-Gordon identities. Similar "motivated proofs" have been given by Andrews and Baxter for the Rogers–Ramanujan identities and by Lepowsky and Zhu for Gordon's identities. Additionally, "motivated proofs" have also been given for the Andrews-Bressoud identities by Kanade, Lepowsky, Russell, and Sills and for the Göllnitz–Gordon–Andrews identities by Coulson, Kanade, Lepowsky, McRae, Qi, Russell, and the third author. Our proof borrows both the use of "ghost series" from the "motivated proof" of the Andrews–Bressoud identities and uses recursions similar to those found in the "motivated proof" of the Göllnitz–Gordon–Andrews identities. We anticipate that this "motivated proof" of the Bressoud–Göllnitz–Gordon identities will illuminate certain twisted vertex-algebraic constructions. [ABSTRACT FROM AUTHOR]

Chan and Cooper proved that if the integers c (n) (n = 0 , 1 , 2 , ...) are given by ∑ n = 0 ∞ c (n) q n = ∏ n = 1 ∞ 1 1 - q n 2 1 - q 3 n 2 , then ∑ n = 0 ∞ c (2 n + 1) q n = 2 ∏ n = 1 ∞ 1 - q 2 n 4 1 - q 6 n 4 1 - q n 6 1 - q 3 n 6 . We prove many other results of this type and apply them to the determination of congruence properties of the coefficients. [ABSTRACT FROM AUTHOR]

Proudfoot, Xu, and Young introduced the Z-polynomial for any matroid and conjectured the polynomial has only real roots. Recently, Ferroni, Nasr, and Vecchi introduced the γ-polynomial of a matroid. In this paper, we prove that both the Z-polynomials and γ-polynomials of uniform matroids are ultra log-concave, which due to Newton's inequality partially supports the real-rootedness conjecture. We also give an alternative formula for the γ-polynomials of uniform matroids. As an application, we use this formula to provide a new proof of the γ-positivity of sparse paving matroids. [ABSTRACT FROM AUTHOR]

A permutation is called Grassmannian if it has at most one descent. The study of pattern avoidance in such permutations was initiated by Gil and Tomasko in 2021. We continue this work by studying Grassmannian permutations that avoid an increasing pattern. In particular, we count the Grassmannian permutations of size m avoiding the identity permutation of size k, thus solving a conjecture made by Weiner. We also refine our counts to special classes such as odd Grassmannian permutations and Grassmannian involutions. We prove most of our results by relating Grassmannian permutations to Dyck paths and binary words. [ABSTRACT FROM AUTHOR]

In this paper, we establish a system of recurrence relations and an algorithm for finding the generating function Ak(x) for the number of words over alphabet [k] of length n that avoid 1243, for arbitrary k. In particular, we present an explicit formula for the generating function Ak(x) for 1 ≤ k ≤ 10. [ABSTRACT FROM AUTHOR]

Counting perfect matchings is an interesting and challenging combinatorial task. It has important applications in statistical physics and chemistry. As the general problem is #P-complete, it is usually tackled by randomized heuristics and approximation schemes. Let GG and HH be two graphs. Denote by G×HG\times H the Cartesian product of graphs GG and HH. The number of perfect matchings of some types of Cartesian product G×HG\times H is investigated by the Pfaffian method, where G≅P2G\cong {P}_{2}, P3{P}_{3}, P4{P}_{4} or C4{C}_{4}, and H≅TH\cong T or HH is a non-bipartite graph with a unique cycle. In this article, we construct a Pfaffian orientation of the graph G×P2G\times {P}_{2}, where GG is a non-bipartite graph with kk odd cycles. We obtain the counting formula on the number of perfect matchings of G×P2G\times {P}_{2}.

We refine the enumeration of fusene chains of a given length with respect to the number of turns by constructing bijections between such chains and ternary words. Explicit formulas thus obtained are then used to compute the expected values for the whole class of bond-additive degree-based topological indices over all such chains of a given length. The results are also applicable to several other classes of chemically interesting polycyclic chains, such as, e.g., phenylene and spiro chains. [ABSTRACT FROM AUTHOR]

Two totally order relations are defined on the hyperoctahedral group B n . Regarding B n as a Coxeter group of type B, we always use the natural order. By taking B n as a color permutation group, it is convenient to use the r-order. Considering B n as a colored permutation group, Moustakas proved that the Eulerian distribution on the involutions of B n is unimodal, Cao and Liu proved that it is γ -positive, they also proved that the Eulerian distribution on the fixed-point free involutions of B n is symmetric, unimodal and γ -positive. In this paper, we prove that the Eulerian distribution on the fixed-point free involutions of B n is symmetric, unimodal and γ -positive when B n is viewed as Coxeter group of type B. [ABSTRACT FROM AUTHOR]

Munarini (J Integer Seq 23: Article 20.3.8, 2020) recently showed that the derangement polynomial d n (q) = ∑ σ ∈ D n q maj (σ) is expressible as the determinant of either an n × n tridiagonal matrix or an n × n lower Hessenberg matrix. Qi et al. (Cogent Math 3:1232878, 2016) showed that the classical derangement number d n = n ! ∑ k = 0 n (- 1) k k ! is expressible as a tridiagonal determinant of order n + 1 . We show in this work that similar determinantal expressions exist for the type B derangement polynomial d n B (q) = ∑ σ ∈ D n B q fmaj (σ) studied previously by Chow (Sém Lothar Combin 55:B55b, 2006), and the type D derangement polynomial d n D (q) = ∑ σ ∈ D n D q maj (σ) studied recently by Chow (Taiwanese J Math 27(4):629–646, 2023). Representations of the types B and D derangement numbers d n B and d n D as determinants of order n + 1 are also presented. [ABSTRACT FROM AUTHOR]

We construct a cubic cut-and-join operator description for the partition function of the Chekhov–Eynard–Orantin topological recursion for a local spectral curve with simple ramification points. In particular, this class contains partition functions of all semi-simple cohomological field theories. The cut-and-join description leads to an algebraic version of topological recursion. For the same partition functions we also derive N families of the Virasoro constraints and prove that these constraints, supplemented by a deformed dimension constraint, imply the cut-and-join description. [ABSTRACT FROM AUTHOR]

Using symbolic computation with Maple, we can discover lots of (rigorously-proved!) facts about Standard Young Tableaux, in particular the distribution of the entries in any specific cell, and the sorting probabilities. [ABSTRACT FROM AUTHOR]

The desire for privacy significantly impacts various aspects of social behavior as illustrated by people's tendency to seek out the most secluded spot when multiple options are available. In particular, this can be seen at rows of payphones, where people tend to occupy an available payphone that is most distant from those already occupied. Assuming that there are n payphones in a row and that n people occupy payphones one after another as privately as possible, the resulting assignment of people to payphones defines a permutation, which we will refer to as a payphone permutation. In the present study, we consider different variations of payphone permutations and enumerate them. [ABSTRACT FROM AUTHOR]

Recently, Freud and Rodriguez proposed a new counting process which is called the Bell–Touchard process and based on the Bell–Touchard probability distribution. This process was developed to solve the problem of rare events hypothesis which is one of the limitations of the Poisson process. In this paper, we consider the discrete degenerate Bell distributions and the degenerate Bell process which are "degenerate versions" of the Bell–Touchard probability distributions and the Bell–Touchard process, respectively. We investigate several properties of the degenerate Bell distribution. We introduce the degenerate Bell process by giving two equivalent definitions and show one method of constructing a new infinite family of degenerate Bell process out of a given infinite family of degenerate Bell process. [ABSTRACT FROM AUTHOR]

In this paper, we enumerate two families of polycubes, the directed plateau polycubes and the plateau polycubes, with respect to the width and a new parameter, the lateral area. We give an explicit formula and the generating function for each of the two families of polycubes. Moreover, some asymptotic results about plateau polycubes are provided. We also establish results concerning the enumeration of column-convex polyominoes that are useful to get asymptotic results of polycubes. [ABSTRACT FROM AUTHOR]

The group of the almost-Riordan arrays with exponential generating functions is defined. The subgroups of the exponential almost-Riordan group are presented. Also, some isomorphisms between the exponential almost-Riordan group and the exponential Riordan group are considered. Then, the production matrix for the exponential almost-Riordan array is obtained. [ABSTRACT FROM AUTHOR]

In this paper, we study the generating functions of multiple t-star values with an arbitrary number of blocks of twos, which are based on the results of the corresponding generating functions of multiple t-harmonic star sums. These generating functions can deduce an explicit expression of multiple t-star values. As applications, we obtain some evaluations of multiple t-star values that represent the relations between multiple t-star values and alternating multiple t-half values. [ABSTRACT FROM AUTHOR]

We give new explicit formulas as well as new generating functions for the associated Meixner, Charlier, and Krawtchouk polynomials. The obtained results are then used to derive new generating functions and convolution-type formulas of the corresponding classical polynomials. Some consequences of our results are also mentioned. [ABSTRACT FROM AUTHOR]

Diaconis and Gamburd computed moments of secular coefficients in the CUE ensemble. We use the characteristic map to give a new combinatorial proof of their result. We also extend their computation to moments of traces of symmetric powers, where the same result holds but in a wider range. Our combinatorial proof is inspired by gcd matrices, as used by Vaughan and Wooley and by Granville and Soundararajan. We use these CUE computations to suggest a conjecture about moments of characters sums twisted by the Liouville (or by the Möbius) function, and establish a version of it in function fields. The moral of our conjecture (and its verification in function fields) is that the Steinhaus random multiplicative function is a good model for the Liouville (or for the Möbius) function twisted by a random Dirichlet character. We also evaluate moments of secular coefficients and traces of symmetric powers, without any condition on the size of the matrix. As an application we give a new formula for a matrix integral that was considered by Keating, Rodgers, Roditty-Gershon and Rudnick in their study of the k-fold divisor function. [ABSTRACT FROM AUTHOR]

In 1988, Andrews and Garvan introduced the partition statistic "crank" in order to give combinatorial interpretation for Ramanujan's celebrated partition congruence modulo 11. In 2009, Choi, Kang and Lovejoy established congruences modulo powers of 5 for the crank parity function pC (n) by utilizing the theory of modular forms, where pC(n) denotes the difference between the number of partitions of n with even crank and the number of partitions of n with odd crank. In this paper, we provide a completely elementary proof of this congruence family. Moreover, we also prove several new congruences modulo small powers of 5. [ABSTRACT FROM AUTHOR]

We count lucky cars in parking functions of a given length, and provide elementary derivations for the generating functions, expected values and variances. We consider not only classical parking functions, but also problems with additional parking slots, and with cars of different sizes. [ABSTRACT FROM AUTHOR]

We show that the order complex of the poset of nonempty intervals, ordered by inclusion, is a Tchebyshev triangulation of the order complex of the original poset. Besides studying the properties of this transformation, we show that the dual of the type B permutohedron is combinatorially equivalent to the suspension of the order complex of the poset of nonempty intervals of a Boolean algebra (with the minimum and maximum elements removed). [ABSTRACT FROM AUTHOR]

The weight of a partition is the sum of its nonzero coordinates. Let R and S be partitions of the same weight and $ {\mathcal {A}}(R,S) $ A (R , S) be the class of all $ (0,1) $ (0 , 1) -matrices with row sums R and column sums S. For a positive integer t, the t-term rank of a matrix $ A\in {\mathcal {A}}(R,S) $ A ∈ A (R , S) , denoted $ \rho _t(A) $ ρ t (A) , is defined as the largest number of 1's in A with at most one 1 in each column and at most t 1's in each row. The term rank partition of A is the partition $$\begin{align*} term\ \rho(A) & :=(\rho_1(A)-\rho_0(A),\rho_2(A) \\ & \quad - \rho_1(A),\ldots ,\rho_t(A)-\rho_{t-1}(A),\ldots), \end{align*} $$ term ρ (A) := (ρ 1 (A) − ρ 0 (A) , ρ 2 (A) − ρ 1 (A) , ... , ρ t (A) − ρ t − 1 (A) , ...) , where $ \rho _0(A)=0 $ ρ 0 (A) = 0. Let θ be a partition of weight equal to the number of nonzero coordinates of S. In this paper, we study conditions for the existence of a matrix $ C\in {\mathcal {A}}(R,S) $ C ∈ A (R , S) with $ term\ \rho (C)=\theta. $ term ρ (C) = θ. [ABSTRACT FROM AUTHOR]

In 2018, Lin and Wang introduced two restricted partition triples, whose generating functions are related to the reciprocals of Ramanujan–Gordon identities. Let R G 2 (n) denote the number of partitions triples of n, where odd parts in the first two components are distinct and the last component only contains even parts. Lin and Wang proved some congruences modulo 5 and 7 satisfied by R G 2 (n) . They further asked the existence of the infinite families of congruences modulo high powers of 2 for the function R G 2 (n) . Utilizing some q-techniques, we prove that such congruence families indeed exist. [ABSTRACT FROM AUTHOR]