1
vote
2answers
30 views

Partitions tending to a constant

$P_{k}(n)$ = the number of partitions of n into k parts. Now, if we fix some $t\ge 0$ , then $\lim_{n\to\infty}P_{n-t}(n)\to$ c, c being some constant. Please help me with this! I believe ...
0
votes
0answers
26 views

Question about computing two asymptotics

Fix $k$. Is there a constant $c \in (0,1)$ such that if $L=cn$ and $n$ tends to infinity then $$\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} \sim \sum_{s=0}^k{L \choose s}{n-L \choose ...
0
votes
0answers
13 views

Asymptotics of two expressions

I'd like to know something about this equation $\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} = \sum_{s=0}^k{L \choose s}{n-L \choose s}s!\frac{(2k-2s)!}{2^{k-s}(k-s)!)}{L-s \choose 2k-2s}.$ I am ...
2
votes
0answers
45 views

Density of Pythagorean triples

We define a Pythagorean triple as a triple $<a,b,c>$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $<a,b,c>$ is legit iff $b>a$. ...
2
votes
2answers
74 views

Growth Rate of Alternating Sign Matrices

I am trying to compute the best growth rate for the following sequence $$ a_n=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} $$ This sequence counts the number of $n\times n$ alternating sign matrices: ...
6
votes
1answer
33 views

Equivalent of a sequence in regard to a certain length of a cycle for $\mathfrak{S}_{n}$

Let $n \in \Bbb{N}$ ( for me $0\notin \Bbb{N})$. Find the limit as $n$ tends to $+ \infty$ of the following sequence $$\frac{\alpha_{n}}{n}$$ where $\alpha_{n}$ is the number of permutations of ...
8
votes
0answers
162 views

How to estimate $Pr[vr_i=ur_i]$ in the presence of rotations

Suppose we want to compute the probability that for two different random vectors (with elements that are $0$ or $1$), denoted by $v$ and $u$, multiplying them with the rotations of a random vector $r$ ...
3
votes
1answer
38 views

Combinatorial identity involving sum of products?

