Search Results

Apply the technique described in this blog post to $F(x) F(y)$, then to $x F(x) F(y)$. The key observation here is that one can compute Hadamard products of rational functions using the residue theor …

The PET (if you're referring to the same thing I'm thinking of) is a special case of Burnside's lemma, which still applies here - but the group is slightly larger. Instead of the group $C_4$ of rotat …

I figured that's the question you wanted to ask. The relation $$\sum_{k=0}^{n} (-1)^k {n \choose k} a_k = b_n$$ for all $n$ (you did not specify this; it was very unclear) is equivalent to the rela …

In addition to Wilf I also recommend Graham, Knuth, and Patashnik's Concrete Mathematics for these kinds of questions. GKP has a lot of good material on, for example, techniques for estimating the gr …

Yes. Take the companion matrix $M$ of the characteristic polynomial of your original recurrence. Then the squared recurrence satisfies a recurrence with the characteristic polynomial of the symmetric …

The bijection definition is fine, although it's not a very nice group. One might also consider the group generated by all transpositions on {1, 2, ...}, which is the subgroup of all bijections that f …

The number ${n \choose k}$ of $k$-element subsets of an $n$-element set and the number $\left( {n \choose k} \right)$ of $k$-element multisets of an $n$-element set satisfy the reciprocity formula $\ …

The category of combinatorial species is equivalent to the category of sequences $F_n$ of $S_n$-sets, where $S_n$ is the symmetric group on $n$ letters. Of course $[n] = \{ 1, 2, 3, ... n \}$ is itsel …

That's very poor wording, so let me be more precise. Suppose $L$ is an unambiguous regular language on an alphabet $\{a_1, \dots, a_n\}$, and suppose to each letter of the alphabet we associate two n …

$\theta$ could be any permutation of the form $\alpha (\beta \alpha) \alpha^{-1}$; in other words, it could be any permutation conjugate to $\beta \alpha$, so knowing $\beta \alpha$ tells you only the …

For graphs $G, H$, let $G \times H$ denote the graph with vertex set $V(G) \times V(H)$ and such that $(g_0, h_0)$ and $(g_1, h_1)$ are connected by an edge iff $g_0$ and $g_1$ are connected by an edg …

I think you've been misled by the standard description of combinatorial species. It's cleaner to think of (exponential) generating functions in one variable as being categorified by analytic functors, …

The number of solutions is relatively straightforward to compute (although I don't have anything intelligent to say about the computational complexity of the method I'm about to propose). The number …

For fixed $k$ and large $n$ this is pretty doable. You want to find solutions to $$x_1 + x_2 + ... + x_k = n$$ where $x_1 \ge x_2 \ge ... \ge x_k$. Letting $y_i = x_i - x_{i+1}$ and $y_k = x_k$, t …

Okay, so it's not quite a duplicate because I guess you're asking about initial conditions as well. The generating functions of the sequences $a_n$ which have this property are called $\mathbb{N}$-re …