Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [analytic-combinatorics]

Use for questions related to counting combinatorial objects.

1
vote
0answers
20 views

Asymptotics of Generating Coefficients along a Ray

Suppose I have a multidimensional array of numbers $a(n_1,\ldots,n_r)$, for $n_1,\ldots,n_r\in\mathbb N\cup\{0\}$. I can form the generating function $$A(x_1,\ldots,x_r)=\sum_{n_1,\ldots,n_r\geq 0}a(...
2
votes
2answers
81 views

Solving combinatorial problems with symbolic method and generating functions

I am trying to solve the following problems: a) Let $\mathcal{F}$ be the family of all finite 0-1-sequences that have no 1s directly behind each other. Let the weight of each sequence be its length. ...
1
vote
0answers
56 views

Relation between generating function of a sequence and reciprocal sequence

Stating that for a sequence $\{a_n\}$ its generating function is $f(x)=\sum_{n=0}^\infty a_n x^n$. I am interested in finding out its relationship with generating function of the sequence $\{b_n=1/a_n\...
1
vote
0answers
22 views

Asymptotic Expression for the number of solutions to linear Diophantine equation.

Consider the the general linear diophantine equation $$\sum_{i=1}^{k}a_ix_i =n $$ with $a_i\geq 1, n\geq 1$ and $x_i\geq 0.$ Then the generating function that counts the number of solutions to this ...
2
votes
1answer
73 views

Properties of analytic functions with no real roots?

Suppose one has an entire complex analytic function $f(z)$ having no zeros on the real axis. Is it possible to find an analytic function $g(z)$ such that the coefficients of the power series expansion ...
4
votes
1answer
78 views

Number of ways to represent $100$ as a sum of $1, 5, 10, 25$

In how many ways can you represent $100$ as a sum using only these numbers: $1, 5, 10, 25$ if the order does not matter? What if the order did matter? My solution: Let the power of $x$ denote our ...
5
votes
1answer
296 views

Multivariate Faà di Bruno's formula

I'm attempting to implement a computer algebra function using the combinatoric version of Faà di Bruno's formula presented by Michael Hardy in Combinatorics of Partial Derivatives that "collapses" ...
2
votes
1answer
642 views

Number of paths in a grid below a diagonal [closed]

Given there is a $n\times n$ square grid . I was trying to calculate the number of paths from $(0,0)$ to $(n,n)$ under the condition that one might move either up or to the right one step at a time. ...
1
vote
1answer
34 views

Obtaining central coefficients from bivariate generating function

Let $\langle a_{k,n} : k,n \in \mathbb{N} \rangle$ be a bivariate number sequence, and let $f(x,y) = \sum_k \sum_n a_{k,n} x^k y^n$ be its corresponding bivariate generating function. Is there a ...
2
votes
1answer
39 views

5 power k in binary form 1's and 0's density for large k.

Suppose you have a very large k. By observation (thousands of digits), 5 power k in a binary form tends to have half 1's, and half 0's. Is this observation easy to prove?
2
votes
1answer
172 views

Lower Bound for Sum.

I want to find a lower bound for the sum \begin{equation} (1/2)^{2n} \sum_{k=0}^{2n} \binom{2n}{k} \left|1- (1+\delta)^k (1-\delta)^{2n-k} \right| \end{equation} where $n>1$, $0<\delta<1/4$. ...
3
votes
1answer
54 views

Number of groups of order n as a series coefficient

Consider the sequence A000001 in oesis.org: $ g_{n}= $ number of (isomorphism classes of) groups of order n. Is it known for which $ z $ the generating function $ \sum_{n=1}^{\infty}g_{n}z^{n} $ ...
1
vote
1answer
68 views

Integer solutions to $a_1+a_2+a_3+\cdots a_n = N$, where $l_i \leq a_i \leq r_i$ for each $i=1,2,\ldots,n$

Given $l_1, l_2, l_3, \ldots, l_n\in\mathbb{Z}$, $r_1, r_2, r_3, \ldots, r_n\in\mathbb{Z}$, and an integer $N$, find a general formula to calculate the number of ways that $N$ can be written as the ...
0
votes
1answer
62 views

Prove that the no. of selections of n things from two sets of n identical things and n other distinct things is (n+2)×2^(n-1)

Prove that the number of selections of $n$ things from two sets of $n$ identical things and $n$ other distinct things is $(n+2)\cdot 2^{(n-1)}$. I have been trying to come up with a combinatorial ...
2
votes
1answer
90 views

Number of partitions in decreasing order

I want to find out the number of partitions which are strictly in decreasing order. Eg. Partition of 4 is : 4 3 1 2 1 1 1 1 1 1 Here there's only one partition {...
3
votes
2answers
176 views

Inverse of the sum $\sum\limits_{j=1}^k (-1)^{k-j}\binom{k}{j} j^{\,k} a_j$

$k\in\mathbb{N}$ The inverse of the sum $$b_k:=\sum\limits_{j=1}^k (-1)^{k-j}\binom{k}{j} j^{\,k} a_j$$ is obviously $$a_k=\sum\limits_{j=1}^k \binom{k-1}{j-1}\frac{b_j}{k^j}$$ . How can one ...
10
votes
4answers
451 views

Prove that $\sum\limits_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\binom{2n-j}{j}\,2^{2(n-j)}=\binom{2n+1}{2k+1}$.

In an attempt to answer this thread, I discovered an identity involving binomial coefficients. However, I am not able to find a proof. All tricks are welcome. Let $n$ and $k$ be nonnegative ...
10
votes
0answers
152 views

Generalizing the growth of sums of two squares

Consider the set $S$ of numbers which are the sum of two (integer) squares, and define $S(n)$ as the number of members of $S$ in $\{1,2,\ldots,n\}.$ It is well-known that $$ S(n) \sim \frac{Kn}{\sqrt{\...
2
votes
0answers
268 views

Taylor series for multivalued complex functions (and their use in combinatorics)

As far as I know, it is considered to be a "fact" that by the Generalized Binomial Theorem, the complex function $\sqrt{1 + z}$ has the following Taylor expansion at $z = 0$: $$\sqrt{1 + z} = \sum_{n \...
2
votes
0answers
39 views

Limiting behaviour of usual lengths of runs

From Flajolet/Segdewick's Analytical Combinatorics (p. 53) I have learned that 97% of the binary sequences of length 200 contain runs longer than 5. The other way around: 97% of the sequences contain ...
1
vote
1answer
426 views

Using generating functions to answer how many bit strings of length N have no 000

The Problem I've been self-studying Introduction to Analysis of Algorithms by Sedgewick and Flajolet. I'm on the fifth chapter, and struggling with exercise 5.1: How many bit strings of length N ...
1
vote
2answers
501 views

In how many bit strings of length 10 are there with no 3 0s adjacent

it is hard for me dealing with more than 2 not adjacency problems, I need some straightforward approaches for these kinda problems, I have searched most of the community looking for similar problems ...
2
votes
1answer
143 views

A combinatorial sum and identity involving Stirling numbers of the second kind

Let $n, k \geq 1$. Let $a(j),\, 1\leq j \leq k$, be a sequence of real numbers. Consider the sum $$ \sum_{j=1}^k j! S(k, j) {n \choose j} a(j), $$ where $S(k,j)$ are Stirling numbers of the second ...
0
votes
0answers
94 views

Asymptotics of Binomial coefficients

I have the following expression $$\binom{p-q}{\frac{p-q}{2}}-\binom{p-q}{\frac{p-q}{2}-1}=\frac{(p-q)!}{(\tfrac{p-q}{2})!(\tfrac{p-q}{2}+1)!},$$ where $p$ and $q$ are nonnegative integers with $p\...
4
votes
2answers
180 views

Generating functions for tail length and rho-length

I am trying to obtain generating functions for tail length and rho length of a random point in a random mapping. Let $\phi:\{1,2,\ldots,n\}\to \{1,2,\ldots,n\}$ be a random function. Consider the ...
0
votes
1answer
71 views

Count n-length words containing pattern

I have a class $A$ of words from alphabet of letters {a,b,c}, containing "abbc" and class $B$ which has the same words but with ...
2
votes
2answers
98 views

Analytic Combinatorics to asymptotically estimate the number of objects of size at most n?

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics. I am quiet curious as how to asymptotically estimate the number of objects of size at most n. Suppose for example ...
2
votes
0answers
348 views

The number of lattice points in d-dimensional ball

The following paper states that the number of lattice points in a $d$-dimensional ball of radius $R$ is $V_d R^d + O(R^\alpha)$ where $\alpha = d - 2$ and $V_d$ is the volume of the unit $d$-...
8
votes
3answers
720 views

Generating Functions and Linear Diophantine Inequalities

The following exercise is from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick, page 46. A $k$-composition of $n$ is an ordered $k$-tuple of non-negative integers whose sum is $n$. ...