54 votes
Accepted
The "square root" of a graph?
There is a fixed-point-free involution on these graphs which I will call loop-switching, given by adding a loop to every vertex that doesn't have one while simultaneously deleting the loops from all ...
- 1,432
40 votes
The "square root" of a graph?
These numbers count balanced signed graphs (without loops). A signed graph is a graph in which every edge has a sign, either positive or negative. It is balanced if every cycle has an even number of ...
- 17.7k
22 votes
Accepted
How to prove the identity $\sum_{k=0}^\infty(22k^2-92k+11)\binom{4k}k/16^k=-5$?
Per my old answer in AoPS, the generating function $f(x) := \sum_{k\geq0} \binom{4k}k x^k$ satisfies the algebraic identity: $$(f(x) - 1)(3f(x) + 1)^3 = x ( 4 f(x) )^4.$$ From where by differentiating,...
- 38.3k
22 votes
Have you seen my power series?
The general solution to $$\Phi(q,t)\cdot \Phi(q^{-1},-t) = 1,\quad \Phi(q,0)=-1$$ is given by $$\Phi(q,t)=-e^{tF(q+q^{-1},t^2) + (q-q^{-1})t^2G(q+q^{-1},t^2)},$$ where $F$ and $G$ are arbitrary ...
- 38.3k
21 votes
Accepted
Alternating sum of hook lengths: Part I
The hook length $h_{ij}(\lambda)$ counts the number of boxes directly below or directly to the right of box $(i,j)$. (I picture the Young diagram of $\lambda$ as having the corner $(0,0)$ located in ...
- 86.4k
19 votes
Accepted
Coincidence between coefficients of tanh(tan(x/2)) and Chow ring computations?
The integrals $$\int_{\overline{\mathcal{M}}_g} \lambda_{g-1}^3=\frac{|B_{2g}|}{2g}\frac{|B_{2g-2}|}{2g-2}\frac{1}{(2g-2)!}$$ were computed by Faber and Pandharipande in Theorem 4 in their paper Hodge ...
- 796
16 votes
Generating function in graph theory
Consider all trees with labelled vertices $1,\dots,n$, for each tree take a monomial $\prod_{i=1}^n x_i^{\deg(i)-1}$. The sum $F_n$ of these monomials equals $(\sum x_i)^{n-2}$. This may be proved by ...
- 115k
16 votes
Accepted
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
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 ...
- 87.7k
16 votes
Accepted
Matrices of combinatorial sequences that are inverse in two ways
Following up on David's nice answer, there is a different parametrization that makes the pattern much more obvious. Namely, let $s_1,s_2,\dots$ be arbitrary, then you can write $$A=\Big(h_{i-j}(s_1,...
- 86.4k
15 votes
A special type of generating function for Fibonacci
Sure: choose any nonzero value for $a_0$, and write $F(x)=a_0+a_1x+a_2x^2+...$. Expanding $F(x)^n$ gives you a LINEAR equation in $a_n$ as a function of the preceding ones, the coefficient of $a_n$ ...
- 13.9k
15 votes
Accepted
Generating function for Schur polynomials
This is done in my paper The character generator of SU(n). I believe there was an essentially the same previous MO question, but I am unable to find it.
- 53.5k
15 votes
Accepted
How are Sheffer polynomials related to Lie theory?
First, a general set of Sheffer polynomials is not orthogonal with respect to some weight function; for example, the prototypical sequence $p_n(x) = x^n$, which belongs to both special sub-groups of ...
- 11k
15 votes
Recursion for generating functions
That seems really unlikely. For example, $$F(z)=\sum_{k=0}^\infty 2^kz^k = \frac{1}{1-2z}$$ is a rational function, but $$G(z)=\sum_{k=0}^\infty 2^{2^k}z^k$$ has radius of convergence $0$.
- 41.7k
14 votes
Accepted
Congruences Ramanujan-style
More general versions of this have been established: see in particular Theorem 2 of Kiming and Olsson, and for other work see (for example) Locus and Wagner. To answer the question fully, as Ofir ...
- 44.2k
14 votes
Accepted
Properties of some polynomials defined by $P_{n}(x)={e}^{-x}\sum_{k=0}^{\infty}\frac{a_{k,n}{x}^{k}}{k!}$
Noticing that $$a_{k,n} = \frac1{\prod_{i=1}^n (k+2i)} = \frac1{2^n(n-1)!}\int_0^1 (1-t)^{n-1}t^{k/2}\,{\rm d}t,$$ we get $$P_n(x) = \frac{e^{-x}}{2^n(n-1)!} \int_0^1 (1-t)^{n-1} e^{x\sqrt{t}}\,{\rm d}...
- 38.3k
13 votes
Important combinatorial and algebraic interpretations of the coefficients in the polynomial $[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})$
This answer concerns a geometric/Lie-theoretic interpretation of $[n]!_q$. Suppose that $q=p^k$ is a prime power. Then $[n]!_q$ is the number of points in the full flag variety of full flags of ...
13 votes
Accepted
Is the Gauss hypergeometric series ${}_2F_1\bigl(\frac{1}{2},\frac{1}{2};2;t\bigr)$ an elementary function?
Maple does it in terms of complete elliptic integrals $\rm{K}$ and $\rm{E}$ ... $$ {\mbox{$_2$F$_1$}\left(\frac12,\frac12;\,2;\,t\right)}={\frac {4\left( t-1 \right){\rm K} \left( \sqrt {t} \right) ...
- 41.7k
13 votes
Accepted
Finding $\sum_i x_i$ given $\{\sum_i x_i^{2n}\}_{n\in \mathbb{N}}$
If you plot $\log f_n$ versus $n$, with $f_n=\sum_i x_i^{2n}$, then the asymptotic slope for large $n$ will give you the largest of the $x_i$; subtracting that contribution from $f_n$ and repeating ...
- 200k
12 votes
Accepted
Why $\lim_{n\rightarrow \infty}\frac{F(n,n)}{F(n-1,n-1)} =\frac{9}{8}$?
We will compute the generating function, and use the method described in section 2 of this paper. Let $F_{m,n}=F(m,n)$. Consider the generating function $$G(x,y)=\sum_{m=0}^\infty\sum_{n=0}^\infty F_{...
- 2,889
12 votes
Series involving power of the index
There are many ways to prove the formula $$ \sum_{n=1}^{\infty} \frac{n^{n-1}}{n!}(xe^{-x})^n = x.\tag{1}$$ As Alexandre Eremenko noted, one approach is Lagrange inversion. Another can be found at ...
- 17.7k
12 votes
Accepted
Generating function for A261041
Let us derive a formula for $a(n)$. We will employ the inclusion-exclusion principle to get $a(n)$ as the number of partitions not satisfying any of the properties $P_i =$ "elements $i$ and $i+1$ ...
- 38.3k
11 votes
Generating function in graph theory
A good source (despite not being very modern) is Harary, Palmer - Graphical enumeration. A few examples: let $C(x) = \sum_{n = 0}^{\infty} x^n \frac{2^{n(n - 1) / 2}}{n!}$ be the e.g.f. of labelled ...
- 5,752
11 votes
A special type of generating function for Fibonacci
Lagrange–Bürmann formula claims that $$[w^{n-1}]H'(w)(\varphi(w))^n=n[z^n]H(g(z)),$$ where $g(z)$ and $f(w)=w/\varphi(w)$ are compositionally inverse power series without constant term (that is $g(f(w)...
- 115k
11 votes
A special type of generating function for Fibonacci
Another way to state Fedor's answer is Exercise 5.56(a) of Enumerative Combinatorics, vol. 2. Namely, if $G(x)=a_1x+a_2x^2+\cdots$ is a power series (say over $\mathbb{C}$) with $a_1\neq 0$ and $n>...
- 53.5k
11 votes
Matrices of combinatorial sequences that are inverse in two ways
I don't know, but I will point out that, if you specify the entries $A_{(i+1)i}$, then every other entry is uniquely determined by these. The property of being inverse as matrices means that the upper ...
- 161k
11 votes
Finding $\sum_i x_i$ given $\{\sum_i x_i^{2n}\}_{n\in \mathbb{N}}$
If $\sum x_i^2$ is finite, the sum $f(z)=\sum \frac{x_i^2}{1-x_i^2z}$ is a meromorphic function on the complex plane, and we know its Taylor series at 0. Thus we know $f$, hence the poles of $f$, ...
- 115k
11 votes
Accepted
Reference request: Gessel interview's generating function identities
Result 1 can be found in N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, New York, 1981, p. 71. Result 2 follows from a formula of E. M. Wright, though he didn't state it in this form. A ...
- 17.7k
11 votes
Have you seen my power series?
In most situations I know, the equation $$ \Phi(q,t)\Psi(q^{-1},-t)=1 $$ indicates that there is a Koszul algebra $A$ with the "standard" grading $A=\bigoplus_n A_n$ (for which Koszulness ...
11 votes
Have you seen my power series?
Not an answer, but a conjecture. Based on numerical evidence, I would like to venture the conjecture that there is an infinite product formula $$\Psi(q,t) = −\Phi(q,−t) = \frac{1}{\displaystyle\prod_{...
- 3,497
Only top scored, non community-wiki answers of a minimum length are eligible