Applying the multisection series method to the MacLaurin series expansion of arcsin-function, we transform the Apéry–like series involving the central binomial coefficients into systems of linear equations. By resolving the  linear systems (for example, by Mathematica), we establish numerous remarkable infinite series formulae for π and logarithm functions, including several recent results due to Almkvist et al. (2003) and Zheng (2008).

We introduce the notion of capacity (ability to contain water) for compositions. Initially the compositions are  defined on a finite alphabet $[k]$ and thereafter on $\mathbb{N}$. We find a capacity generating function for all compositions, the average capacity generating function and an asymptotic expression for the average capacity as the size of the composition increases to infinity

As suggested by Currie, we apply the probabilistic method to problems regarding pattern avoidance. Using techniques from analytic combinatorics, we calculate asymptotic mean pattern occurrence and use them in  conjunction with the probabilistic method to establish new results about the Ramsey theory of unavoidable  patterns in the abelian full word case and in the nonabelian partial word case.

In this paper, we present several explicit formulas of the sums and hypersums of the powers of the first $(n+1)$-terms of a general arithmetic sequence in terms of Stirling numbers and generalized Bernoulli polynomials

We define a generalized class of modified zeta series transformations generating the partial sums of the Hurwitz zeta function and series expansions of the Lerch transcendent function. The new transformation coefficients we define within the article satisfy expansions by generalized harmonic number sequences as the partial sums of the Hurwitz zeta function. These transformation coefficients satisfy many properties which are analogous to known identities and expansions of the Stirling numbers of the first kind and to the known transformation coefficients employed to enumerate variants of the polylogarithm function series. Applications of the new results we prove in the article include new series expansions of the Dirichlet beta function, the Legendre chi function, BBP-type series identities for special constants, alternating and exotic Euler sum variants, alternating zeta functions with powers of quadratic  denominators, and particular series defining special cases of the Riemann zeta function constants at the positive integers s ≥ 3.

Let $[k]=\{1,2,\dots ,k\}$ be an alphabet over $k$ letters. A word $\omega$ of length $n$ over alphabet $[k]$ is an element of $[k{]}^n$ and is also called $k$-ary word of length $n$. We say that $\omega$ contains a peak, if exists $2\le i\le n-1$ such that ${\omega }_{i-1}{\omega }_{i+1}$. We say that $\omega$ contains a symmetric peak, if exists $2\le i\le n-1$ such that ${\omega }_{i-1}={\omega }_{i+1}<{\omega }_i$, and contains a non-symmetric peak, otherwise. In this paper, we find an explicit formula for the generating functions for the number of $k$-ary words of length $n$ according to the number of symmetric peaks and non-symmetric peaks in terms of Chebyshev polynomials of the second kind. Moreover, we find the number of symmetric and non-symmetric peaks in $k$-ary word of length $n$ in two ways by using generating functions techniques, and by applying probabilistic methods.

In this paper, we first give a new $q$-analogue of the Lah numbers. Then we show the irreducible factors of the $q$-Lah numbers over $\mathbb{Z}$.

Let $A$ and $B$ be additive sets of ${\mathbb{Z}}_{2k}$, where $A$ has cardinality $k$ and $B=v\cdot CA$ with $v\in {\mathbb{Z}}_{2k}^{\times }$. In this note, some bounds for the cardinality of $A+B$ are obtained using four different approaches. We also prove that in a special case, the bound is not sharp and we can recover the whole group as a sumset.

In this paper, we analyze the asymptotic number $I(m,n)$ of involutions of large size $n$ with $m$ singletons. We consider a central region and a non-central region. In the range $m=n–n^{\alpha }$, $0<\alpha <1$, we analyze the dependence of $I(m,n)$ on $\alpha$. This paper fits within the framework of Analytic Combinatorics.

An inverse-conjugate composition of a positive integer $m$ is an ordered partition of $m$ whose conjugate coincides with its reversal. In this paper, we consider inverse-conjugate compositions in which the part sizes do not exceed a given integer $k$. It is proved that the number of such inverse-conjugate compositions of $2n–1$ is equal to $2F_n^{(k-1)}$, where $F_n^{(k)}$ is a Fibonacci $k$-step number. We also give several connections with other types of compositions, and obtain some analogues of classical combinatorial identities.

