Generating functions are formed by making a series $\sum_{n\geq 0} a_n x^n$ out of a sequence $a_n$. They are used to count objects in enumerative combinatorics.

learn more… | top users | synonyms

3
votes
2answers
25 views

Extending generating function into series.

There is a reccurent equation: $a_{n+2}-2\cos(\phi)a_{n+1}+a_n=0$ and I must to solve it. I found generating function: $$A(t) = \dfrac{1 - t\cos(\phi)}{1 - 2t\cos(\phi) + t^2},$$ but I can not extend ...
1
vote
0answers
20 views

Generating Function for 2-Associated Stirling Numbers of the Second Kind

I am looking for a paper which explicitly defines a power series for 2-associated Stirling Numbers of the Second Kind. The paper defines the generating function as follows: Let $S_2(n,k)=b(n,k)$ be ...
0
votes
0answers
11 views

Expressing one generating function like combination of another generating functions.

Let A (t), B (t) and C (t) - generating functions for sequences $a_0, a_1, a_2,\dots; b_0, b_1, b_2,\dots and\ c_0, c_1, c_2,\dots$ Express C (t) through A (t) and B (t), if ...
1
vote
1answer
41 views

Showing the equality of two rook polynomials.

I'm reading Barbeau's Polynomials. I've done the following: Taking an arbitrary chessboard $C$ with some of the squares forbidden (with $n$ being the number of squares and $F$ the number of ...
0
votes
1answer
13 views

List primitive elements of GF(2^3) = {0, 1, a, a^2,…, a^6} [on hold]

I need the find the primitive elements of GF(2^3) = {0, 1, a, a^2,....., a^6}, could any one help me out how to go about it?
0
votes
1answer
21 views

Generating-function problem

