36
Apparently not mentioned yet, though surely not new:
use the quadratic equation satisfied by the generating function.
Since we look for $n+1$ to be a power of $2$, we shift the index by $1$
and consider
$$
F = \sum_{n=0}^\infty C_n x^{n+1} = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots.
$$
Then $F = x + F^2$. Instead of solving ...
36
Taking the fact that Catalan numbers $C_n$ measure the number of binary trees on $n$ nodes, we can find an involution on the set of these trees: choose the lexicographically first node in the tree that's unbalanced (i.e., where the number of nodes in the left subtree is different from the number in the right subtree). Then partner this tree with the one ...
24
I'm not sure if this is exactly what you're looking for, but the main topic of Herb Wilf's article What is an Answer? is how to answer the question "How many ______ are there?" His basic thesis is that an alleged answer to such a question is satisfactory only if it provides an algorithm whose computational complexity is significantly less than the ...
22
I'll show that
$$
\log a(n) \sim \frac{(\log n)^2}{\log 4} \approx 0.7213\ldots (\log n)^2.
$$
So the range for the constant given in the conjecture is false, but an asymptotic of that general shape
holds. One can obtain more precise asymptotics by working harder with the argument below.
Roughly speaking what the argument says is that $a(n)$ behaves (...
22
Multiply the whole equality by $(-1)^n$.
First of all, notice that $k\choose m_1,\dots,m_k$ is the number of ways to permute the numbers $\lambda_1,\dots,\lambda_k$, so the left-hand side equals
$$
L=\sum_{\lambda_i\geq 1, \; \lambda_1+\dots+\lambda_k=n}
(-1)^k\prod_{i=1}^k{n+1\choose \lambda_i}.
$$
Denote
$$
S(x)=\sum_{j=1}^{n+1} {n+1\choose j}x^l=(...
21
Just playing around with it: The RHS multiplied by $n$ is the same as
$$2 \sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n}{k} \binom{n+1}{k+2}.$$
Subtracting this from $n$ times the LHS gives
$$\sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n+1}{k+2} \left( \binom{n}{k+1} - \binom{n}{k} \right).$$
Now you check that replacing $k$ with $n-1-k$ changes the sign of the ...
20
Both sides are equal to $\binom{x+y+1}{n}_q$. This enumerates lattice paths in an $n\times (x+y-n+1)$ rectangle, according to the area statistic. We will assume that these paths start at $(0,0)$ and end at $(x+y-n+1,n)$, and they are only directed East or North. Here are two ways to enumerate it:
First count: For each path there will be a unique $k$, so it ...
18
This is known as Jensen's identity and dates back to 1902. See here an overview of this identity and related ones, and a proof: https://arxiv.org/abs/1005.2745, a paper by Victor Guo.
18
Grigorchuk showed that there are uncountably many growth degrees of 2-generated infinite p-groups for any prime p. Hence there are uncountably many isomorphisms classes and even quasi-isometry classes of finitely generated torsion groups. See page 116 of Grigorchuk - On the Gap Conjecture concerning group growth for a discussion. This is of course much ...
17
The answer to your question is ``yes". Something more general was proved by Hawkes, Isaacs and \"Ozaydin in a 1989 paper in the Rocky Mountain Journal of Mathematics.
CORRECTION: As Sebastien Palcoux notes below, this result is due to Kratzer and Th\'evenaz
More precise results for the groups $PSL_2(p)$ were known to Philip Hall, and $PSL_2(q)$ was ...
17
Here is a bijective proof that equates both $a(n)$ and $b(n+1)$ to the quantity
$$p(n)+2p(n-1)+\cdots+np(1)+(n+1)p(0) \tag1$$
where $p(n)$ is the number of partitions of $n$.
For $a(n)$: each partition with three types of $1$'s corresponds to a partition of $k$ together with $(n-k)$ parts from $\{1',1''\}$. This second gadget can be chosen in $(n-k+1)$ ways, ...
16
For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2} $ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics" (see p.481) with the main ingredients being singularity analysis and the relation
$$I(z)=H(z)-\frac{1}{2}\left(H(z)^2-H(z^2)\right)$$
where $I$ is the ...
16
Here is at least a heuristic argument for why we should expect fewer vertical dominoes than horizontal dominoes. As we increase the length of the strip (to the right, say), let us think about how the rightmost four squares are covered. There are three cases: (1) two horizontal dominoes; (2) two vertical dominoes; (3) the last two squares are covered by a ...
16
Here's a proof that indicates a systematic method for proving such identities. Let $\eta(z) = q^{1/24} \prod_{n=1}^{\infty} (1-q^{n})$, with $q = e^{2 \pi i z}$. The identity you state in the equation is the same as
$$
\frac{\eta^{3}(2z)}{\eta^{3}(z)} - \frac{\eta(6z)}{\eta(3z)} = 3 \frac{\eta(2z) \eta^{2}(18z)}{\eta^{2}(z) \eta(9z)}.
$$
Replacing $z$ with ...
15
We can use the characterization by Christie. Let $\pi \in S_n$. Add a fixed point $0$ to $\pi$, and let $c$ be the cycle $(0, 1, \ldots, n)$. Then the smallest number of block interchanges to sort $\pi$ is equal to $\frac{n + 1 - t}{2}$, where $t$ is the number of cycles in decomposition of $c \pi^{-1} c^{-1} \pi$. When $n$ is odd, the maximum value is ...
14
This is a sketch of a solution by my student Yan Zhuang and me. A paper with all the details (and further results) can be found in Counting permutations by alternating descents, Electronic J. Combin. 21 (4) (2014), Paper #P4.23.
We find the exact exponential generating function for counting these permutations and derive the asymptotics from it.
First, ...
14
You can find the solutions for any given $z$ by looking for the integral
points on the elliptic curve
$$x^2 = (-y)^3 + z^7$$
(which would usually be written $y^2 = x^3 + z^7$). The curve
is isomorphic to the curve obtained by replacing $z^7$ with $z$,
so the computation is feasible for reasonable values of $z$.
Magma (for example, but
also SAGE) has an ...
14
Here is a purely combinatorial proof of a more general identity
$$
\sum_{\lambda\vdash n}(-1)^{n-k}\frac{k!}{m_1!\cdots m_n!}\prod_{i=1}^k\binom{A}{\lambda_i}=\binom{A+n-1}n.
$$
As Ilya suggests, we rewrite this as $$\sum_{\lambda_i\geq 1, \; \lambda_1+\dots+\lambda_k=n}
(-1)^{n-k}\prod_{i=1}^k{A\choose \lambda_i}.$$
This is an alternating sum of sequences ...
14
Yes there is a connection. While $n^{n-2}$ counts the number of vertex labeled trees on $n$ vertices, the expression $2^n(n+1)^{n-2}$ counts the number of edge labeled trees on $n$ edges. There is a bijection between edge labeled trees on $n$ vertices and proper $(n-1)$-dimensional polycubes of size $n$. See lemma 2 (which combinatorially proves the relation ...
14
For power series $u(x_1,\ldots,x_n),v(x_1,\ldots,x_n)$ call $u,v$ similar and write $u\sim v$ if all monomials $\prod x_i^{c_i}$ with $c_i\in \{0,1\}$ have equal coefficients in $u,v$. In other words, if $u$ is congruent to $v$ modulo the ideal generated by $x_i^2$'s. Note that this similarity respects addition and multiplucation, and that $(1-x_i)^{-1}\sim \...
13
Oh no, I was too slow... sorry for the double reference. This is Jensen's identity. It first appeared (in a slightly modified form) in: Jensen, Sur une identité d'Abel et sur d'autres formules analogues, Acta Mathematica, vol 26 (1902) pp.307-318.
There is the following paper that gives elementary proofs to Jensen's identity and some generalizations or ...
12
Simple proof? Sort of.
Let $t(n)$ be the number of plane triangulations with $n$ vertices. Tutte
[in ''A Census of Planar Triangulations,'' Canad. J. Math. 14 (1962), 21-38]
found an explicit formula for $t(n)$, implying that $t(n)\sim c n^\alpha \gamma^n$, where $\gamma=256/27$. From here, the number $a(n)$ of non-isomorphic planar graphs is at most ...
12
There's a beautiful lecture by Carl Pomerance in which he discusses Erdos's Multiplication Table Problem and then goes on to talk about dense product-free sets of integers. The talk was at the JMM in Boston in 2012. It's available at
https://math.dartmouth.edu/~carlp/sumproductboston.pdf
12
Let $$C(x) = \sum_{n=1}^\infty C_{n-1} x^n = \frac{1-\sqrt{1-4x}}{2}.$$ Then the identity in question follows easily from $C(x(1-x)) = x$.
12
Let's consider $n\geqslant 5$ case only ($n=1,2,3,4$ are straightforward). Then $Q_n$ has non-negative coefficients and we care on the number of negative roots of $Q_n$.
We have $2P_n(-x)=(1+i\sqrt{x})^n+(1-i\sqrt{x})^n$. So, we should prove that $$2Q_n(-x)=(1+i\sqrt{x})^n+(1-i\sqrt{x})^n+2nx$$ has $\lfloor n/2\rfloor$ positive roots. Denote $x=\tan^2 t$, $0&...
11
You can split noncrossing graphs and get equations for the generating functions. I like to take the minimal root edge (if it exists).
$$N=1+xN+2xN\bar N$$
This says that an acyclic noncrossing graph is either empty ($1$), or has an isolated root ($xN$), or has a minimal root edge ($2$ counts either direction) with a noncrossing graph on one side and an edge-...
11
If we substitute $y:=v+n$ in the identity, the LHS becomes a convolution of two similar sequences,
$$\sum_{k=0}^nq^{(v+1)k}\binom{x+k}{k}_q \binom{v+(n-k)}{n-k}_q =\sum_{k=0}^n q^{n-k}\binom{x+v+n-k}{n-k}_q \, .$$
In terms of the known series $$f_x(z):=\sum_{k=0}^\infty \binom{x+k}{k}_q \,z^k=\prod_{k=0}^x{1\over1-q^kz}$$ the identity reads
$$f_x(q^{v+1}z)\...
11
By the method I used to solve
Counting "connected" edge orderings (shellings) of the complete graph,
I can show the following:
$$ g(m,n) = (mn-1)!\,m!\,n!\sum \frac{b_1 b_2\cdots b_{m+n-2}}
{b_{m+n-2}(b_{m+n-3}+b_{m+n-2})\cdots(b_1+b_2+\cdots+b_{m+n-2})}, $$
where the sum is over all sequences $a_1 a_2\cdots a_{m+n-2}$ of $m-1$
$0$'s ...
11
Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how the number of permutations in $\mathfrak{S}_n$ you are looking for is asymptotically $\approx \frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $...
11
The sum $\sum_\mu \chi^\lambda_\mu$ over partitions $\mu$ of $n$ is the multiplicity of the irreducible $\chi^\lambda$ in the character afforded by $\mathfrak S_n$ acting on itself by conjugation. If $\psi$ is the character for conjugation, then $\psi(g)$ is the size of the centralizer of $g$, so
$$\langle \chi^\lambda,\psi\rangle =\sum_{\mu\vdash n} \frac{\...
Only top voted, non community-wiki answers of a minimum length are eligible