S. Ekhad and D. Zeilberger recently proved that the multivariate generating function for the number of simple singular vector tuples of a generic $m_1\times ···\times m_d$ tensor has an elegant rational form involving elementary symmetric functions, and provided a partial conjecture for the asymptotic behavior of the cubical case $m_1=···=m_d$. We prove this conjecture and further identify completely the dominant asymptotic term, including the multiplicative constant. Finally, we use the method of differential approximants to conjecture that the subdominant connective constant effect observed by Ekhad and Zeilberger for a particular case in fact occurs more generally

In this paper, we define the q-analogue of the so-called symmetric infinite matrix algorithm. We find an explicit formula for entries in the associated matrix and also for the generating function of the k-th row of this matrix for each fixed k. This helps us to derive analytic and number theoretic identities with respect to the q-harmonic numbers and q-hyperharmonic numbers of Mansour and Shattuck.

Bargraphs are lattice paths in ${\mathbb{N}}_0^2$ with three allowed types of steps: up $(0,1)$, down $(0,-1)$, and horizontal $(1,0)$. They start at the origin with an up step and terminate immediately upon return to the $x$-axis. A wall of size $r$ is a maximal sequence of $r$ adjacent up steps. In this paper, we develop the generating function for the total number of walls of fixed size $r\ge 1$. We then derive asymptotic estimates for the mean number of such walls.

We survey four instances of the Fourier analytic ‘transference principle’or ‘dense model lemma’, which allows one to approximate an unbounded function on the integers by a bounded function with similar Fourier transform. Such a result forms a component of a general method pioneered by Green to count solutions to a single linear equation in a sparse subset of integers.

Let $E\subseteq {\mathbb{F}}_q^2$ be a set in the 2-dimensional vector space over a finite field with $q$ elements, which satisfies $|E|>q$. There exist $x,y\in E$ such that $|E\cdot (y–x)|>q/2$. In particular, $(E+E)\cdot (E–E)={\mathbb{F}}_q.$

Let $(x(n){)}_{n\ge 1}$ be an $s$-dimensional Niederreiter-Xing sequence in base $b$. Let $D((x(n){)}_{n=1}^N)$ be the discrepancy of the sequence $(x(n){)}_{n=1}^N$. It is known that $ND((x(n){)}_{n=1}^N)=O({\ln }^{s}N)$ as $N\to \mathrm{\infty }$. In this paper, we prove that this estimate is exact. Namely, there exists a constant $K>0$, such that
$$\underset{w\in [0,1{]}^s}{inf}\underset{1\le N\le b^m}{sup}ND((x(n)\oplus w{)}_{n=1}^N)\ge K{\ln }^s\text{ for }m=1,2,\dots .$$

We also get similar results for other explicit constructions of $(t,s)$-sequences.

We define a new class of generating function transformations related to polylogarithm functions, Dirichlet series, and Euler sums. These transformations are given by an infinite sum over the jth derivatives of a sequence generating function and sets of generalized coefficients satisfying a non-triangular recurrence relation in two variables. The generalized transformation coefficients share a number of analogous properties with the Stirling numbers of the second kind and the known harmonic number expansions of the unsigned Stirling numbers of the first kind.

We prove a number of properties of the generalized coefficients which lead to new recurrence relations and summation identities for the k-order harmonic number sequences. Other  applications of the generating function transformations we define in the article include new series expansions for the polylogarithm function, the alternating zeta function, and the Fourier series for the periodic Bernoulli polynomials. We conclude the article with a discussion of several specific new “almost” linear recurrence relations between the integer-order harmonic numbers and the generalized transformation coefficients, which provide new applications to studying the limiting behavior of the zeta function constants, ζ(k), at integers k ≥ 2.

