Questions tagged [generating-functions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
18 views

How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?

The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion: $$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
-2
votes
2answers
365 views

Are mathematical functions used in computer science? [closed]

Well, I know the difference between functions used in math and C language. But what are those specific areas where mathematical functions are used?
3
votes
1answer
54 views

How to solve this recurrence involving binomial coefficients?

How to solve the following recurrence involving binomial coefficients, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers ($n \ge k \ge 0$)? $$ A(n,k) = A(n-1,k) +...
1
vote
1answer
72 views

Advantage of using generating functions in analyzing an algorithm

I'm reading through the first chapters of "Introduction to the analysis of algorithm" by Sedgewick. I wasn't familiar with the use of generating functions, and complex analysis in general to analyse ...
1
vote
1answer
41 views

Obtaining a recurrence from a rational generating function

Looking at some Generating functions of a series, I have conjectured - If $G(x) \ =\ \frac{1}{1-x^{t_1}-x^{t_2}-...-x^{t_n}}$, then the recurrence equation of the the series is - $a_n = a_{n-t_1}+...