Let $(c_1, c_2, \cdots)$ be an $m$-periodic sequence of natural numbers and let $n$ and $k$ be integers with $0\leq k \leq n$. I am trying to simplify $$ \sum_{\substack{I \subseteq \{1, \cdots, n\}\\ ...
0
votes
1answer
31 views

asymptotic notation rearrangment

I'm having a look at this paper http://arxiv-web3.library.cornell.edu/pdf/0903.3048v1.pdf namely Theorem 5 and why it implies Theorem 2 immediately. Basically, I'm hoping somebody could explain to ...
0
votes
0answers
63 views

OEIS sequence A086449

OEIS sequence A086449 http://oeis.org/A086449 is defined by: $a(0)=1$, $a(2n+1)=a(n)$, $a(2n) = a(n)+a(n-1)+\ldots+a(n-2^m)+\ldots$ $= a(n)+\sum_{i=0}^{\lfloor\lg n\rfloor}a(n-2^i)$ One can show ...
1
vote
1answer
49 views

Integer Partition into Powers

Is there any way to count the number of integer partitions of a number N into powers of two such that each size is repeated a power of two times? Ok so the recurrence can be expressed by: $a(0)=1$, ...
0
votes
0answers
18 views

Big-Oh for size of a Sperner family

I'm developing an algorithm that will generate a collection of subsets of a ground set having the property that no subset in the collection is a subset of any other, and I'd like to give a Big-Oh ...
1
vote
1answer
38 views

Rearranging asymptotic notation

If $a \le b^{\frac{1+\log_{2}b}{2}}(1+o(1))$, then what is $b$ in terms of $a$? Whenever I try to rearrange this, I get in a huge mess... Any help would be appreciated. Thanks.
0
votes
1answer
46 views

Expected number of $k$-cliques in $G(n, 1/2) \ge 1$

Let the expected number of $k$-cliques be denoted by $$f(k) = \binom{n}{k} (\frac{1}{2})^{- \binom{k}{2}}$$ let $k_0$ denote the largest $k$ such that $f(k) \ge 1$. I want to prove that $k_0 = ...
0
votes
1answer
10 views

A question on an asymptotic combinatorial expasion

Suppose we are given $(\lambda a + \bar{\lambda}b+O(\lambda^2))^{n}$, where $0 < \lambda < 1$ and $\bar{\lambda} := 1-\lambda$; also, $0 < a,b < 1$. $O(\cdot)$ is the traditional Big-Oh ...
1
vote
3answers
65 views

A particular sum involving product of binomial coefficients

I am encountering a particular sum involving binomial coefficients, and I am looking for a possible closed-form solution. Here is the sum: suppose we are given two real numbers $a \in (0,1)$ and $b ...
0
votes
0answers
25 views

Little O Bound, Combinatorics

I am reading a book on combinatorics. I tried deriving the result in the following sentence, but could not get it. Can someone show me the algebra? Theorem 1.2.1: If $\dbinom{n}{k} {(1- ...
0
votes
1answer
89 views

Big-Oh, Big-Omega, Big-Theta

Can someone provide concrete reasoning for how to solve the following equations with respect to Big-Oh, Big-Omega, and Big-Theta? \begin{equation} 6n^2 + 20n = O(n^3) \end{equation} \begin{equation} ...
0
votes
1answer
33 views

Proving if equation is $O(\log n)$

How do I prove if \begin{equation} 2\log(n^{2}\log n) = O(\log n) \end{equation} is true? I began by trying to find a $C$ where \begin{equation} 2\log(n^{2}\log n) < O(\log n) \end{equation} ...
-1
votes
2answers
73 views

Proving Big O(1) [closed]

How do I determine if the below is true or false? \begin{equation} 17^{100} + \frac{1}{n} = O(1)? \end{equation} I have tried using the c and No method but still can not come up with a solution.
0
votes
1answer
34 views

Proving Big Θ of summations with exponentials

I have been working on this problem but have had a hard time understanding how to prove it as True, which I believe it is. ...
2
votes
0answers
32 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
1
vote
1answer
49 views

Maximizing edges in directed acyclic graph

Question: What is the maximum number of edges in a non-transitive directed acyclic graph on $n$ vertices? Here nontransitive means, if there is an edge between $A$ and $B$, and an edge between $B$ ...
1
vote
0answers
24 views

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)…(n-k+1) \approx n^k$

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)...(n-k+1) \approx n^k$ Do I start by dividing both sides by n^k and collecting terms, perhaps? Not sure. Not entirely sure about the relevance of ...
3
votes
0answers
60 views

Asymptotics of partitions in at most n parts, bounded by r

For every positive integers $n,r,w$ define $$ p_w(n,r)=\#\{ (i_1,...,i_r) | \, 0\leq i_1 \leq \dots \leq i_r\leq n, \, i_1+\dots+i_r=w\} $$ as the number of partitions of $w$ in at most $r$ piece ...
0
votes
1answer
47 views

Stirling, asymptote of $n^2+n-1\choose n$

I need to find the asymptote of $n^2+n-1\choose n$. any idea? I used the Stirling formula for $n!$ but I found an unexpected final answer.
9
votes
2answers
190 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
6
votes
3answers
98 views

Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$

In this question we are asked to show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$ What I did: $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \sum_{k=2012}^{n} 2^k*1^{n-k}\binom{n}{k} \leq ...
15
votes
4answers
610 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
3
votes
1answer
111 views

Euler numbers grow $2\left(\frac{2}{ \pi }\right)^{2 n+1}$-times slower than the factorial?

Stirling's approximation of the factorial for even numbers is given by $$ (2n)! \sim \left(\frac{2n}{e}\right)^{2n}\sqrt{4 \pi n}. \tag{1} $$ Further, the Euler numbers grow quite rapidly for large ...
1
vote
1answer
84 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
2
votes
0answers
176 views

representing integers as linear combination of integers

Let $a,b,a',b'$ be $r-\epsilon_1$ bit positive integers. Let $c,d$ be $s+\epsilon_2$ bit positive integers. Fix a pair $c,d$ and vary $a,b$ over all $r-\epsilon_1$ bit numbers. Do we have almost ...
4
votes
1answer
84 views

Asymptotics of coefficients in the expansion of $\log\cos x$

Let $c_n$ be the coefficient of $x^{2n}$ in the Maclauren expansion of $\log\cos x$. What can be said about the asymptotics of $c_n$ as $n\to\infty$? I expect that this question is routine, but I ...
0
votes
0answers
52 views

Number of Singleton Blocks in Set Partition

I'm interested in some general information on the following question: Consider the collection of partitions of an $n$-set into $m$ blocks as a uniform probability space. Let $X$ be the random ...
5
votes
2answers
158 views

Find asymptotics of $x(n)$, if $n = x^{x!}$

Find the asymptotic for $x(n)$, if $n = x^{x!}$. I've tried 1) to take a logarithm: $x! \log{x} = \log{n}$. 2) to find $n'(x)$, using gamma-function for factorial $\Gamma(z) = \int_0^\infty ...
3
votes
1answer
132 views

Asymptotics for sums involving factorials

This question is rather general, but I have recently encountered the following situation in a variety of different settings. Let us suppose that we are given a complicated sum involving factorials ...
5
votes
1answer
123 views

Find asymptotic for $s(n)=\min\{m\in{\mathbb N}\mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I ...
0
votes
1answer
94 views

Threshold of connectivity in a random graph

I am trying to understand the proof to a random graph problem (the threshold for connectivity of $G \sim G(n,p)$ being $\frac{logn}{n}$). I am struggling to see exactly why the following holds: ...
2
votes
1answer
40 views

Would this be bounded

Let $a_{m}$ be supremum of the minimum of the angle between the line segments between any $m$ points, in which the supremum is taken over all configurations of $m$ points. Is $\sqrt{m}a_{m}$ bounded ...
0
votes
3answers
95 views

Asymptotic of binomial coeficient

I was doing a problem, and I found that I needed to calculate asymptotics for $$ \frac{1}{{n - k \choose k}}$$ Supposing $n = k^2$. Any help with this would be appreciated, thanks.
0
votes
2answers
172 views

Probability in ball coloring

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ...
33
votes
0answers
816 views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
8
votes
2answers
233 views

Known bounds for the number of groups of a given order.

The number of nonisomorphic groups of order $n$ is usually called $\nu(n)$. I found a very good survey about the values. $\nu(n)$ is completely known absolutely up to $n=2047$, and for many other ...
5
votes
2answers
193 views

Interval of convergence of $\sum\limits_{n\geq0} \binom{2n}{n} x^n$

We consider the power series $\displaystyle{\sum_{n\geq0} {2n \choose n} x^n}$. By Ratio Test, the radius of convergence is easily shown to be $R=\frac{1}{4}$. For $x=\frac{1}{4}$, Stirling ...
4
votes
4answers
481 views

How do I prove that $2^n=O(n!)$?

How do I prove that $2^n=O(n!)$? Is this a valid argument? ...
0
votes
1answer
75 views

Summing ratio of partial sums of binomial coefficients

I would like to approximate the following when $n \gg k$. $\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$ The formula can be re-written ...
2
votes
0answers
89 views

Weighted sum of ratio of partial sum of binomial coefficients

I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$, $$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
2
votes
1answer
136 views

Proof of asymptotic expansion of binomial coefficient

here's the problem I'm currently stuck on: Prove that (for $k$ fixed): $$\binom{N}{k}=\frac{N^{k}}{k!}+O(N^{k-1})$$ I know that: $$\binom{N}{k}\le\frac{N^{k}}{k!}$$ But I'm not sure how to ...
1
vote
0answers
41 views

Conditioned probability in certain matrices with entries 0,1,$-1$

Consider $2\times n$-matrices with entries 0, 1 or $-1$, such that the number of zeroes in both rows is the same. Let $P_n$ be the probability that the first non negative element of both rows is a ...
4
votes
2answers
180 views

Asymptotic behavior of sum of squares of combinatorial numbers with a weight.

Consider the following sequence of natural numbers, $$M_n = \sum_{k=0}^n \binom{n}{k}^2 4^k$$ We can interpret $M_n$ as the cardinality of the set $X$ of $(2\times n)$-matrices with entries in ...