Generating functions for Pell and Pell-Lucas numbers are obtained. Applications are given for some results recently obtained by Mansour [Mansour12]; by using an alternative approach that considers the action of the operator ${\delta }_{e_1{e}_2}^k$ to the series $\sum _{j=0}^{\mathrm{\infty }}{a}_j(e_{1}z{)}^j$.

Motivated by the Monthly problem #11515, we prove further interesting formulae for trigonometric series by means of telescoping method.

The main theorem establishes the generating function $F$ which counts the number of times the staircase $1+2+3+\cdots +m^{+}$ fits inside an integer composition of $n$.
$$F=\frac{k_m–\frac{q{x}^{m}y}{1-x}{k}_{m-1}}{(1-q)x^{(\genfrac{}{}{0ex}{}{m+1}{2})}{\left(\frac{y}{1-x}\right)}^m+\frac{1-x-xy}{1-x}(k_m–\frac{q{x}^{m}y}{1-x}{k}_{m-1})}.$$
where
$$k_m=\sum _{j=0}^{m-1}{x}^{mj–(\genfrac{}{}{0ex}{}{j}{2})}{\left(\frac{y}{1-x}\right)}^j.$$

Here $x$ and $y$ respectively track the composition size and number of parts, whilst $q$ tracks the number of such staircases contained.

An involution is a permutation that is its own inverse. Given a permutation $\sigma$ of $[n]$, let $N_n(\sigma )$ denote the number of ways to write $\sigma$ as a product of two involutions of $[n]$. If we endow the symmetric groups $S_n$ with uniform probability measures, then the random variables $N_n$ are asymptotically lognormal.

The proof is based upon the observation that, for most permutations $\sigma$, $N_n(\sigma )$ can be well-approximated by $B_n(\sigma )$, the product of the cycle lengths of $\sigma$. Asymptotic lognormality of $N_n$ can therefore be deduced from Erdős and Turán’s theorem that $B_n$ is itself asymptotically lognormal.

The Stirling number of the second kind $S(n,k)$ counts the number of ways to partition a set of $n$ labeled balls into $k$ non-empty unlabeled cells. We extend this problem and give a new statement of the $r$-Stirling numbers of the second kind and $r$-Bell numbers. We also introduce the $r$-mixed Stirling number of the second kind and $r$-mixed Bell numbers. As an application of our results we obtain a formula for the number of ways to write an integer $m>0$ in the form $m_1\cdot m_2\cdot \cdots \cdot m_k$, where $k\ge 1$ and $m_i$’s are positive integers greater than 1.

Packing patterns in permutations concerns finding the permutation with the maximum number of a prescribed pattern. In 2002, Albert, Atkinson, Handley, Holton and Stromquist showed that there always exists a layered permutation containing the maximum number of a layered pattern among all permutations of length n. Consequently the packing density for all but two (up to equivalence) patterns up to length 4 can be obtained. In this note we consider the analogous question for colored patterns and permutations. By introducing the concept of “colored blocks” we characterize the optimal permutations with the maximum number of a given colored pattern when it contains at most three colored blocks. As examples we apply this characterization to find the optimal permutations of various colored patterns and subsequently obtain their corresponding packing densities.

We extend the main result of the paper “Arithmetic progressions in sets of fractional dimension” ([12]) in two ways. Recall that in [12], Łaba and Pramanik proved that any measure $\mu$ with Hausdorff dimension $\alpha \in (1–{ϵ}_0,1)$ (here ${ϵ}_0$ is a small constant) large enough depending on its Fourier dimension $\beta \in (2/3,\alpha ]$ contains in its support three-term arithmetic progressions (3APs). In the present paper, we adapt an approach introduced by Green in “Roth’s Theorem in the Primes” to both lower the requirement on $\beta$ to $\beta >1/2$ (and ${ϵ}_0$ to $1/10$) and perhaps more interestingly, extend the result to show for any $\delta >0$, if $\alpha$ is large enough depending on $\delta$, then $\mu$ gives positive measure to the (basepoints of the) non-trivial 3APs contained within any set $A$ for which $\mu (A)>\delta$.

