# Tagged Questions

86 views

### Make $n$ cents with $1$-cent, $2$-cent, and $3$-cent coins

I encountered the following problem in Herber Wilf's book Generatingfunctionology: Prove that, in country that has $1$-cent, $2$-cent, and $3$-cent coins only, the number of ways of changing ...
61 views

### How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents)?

How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents), between four children, with the following restriction: A child receives at leat 1 penny and 3 nickels The children 2,3 and 4, ...
100 views

### Finding the number of solutions to $x+2y+4z=400$

My question is how to find the easiest way to find the number of non-negative integer solutions to $$x+2y+4z=400$$ I know that I can use generating functions, and think of it as partitioning $400$ ...
64 views

### Count the number of ways n different-sided dice can add up to a given number

I am trying to find a way to count the number of ways n different-sided dice can add up to a given number. For example, 2 dice, 4- and 6-sided, can add up to 8 in 3 different ways: ...
52 views

### Simplifying a generating function in two variables with two binomial coefficients

I'm trying to to make the below expression simpler, and it would be great if it could be expressed as something like $(x+y)^k$. $$\sum_{i=0}^k\binom{n+1}i\binom{m+1}{k-i}x^iy^{k-i}$$ The number ...
48 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
51 views

### generating function combinatorics solution

I am studying generating functions in combinatorics, and came across a problem that has already been posted here: Generating function and combinatorics =x^10(1-x^6)^10 * (1+x+x^2....)^10 I ...
60 views

### Partitions applications in physics

Is there any direct application of all developments related to partitions? I am specially interested in physics but cryptography or other mostly theoretical areas would also be a good answer. By ...
39 views

58 views

### Two generating functions are combined, how are the coefficients for the combined generating function determined?

I have a function or operation $f(x)$ that takes integer inputs $0\leq x_\mathrm{in}<2^N$ to a limited set of integer outputs $x_\mathrm{out}\in[-N,N]$. I know that if all inputs are computed then ...
61 views

### Closed form of generating function of sequence [closed]

I am looking for a simple closed form for the generating function of the sequence $a_n = n^2$.
48 views

### Proving a recurrence relationship for a sequence

I have an assignment question which I have spent hours working on without getting even close to the answer, and would really appreciate any pointers that could help me figure it out. QUESTION Let ...
67 views

### How to prove this identity?(perhaps related to partition)

How to prove this identity? $$\sum_{n\ge 0} \frac{x^{n^2}}{(1-x)(1-x^2)\cdots(1-x^n)} = \frac{1}{\prod_{k \ge 0}(1-x^{5k+1})(1-x^{5k+4})}$$ Maybe the method using generating functions is good.
38 views

### Find the Generating Function with respect to n

The following is a problem from Chapter 2 of Herbert Wilf's generatingfunctionology: Let $S$ and $T$ be two fixed sets of nonnegative integers. Let $f(n,k,S,T)$ denote the number of ordered ...
49 views

### partitioning numbers from 1 to n in 4 non-empty subsets so no subset has 2 consecutive numbers.

Attempt: We have to find the number of ways to partition the numbers 1 to n into four non-empty subsets so that none of them are empty. let $f(n)$ be the way to do that and let $f'(n)$ be the way to ...
45 views

### calculate the proportion of n-node trees whose root has only one or two subtrees.

Could we use combinatorics and generating functions to calculate the proportion of n-node trees whose root has only one or two subtrees? Here is what I tried: The combinatorial construction for the ...
50 views

### is there a method for generating functions to construct recurrence relations?

I am starting to read about combinatorics and generating functions and generally I see they use generating functions to get a closed form formula for a recurrence relation. I have some questions about ...
59 views

### Closed form for nth term of generating function

How would I find the closed form for the $n^{th}$ term of a sequence? Is there a general formula I can follow for these types of problems? Taking this sequence for example... $$\frac{x^5}{(1-x)^4}$$
69 views

115 views

### Kind of basic combinatorical problems and (exponential) generating functions

I have a pretty straightforward combinatorical problem which is an exercise to one paper about generating functions. How many ways are there to get a sum of 14 when 4 distinguishable dice are ...
328 views

### Applications of generating functions to number theory

I am familiar (at least at a cursory level) with the extensive role generating functions play in the theory of partitions. What are some other prominent applications of generating functions to number ...
44 views

### Combinatorics-Generating function

5 pirates find 3000 gold coins. In how many ways they can distribute them, if the captain gets at least 500 and not more then 2000 coins. the rest get at least 150 but not more then 1000 coins.(each ...
101 views

### Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
64 views

### Differences Exponential and Ordinary Generating Functions

I am trying to understand conceptually the differences between ordinary generating functions (OGF$=1+x+x^2+\ldots$ ) and exponential generating functions (EGF$=1+x+\frac{x^2}{2!}+\ldots$ ) when it ...
This is a homework problem. In the first part of the problem, I managed to use a combinatorial problem to prove the following identity: $\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$ But ...