Questions tagged [generating-functions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers

Data structure for arguments in Arrow functions in JS

As per the rules of JS, Arrow functions don't have an argument Object, like a regular function inside JS. But it is also true, that we can pass arguments to the <...
Karan Bakshi's user avatar
1 vote
1 answer

Number of ways to make change in o(k), where k is number of coins

Godd afternoon, We have set C of k coins; For example C = (2, 3) We have positive integer n. In how many ways we can represent n using those coins? Example: If n = 12; C = (2, 3) we can represent 12 ...
yomol777's user avatar
  • 111
0 votes
1 answer

How does one define transcendental numbers (such as Pi) in theory of general recursive functions

On a turing machine and in the lambda calculus one can define transcendental numbers such as Pi, the golden ratio, etc. These are computatible functions with 0-arity that never terminate. In the ...
RFV's user avatar
  • 141
2 votes
1 answer

Solving the recurrence $ T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)} $

What's the (asymptotic) solution of the following recurrence? $$ T(n) = \frac{T(n-1) + T(n-3)} {T(n-2)}. $$ I tried to solve this with generating functions to find an accurate bound.
user avatar
1 vote
0 answers

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_{...
Shreck Ye's user avatar
  • 145
-2 votes
2 answers

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?
Bilal Sheikh's user avatar
3 votes
1 answer

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) +...
hengxin's user avatar
  • 9,501
2 votes
1 answer

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 ...
user8469759's user avatar
1 vote
1 answer

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}+...
Mr. Sigma.'s user avatar
  • 1,293