Let $f(x)=1+\sum _{n=1}^{\mathrm{\infty }}{a}_n{x}^n$ be a formal power series with complex coefficients. Let $\{r_n{\}}_{n=1}^{\mathrm{\infty }}$ be a sequence of nonzero integers. The Integer Power Product Expansion of $f(x)$, denoted ZPPE, is $\prod _{k=1}^{\mathrm{\infty }}(1+w_k{x}^k{)}^{r_k}$. Integer Power Product Expansions enumerate partitions of multi-sets. The coefficients $\{w_k{\}}_{k=1}^{\mathrm{\infty }}$ themselves possess interesting algebraic structure. This algebraic structure provides a lower bound for the radius of convergence of the ZPPE and provides an asymptotic bound for the weights associated with the multi-sets.

We give an arithmetic version of the recent proof of the triangle removal lemma by Fox [Fox11], for the group ${\mathbb{F}}_2^n$. A triangle in ${\mathbb{F}}_2^n$ is a triple $(x,y,z)$ such that $x+y+z=0$. The triangle removal lemma for ${\mathbb{F}}_2^n$ states that for every $\epsilon >0$ there is a $\delta >0$, such that if a subset $A$ of ${\mathbb{F}}_2^n$ requires the removal of at least $\epsilon \cdot 2^n$ elements to make it triangle-free, then it must contain at least $\delta \cdot 2^{2n}$ triangles.

This problem was first studied by Green [Gre05] who proved a lower bound on $\delta$ using an arithmetic regularity lemma. Regularity-based lower bounds for triangle removal in graphs were recently improved by Fox, and we give a direct proof of an analogous improvement for triangle removal in ${\mathbb{F}}_2^n$.

The improved lower bound was already known to follow (for triangle-removal in all groups) using Fox’s removal lemma for directed cycles and a reduction by Král, Serra, and Vena~\cite{KSV09} (see [Fox11, CF13]). The purpose of this note is to provide a direct Fourier-analytic proof for the group ${\mathbb{F}}_2^n$.

A set of natural numbers tiles the plane if a square-tiling of the plane exists using exactly one square of side length n for every n in the set. In [9] it is shown that N, the set of all natural numbers, tiles the plane. We answer here a number of questions from that paper. We show that there is a simple tiling of the plane (no nontrivial subset of squares forms a rectangle). We show that neither the odd numbers nor the prime numbers tile the plane. We show that N can tile many, even infinitely many planes.

Let $s,t$ be any numbers in $\{0,1\}$ and let $\pi ={\pi }_1{\pi }_2\cdots {\pi }_m$ be any word. We say that $i\in [m-1]$ is an $(s,t)$-parity-rise if ${\pi }_i\equiv s(\mathrm{mod}2)$, ${\pi }_{i+1}\equiv t(\mathrm{mod}2)$, and ${\pi }_i<{\pi }_{i+1}$. We denote the number of occurrences of $(s,t)$-parity-rises in $\pi$ by ${\text{rise}}_{s,t}(\pi )$. Also, we denote the total sizes of the $(s,t)$-parity-rises in $\pi$ by ${\text{size}}_{s,t}(\pi )$, that is, ${\text{size}}_{s,t}(\pi )=\sum _{{\pi }_i<{\pi }_{i+1}}({\pi }_{i+1}–{\pi }_i).$ A composition $\pi ={\pi }_1{\pi }_2\cdots {\pi }_m$ of a positive integer $n$ is an ordered collection of one or more positive integers whose sum is $n$. The number of summands, namely $m$, is called the number of parts of $\pi$. In this paper, by using tools of linear algebra, we found the generating function that counts the number of all compositions of $n$ with $m$ parts according to the statistics ${\text{rise}}_{s,t}$ and ${\text{size}}_{s,t}$, for all $s,t$.

In the paper, utilizing respectively the induction, a generating function of the Lah numbers, the Chu-Vandermonde summation formula, an inversion formula, the Gauss hypergeometric series, and two generating functions of Stirling numbers of the first kind, the authors collect and provide six proofs for an identity of the Lah numbers.

