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 ...

answered Nov 20 '21 at 22:02

Noam D. Elkies

70k1212 gold badges249249 silver badges334334 bronze badges

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 ...

answered May 15 '21 at 17:51

Timothy Chow

61.4k1919 gold badges278278 silver badges462462 bronze badges

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 ...

answered May 18 '17 at 20:24

Gjergji Zaimi

81.3k44 gold badges212212 silver badges380380 bronze badges

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.

co.combinatorics sequences-and-series binomial-coefficients enumerative-combinatorics combinatorial-identities

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 ...

answered Apr 16 '21 at 1:31

Benjamin Steinberg

32.6k22 gold badges8989 silver badges159159 bronze badges

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, ...

answered Nov 11 '21 at 1:02

Gjergji Zaimi

81.3k44 gold badges212212 silver badges380380 bronze badges

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 ...

answered Jul 16 '20 at 21:52

Gjergji Zaimi

81.3k44 gold badges212212 silver badges380380 bronze badges

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 ...

answered Sep 9 '21 at 14:03

Timothy Chow

61.4k1919 gold badges278278 silver badges462462 bronze badges

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 ...

answered Dec 14 '16 at 16:31

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

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 ...

answered May 15 '18 at 2:14

Gjergji Zaimi

81.3k44 gold badges212212 silver badges380380 bronze badges

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 \...

answered Dec 20 '21 at 4:12

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

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 ...

co.combinatorics sequences-and-series binomial-coefficients enumerative-combinatorics combinatorial-identities

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

answered Apr 28 '15 at 23:12

Joe Silverman

41.3k22 gold badges119119 silver badges212212 bronze badges

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&...

answered Jun 13 '21 at 12:01

Fedor Petrov

84.6k88 gold badges195195 silver badges353353 bronze badges

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)\...

answered May 18 '17 at 20:39

Pietro Majer

50.7k33 gold badges102102 silver badges225225 bronze badges

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 ...

answered Apr 20 '18 at 2:03

Richard Stanley

42.4k1212 gold badges143143 silver badges238238 bronze badges

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{\...

nt.number-theory reference-request co.combinatorics rt.representation-theory enumerative-combinatorics

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

enumerative-combinatorics × 359co.combinatorics × 274

graph-theory × 52

reference-request × 46

nt.number-theory × 38

permutations × 26

generating-functions × 22

partitions × 21

linear-algebra × 17

pr.probability × 16

rt.representation-theory × 15

gr.group-theory × 14

algebraic-combinatorics × 14

polynomials × 12

trees × 12

discrete-geometry × 11

asymptotics × 10

binomial-coefficients × 10

integer-sequences × 10

matrices × 9

algorithms × 9

convex-polytopes × 9

finite-fields × 9

posets × 8

ac.commutative-algebra × 7