$A(t),B(t) $ and $ C(t)$ are generating functions for sequences $a_0,a_1,a_2,...;b_0,b_1,b_2,...;c_0,c_1,c_2,\dots$ I do not know how to express C(t) through A(t) and B(t), if $c(n)=\sum_{k = 0}^{[n ...
1
vote
1answer
24 views

Generating functions, sequences with unlimited history of recursion

There is sequence $a_n = a_{n - 1} + 2 a_{n - 2} + \dots + n a_0$, and $a_0 = 1$. I found the generating function for this sequence: $(3t^2-3t+1)/(1-2t)^2$ but I do not know what to do next. How can I ...
1
vote
1answer
32 views

How to find $\sum_{n = 0}^{ \infty} \frac{F_n}{3^n}$

How can I find $$\sum_{n = 0}^{ \infty} \frac{F_n}{3^n}$$ If I know that the generating function for the Fibonacci sequence is $G(t) = \frac{t}{1 - t - t^2}$?
1
vote
1answer
25 views

Generation function for recurrence

Could you tell me how I can find the generation function for recurrence $\sum_{n = 0}^{ \infty} n a_n t^n$ if I know $A(t)$ - generation function for $a_0, a_1, a_2 \dots$ . Thanks
0
votes
1answer
9 views

Uncertain Step in Proving an Identity from Generating Functions

From a lecture: It is required to prove that $ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} $ using generating functions. It goes as follows: The generating function $ g(x) = 1+2x+3x^2+4x^3...= ...
0
votes
0answers
10 views

Generate a list of numbers based on range and quartile

I have the following requirement: A function to create a "list" container to hold a group of data with numValues data, and the range, median, and interquartile ranges ...
2
votes
0answers
27 views

Extinction probability of binomial branching process tends to poisson one.

The folowing is stated and proved in the random graphs book by Luczak, Janson, Rucinski and this is on page 108 in the Giant component section. I can't understand why the conclusion follows from the ...
0
votes
0answers
22 views

Obtaining generating function via Fourier transform

Series coefficient for a function can be obtained via Fourier transform: $$f^{(s)}(0)=\frac{1}{2\pi}\int_{-\infty}^{+\infty} (- i \omega)^s \int_{-\infty}^{+\infty}f(t)e^{i\omega t}dt \, d\omega$$ ...
1
vote
1answer
20 views

Question regarding an algebraic manipulation in GFology

How does the author arrive at the last equality in the first line, i.e.$$\text{why is } [x^k]\frac{1}{1-y(1+x)} = \frac{1}{1-y}[x^k]\frac{1}{1-\left(\frac{y}{1-y}\right)x} \text{?}$$
4
votes
0answers
62 views

Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These ...
4
votes
1answer
103 views

Closed form of $\sum_{k=1}^{n}\binom{n}{k} h^{(n-k)}(0)f^{(k-1)}(0)$

Is there a closed form for: $$\sum_{k=1}^{n}\binom{n}{k} h^{(n-k)}(0)f^{(k-1)}(0)$$ where: $$h(x)=(1-x)^{\alpha}(A-Bx)^{\frac{1}{\gamma}-\alpha}$$ and ...
0
votes
0answers
10 views

What is the closed form for generation function of $\xi(2x)$ (Riemann Xi)?

I wonder whether the following coincidence is just random. Here is the function $-1/x$: If we add infinitely many similar functions with a shift of pi/2 each in both directions, we get $\tan x$. ...
2
votes
1answer
65 views

Can one prove that a generating function has infinitely many coefficients equaling 0?

Given a generating function (ordinary, exponential, or otherwise) such as $$ G(a_n;\, x) := \sum_{n=0}^\infty a_nx^n $$ where one or more $a_n = 0$, is there any way to prove that $G$ does or does not ...
0
votes
0answers
33 views

Special partition of a number $n$

Given any integer $n$, how many ways can it be partitioned in which the number $1$ is not allowed? For instance, if $n=6$, then the partitions obeying the aforementioned rule are $6+0$, $4+2$, $3+3$, ...
0
votes
1answer
26 views

what are generating functions

If I have to explain in simple terms the intuition of what is meant by generating function . e.g.: in my notes I have fibonacci sequence := $0,1,1,2,3,5,8$ . it's recurrence relation ...
2
votes
1answer
57 views

Confusion about Generating Function of Restricted Partitions

I ran into some confusion answering this question. The OP asked for the number of partitions of an integer into odd numbers greater than $1$, with the additional constraint that there are two ...
2
votes
1answer
36 views

Showing equivalence of two binomial expressions

I wish to show that $\sum_{k=0}^n {n\choose k}(\alpha + k)^k (\beta + n - k)^{(n-k)} = \sum_{k=0}^n {n\choose k}(\gamma + k)^k (\delta + n - k)^{(n-k)}$ given that $\alpha + \beta = \gamma + \delta$. ...
1
vote
1answer
54 views

How to prove the identity $\sum_{n\in\mathbb{Z}}J_n(x)\,J_{n+m}(x) = 0$ using the Bessel generating function?

I need some help proving the following identity: $$\sum_{n\in\mathbb{Z}}J_n(x)\,J_{n+m}(x) = 0.$$ I wonder if it is possible to use the generating function identity: $$ g(x,t) = ...
0
votes
0answers
42 views

Evaluating a multiplicity factor

Let $f(t_1,\dots, t_n)$ be a function that doesn't depend on the order of its arguments: $$f(t_1,\dots,t_n)=f(\text{sorted}(t_1,\dots,t_n))$$ Here $t_i$ are non-negative integers. I want to find the ...
0
votes
0answers
20 views

Prove a complex function to be convex

I have a function and want to prove that it is convex when $0 \leq x \leq 1$: \begin{equation} f(x)=\frac{b1g'(x) f_1(x)^{n-2}+g'(1) \gamma}{g'(1) ( \gamma+b1) } \end{equation} and \begin{equation} ...
5
votes
3answers
98 views

Counting problem: generating function using partitions of odd numbers and permuting them

We have building blocks of the following lengths: $3, 5, 7, 9, 11$ and so on, including all other odd numbers other than $1$. Each length is available in two colors, red and blue. For a given number ...
2
votes
2answers
59 views

motivation for $1/(1-x)$ used in generating functions

A closed form for the infinite series $1+x+x^2+\ldots+x^n$ works out quickly like this: $S_n = 1+x+x^2+\ldots+x^n$ $xS_n = x+x^2+x^3\ldots+x^{n-1}$ ...
1
vote
1answer
29 views

Partitions without twice odd numbers and where every odd number appears at most once

Let $A=\{2,6,10,14,\ldots\}$ be the set of integers that are twice an odd number. Prove that, for every positive integer $n$, the number of partitions of $n$ in which no odd number appears more than ...
3
votes
1answer
33 views

Explaining the coefficients of matching polynomials

Matching polynomials are generating functions that tells us the number of $k$-matching (meaning choosing of $k$ independent/non-adjacent edges) in the graph say $G$. Farrell et al., "On matching ...
0
votes
0answers
18 views

How do generating function created from solution of system of polynomials

What are the examples of generating function derived from solution of system of polynomials? how to count the number of points in varieties which are solution of system of polynomials? From Wiki, ...
1
vote
2answers
91 views

Binomial theorem / Generating function

I had trouble figuring out if the following equality holds by applying the binomial theorem and using generating functions. Could anyone please shed some light? Any help is greatly appreciated. $${n ...
1
vote
2answers
29 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
1
vote
2answers
45 views

Generating function for number of integer solutions, no computer

How do you solve a Generating function for the number of integer solutions with no computer? Use a generating function to solve the number of integer solutions for $$x_1+x_2+x_3=17$$ Where ...
0
votes
0answers
42 views

Generating function to calculate number of ways of distributing $10$ or less items to $3$ people.

There is a container of 10 identical chocolate frogs and three students, Adam, Bob, and Charles, are to be given some of these chocolate frogs, but not necessarily all of the chocolate frogs. ...
4
votes
2answers
74 views

Geometric Generating Functions

Let $p(t) = t^3 + Ft^2 + Et + V$, where $F,E,V$ are the number of faces, edges, and vertices of a cube, respectively. Factor $p(t)$ and explain your results in terms of generating functions. A hint ...
2
votes
1answer
55 views

More Generating Functions problems

(a) For this problem, define a nonstandard die as a 6-sided die that is equally likely to come up on each side, but has a different set of numbers than the usual 1,2,3,4,5,6 on its sides. A standard ...
1
vote
2answers
51 views

Stuck on Generating Functions

1) Determine how many ways Brian, Katie, and Charlie can split a 50 dollar dinner bill such that Brian and Katie each pay an odd number of dollars and Charlie pays at least 5 dollars . 2) Determine ...
2
votes
2answers
44 views

Number of partitions of number n and number 3n

On some exam i had task "Show that number of partitions of $n$ on four parts is equal to number of partitions of number 3n on four parts, but each part not greater than $n-1$" So first is $$n = a + ...
2
votes
1answer
78 views

What's the shape of this “addsTo” function …?

Note that in this combinatronics question, How many lists of 100 numbers (1 to 10 only) add to 700? I was asking: For an array of 100 numbers, each 1 to 10 inclusive, and the total is T - how many ...
0
votes
2answers
49 views

Showing that a generating function is equivalent to some fraction

I am working with generating functions and am required to prove that the generating function for the sequence $\{a_k\}$ where $a_k = (-8)^k$ for all integers $k\geq0$ is $\cfrac{1}{1+8x}$ and I have ...
0
votes
1answer
30 views

Finding number of ways of distributing toys without generating function

Suppose I want to distribute $30$ toys in $30$ boxes. Any number of toys (from the given toys) can be kept in any box. In how many ways can this be done? I know how to solve this problem using ...
3
votes
2answers
76 views

Find the generating function of the sequence $a_n = \sum\limits_{k=0}^n k(k-1)$

Find the generating function of the sequence $ a_n =\sum\limits_{k=0}^n k(k-1)$ My try: Let's assume $k(k-1)$ is genereated by $F(x)$ then $a_n$ is generated by $\frac{F(x)}{1-x}$ (that's a ...
1
vote
1answer
59 views

Prime number generation - speed comparison

"Efficient prime number generating" leads to some algorithms being displayed as "fast". Up to PG7.8 which does takes 65786 seconds to generate the prime numbers > ...
0
votes
1answer
38 views

How many sequences are there (Using generating functions)

How many sequences are there, with the length of $n$ above $\left\{0,1,2,3,4\right\}$ such that the digits sum is $9$. The solution offers the following generating function for the problem: $$ ...
1
vote
1answer
50 views

Learning about generating functions and sequences.

I've been reading through other questions on this site and external resources for a few hours now but seem to be having a mental block, probably through some elementary misunderstanding of my course ...
0
votes
1answer
21 views

Generating function question, seemingly lacking information

I have to prove that a generating function for the sequence $\{a_k\}$ where $a_k = (-8)^k$ for all integers $k\geq 0$ is $\cfrac{1}{1+8x}$. But I don't have any information on what $x$ is. Nor is ...
2
votes
0answers
78 views

Stirling numbers and Power Group Enumeration

The following question is a reference request concerning a derivation of the EGF for the Stirling numbers of the second kind by Power Group Enumeration / Burnside's Lemma, which is $$\sum_{n\ge 0} ...
2
votes
0answers
66 views

Partitions of 200 into at most 6 parts.

I'm working on a partition problem, and I got an answer that is simply staggering, and I was hoping for someone to verify whether my answer is correct. The question was simply to determine the number ...
2
votes
1answer
49 views

Number of integral soultions to linear equations without unit coefficients

To determine the number of integral solutions for the linear equation $$ x_1+x_2+x_3+\cdots+x_k = N$$ we have an expression $$ ^{N+k-1}C_{k-1}$$ But I want to know if the coefficients of ...
3
votes
0answers
65 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...