We prove that if $A\subset {\mathbb{Z}}_q\setminus \{0\}$, $A\ne ⟨p⟩$, $q=p^{\ell }$, $\ell \ge 2$ with $|A|>C\sqrt[3]{{\sqrt{\ell }}^2{q}^{(1-\frac{1}{4\ell })}}$, then
$$|P(A)\cdot P(A)|\ge C^{\prime }{q}^3$$
where
$$P(A)=\{\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right)\in S{L}_2({\mathbb{Z}}_q):a_{11}\in A\cap {\mathbb{Z}}_q^{\times },a_{12},a_{21}\in A\}.$$

The proof relies on a result in $[4]$ previously established by D. Covert, A. Iosevich, and J. Pakianathan, which implies that if $|A|$ is much larger than $\sqrt{\ell }{q}^{(1-\frac{1}{4\ell })}$, then
$$|\{(a_{11},a_{12},a_{21},a_{22})\in A\times A\times A\times A:a_{11}{a}_{22}+a_{12}{a}_{21}=t\}|=|A{|}^4{q}^{-1}+\mathcal{R}(t)$$
where $|\mathcal{R}(t)|\le \ell |A{|}^2{q}^{(1-\frac{1}{2\ell })}$.

By extending former results of Ehrhart, it was shown by Peter McMullen that the number of lattice points in the Minkowski-sum of dilated rational polytopes is a quasipolynomial function in the dilation factors. Here we take a closer look at the coefficients of these quasi-polynomials and show that they are piecewise polynomials themselves and that they are related to each other by a simple differential equation. As a corollary, we obtain a refinement of former results on lattice points in vector dilated polytopes

Using the Saddle point method and multiseries expansions, we obtain from the generating function of the Eulerian numbers $A_{n,k}$ and Cauchy’s integral formula, asymptotic results in non-central region. In the region $k=n–n^{\alpha }$, $1>\alpha >1/2$, we analyze the dependence of $A_{n,k}$ on $\alpha$. This paper fits within the framework of Analytic Combinatorics.

We introduce the problem of isolating several nodes in random recursive trees by successively removing random edges, and study the number of random cuts that are necessary for the isolation. In particular, we analyze the number of random cuts required to isolate $\ell$ selected nodes in a size-$n$ random recursive tree for three different selection rules, namely (i) isolating all of the nodes labelled $1,2,\dots ,\ell$ (thus nodes located close to the root of the tree), (ii) isolating all of the nodes labelled $n+1–\ell ,n+2–\ell ,\dots ,n$ (thus nodes located at the fringe of the tree), and (iii) isolating $\ell$ nodes in the tree, which are selected at random before starting the edge-removal procedure. Using a generating functions approach we determine for these selection rules the limiting distribution behaviour of the number of cuts to isolate all selected nodes, for $\ell$ fixed and $n\to \mathrm{\infty }$.

Guibert and Linusson introduced the family of doubly alternating Baxter permutations, i.e., Baxter permutations $\sigma \in S_n$, such that $\sigma$ and ${\sigma }^{-1}$ are alternating. They proved that the number of such permutations in $S_{2n}$ and $S_{2n+1}$ is the Catalan number $C_n$. In this paper, we compute the expected limit shape of such permutations, following the approach by Miner and Pak.

In his celebrated proof of Szemerédi’s theorem that a set of integers of positive density contains arbitrarily long arithmetic progressions, W. T. Gowers introduced a certain sequence of norms $\parallel \cdot {\parallel }_{U^2[\mathbb{N}]}\le \parallel \cdot {\parallel }_{U^3[\mathbb{N}]}\le \cdots$ on the space of complex-valued functions on the set $[N]$. An important question regarding these norms concerns for which functions they are `large’ in a certain sense.

This question has been answered fairly completely by B. Green, T. Tao and T. Ziegler in terms of certain algebraic functions called \textit{nilsequences}. In this work, we show that more explicit functions called \textit{bracket polynomials} have `large’ Gowers norm. Specifically, for a fairly large class of bracket polynomials, called \textit{constant-free bracket polynomials}, we show that if $\varphi$ is a bracket polynomial of degree $k-1$ on $[N]$, then the function $f:n\mapsto e(\varphi (n))$ has Gowers $U^k[\mathbb{N}]$-norm uniformly bounded away from zero.

We establish this result by first reducing it to a certain recurrence property of sets of constant-free bracket polynomials. Specifically, we show that if ${\theta }_1,\dots ,{\theta }_r$ are constant-free bracket polynomials, then their values, modulo 1, are all close to zero on at least some constant proportion of the points $1,\dots ,N$.

The proof of this statement relies on two deep results from the literature. The first is work of V. Bergelson and A. Leibman showing that an arbitrary bracket polynomial can be expressed in terms of a so-called \textit{polynomial sequence} on a nilmanifold. The second is a theorem of B. Green and T. Tao describing the quantitative distribution properties of such polynomial sequences.

In the special cases of the bracket polynomials ${\varphi }_{k-1}(n)={\alpha }_{k-1}{n}^{k-2}\{{\alpha }_{1}n\cdots \}$ with $k\le 5$, we give elementary alternative proofs of the fact that $\parallel {\varphi }_{k-1}{\parallel }_{U^k[\mathbb{N}]}$ is `large,’ without reference to nilmanifolds. Here we write $\{x\}$ for the fractional part of $x$, chosen to lie in $(-1/2,1/2]$.

The theory of generic smooth closed plane curves initiated by Vladimir Arnold is a beautiful fusion of topology, combinatorics, and analysis. The theory remains fairly undeveloped. We review existing methods to describe generic smooth closed plane curves combinatorially, introduce a new one, and give an algorithm for efficient computation of Arnold’s invariants. Our results provide a good source of future research projects that involve computer experiments with plane curves. The reader is not required to have background in topology and even undergraduate  students with basic knowledge of differential geometry and graph theory will easily understand our paper.

A level ($L$) is an occurrence of two consecutive equal entries in a word $w=w_1{w}_2\cdots$, while a rise ($R$) or descent ($D$) occurs when the right or left entry, respectively, is strictly larger. If $u=u_1{u}_2\cdots u_n$ and $v=v_1{v}_2\cdots v_n$ are $k$-ary words of the same given length and $1\le i\le n-1$, then there is, for example, an occurrence of $LR$ at index $i$ if $u_i=u_{i+1}$ and $v_i<v_{i+1}$, and likewise for the other possibilities. Similar terminology may be used when discussing ordered $d$-tuples of $k$-ary words of length $n$ (the set of which we’ll often denote by $[k{]}^{nd}$).

In this paper, we consider the problem of enumerating the members of $[k{]}^{nd}$ according to the number of occurrences of the pattern $\rho$, where $d\ge 1$ and $\rho$ is any word of length $d$ in the alphabet $\{L,R,D\}$. In particular, we find an explicit formula for the generating function counting the members of $[k{]}^{nd}$ according to the number of occurrences of the patterns $\rho =L^i{R}^{d-i}$, $0\le i\le d$, which, by symmetry, is seen to solve the aforementioned problem in its entirety. We also provide simple formulas for the average number of occurrences of $\rho$ within all the members of $[k{]}^{nd}$, providing both algebraic and combinatorial proofs. Finally, in the case $d=2$, we solve the problem above where we also allow for \textit{weak rises} (which we’ll denote by $R_w$), i.e., indices $i$ such that $w_i\le w_{i+1}$ in $w$. Enumerating the cases $R_w{R}_w$ and $R_w{R}_{uw}$ seems to be more difficult, and to do so, we combine the kernel method with the simultaneous use of several recurrences.

Let $G$ be a simple, connected graph with finite vertex set $V$ and edge set $E$. A depletion of $G$ is a permutation $v_1{v}_2\dots v_n$ of the elements of $V$ with the property that $v_i$ is adjacent to some member of $\{v_1,v_2,\dots ,v_{i-1}\}$ for each $i\ge 2$. Depletions model the spread of a rumor or a disease through a population and are related to heaps. In this paper, we develop techniques for enumerating the depletions of a graph.