5
votes
3answers
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 ...
1
vote
1answer
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, ...
2
votes
2answers
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$ ...
1
vote
1answer
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: ...
2
votes
1answer
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 ...
3
votes
1answer
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 & = & ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
39 views

Generating function satisfying a second degree equation

I got this problem in an exercise list: Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation: $$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, ...
3
votes
1answer
43 views

A bijection defined on the set of configuration of lamps

Consider $n$ lamps clockwise numbered from $1$ to $n$ on a circle. Let $\xi$ to be a configuration where $0 \le \ell \le n$ random lamps are turned on. A cool procedure consists in perform, ...
6
votes
4answers
130 views

The number of permutations of $\{1,2,\ldots,n\}$ that have exactly one ascent (rise).

Sloane's OEIS A000295 counts the number of $n$-permutations with exactly one ascent. For example $a(3)=4$ because we have: $1\wedge32$, $21\wedge3$, $2\wedge31$, $31\wedge2$ where I have marked the ...
1
vote
1answer
29 views

Products of n exponential generating functions

So I am using exponential generating functions and have a question about taking the product of more than 2 exponential generating functions. I know that the product of 2 exponential generating ...
3
votes
2answers
50 views

Generating Function for the number of ways representing positive integer with odd numbers

I had an exam and this question struck me out of nowhere, making me sad :) Let $f(n)$ denote the number of possibilities representing $n$ using odd positive single-digit numbers $[1,3,...,9]$ For ...
2
votes
1answer
59 views

Generating function for picking j balls without replacement from an urn

In an urn, each balls is labeled with one of $\{0,1,2,...,k\}$. For each $i\in{0,1,2,...,k}$, there are exactly $n_i$ balls labeled $i$. Let $f(x)=\sum\limits_{i=0}^k n_ix^i$. Let ...
0
votes
2answers
114 views

Combinatorics: Binary Strings

Are the these 2 binary generation expressions equal? If so, how do I simplify my answer to match the solution's? Question: The set of binary strings where the length of each block of 0s is divisible ...
0
votes
1answer
27 views

Prove equilvalence of generating series with compositions.

weight function: w(c1, ..., ck) = c1 + ... + ck and w(ci) = ci, 1<=i<=k Could someone explain to me what the N notation stand for? My take would be that the left N notation represents a set ...
1
vote
1answer
41 views

How many ways you can make change for an amount N using A and B monets.

I encountered a quite interesting problem. The question is: How many ways you can make change for an amount N using monets of value A and B, knowing that GCD(A,B)=1. Any idea how to solve this? It ...
4
votes
1answer
69 views

Extracting a coefficient from a generating function

Background: I am working on an exercise relating to Skolem $k-$subsets with index $k$ in Goulden and Jackson's Combinatorial Enumeration text and they broke it down to finding the coefficient of $x^n$ ...
2
votes
1answer
45 views

Number of nodes with an even number of children in an ordered tree (AKA Plane Planted Tree)

I am looking for verification for my attempt at the solution. I have found that my answer disagrees with an answer I found here: Extract Coefficients From A Function Problem at hand: For a plane ...
12
votes
1answer
243 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
2
votes
0answers
57 views

Puzzle with character order

Suppose I have 3 letters a, b, c and I want to find the minimum length of a string that uses all the double combinations of the aforementioned letters. How should I do it or how are such problems ...
2
votes
1answer
41 views

Number of ways to fill a bag of weight $N$ with fruits - Generating series question

How many ways are there to fill a bag (maximum of weight $N$) with watermelons, apples, and grapes, where the number of apples has to be at least the number of watermelons? The weights are given as ...
2
votes
1answer
166 views

Generating function for vertices distance from the root in a planar tree

I need you help to solve this problem: Consider a planar tree with $n$ non-root vertices. Give a generating function for vertices distance $d$ from the root. Proof that the total ...
1
vote
2answers
169 views

Generating function for planted planar trees

I need your help to solve this problem : Give a generating function for planted planar trees with all degrees odd. Show that the number of such trees with $2k+1$ non-root vertices is ...
3
votes
1answer
63 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...
0
votes
0answers
33 views

Generating function counting quaternay sequence.

I have the following problems: $1.$ Calculate the number of the n-digits Quaternary sequence containing even $"2"$ and $"1"$ and at least one $"3"$. (When a sequence is made by the digits $1,2,3,4$) ...
4
votes
2answers
104 views

Formula for the number of integer solutions of an equation (using generating functions)

Let $a_n$ be the number of integer solutions of $$i+3j+3k=n$$ where $i \geq 0, j \geq 2, k \geq 3$. I want to use the generating function of $(a_n)_{n \in \mathbb N}$ to get a formula for $a_n$. We ...
6
votes
0answers
96 views

Specializations of elementary symmetric polynomials

Let $\mathcal{S}_{x}=\{x_{1,},x_{2},\ldots x_{n}\}$ be a set of $n$ indeterminates. The $h^{th}$elementary symmetric polynomial is the sum of all monomials with $h$ factors \begin{eqnarray*} ...
1
vote
0answers
47 views

Deriving combinatorial coefficients for a series related to the binomial series (but with a third index)

I have a problem that reminds me a lot of the binomial coefficients, and I'm wondering how to compute future elements with a nice formula, in the same way that $\binom{n}{k}$ is used as a symbol ...
3
votes
1answer
81 views

Prove combinatorics problem $\sum_{k=0}^n {2k \choose k}{2n-2k \choose n-k}=4^n$ using generating functions

We need to prove for homework using the generating function method that $$c_n:=\sum_{k=0}^n {2k \choose k}{2n-2k \choose n-k}=4^n$$ I figured out we can start with function $$f(x)=\sum_{n=0}^\infty ...
0
votes
0answers
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 ...
-1
votes
2answers
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$.
1
vote
1answer
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 ...
3
votes
1answer
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.
3
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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}$$
1
vote
2answers
69 views

Number of integer solutions by generating functions method

I'm stuck in the middle of a problem and not sure where to go next. The original problem is: Find the number of integer solutions to the equation $$2x + 3y + 4z + w + s + t = n$$ with $$0 \le w ...
0
votes
1answer
33 views

Exponential generating function for number of 10 length sequences built from the alphabet, with some restrictions

I've got the following homework question. If anybody could possibly point me in the right direction, that would be great: Suppose X is a sequence with 10 terms built from 26 letters {a, b, c, ..., ...
2
votes
2answers
74 views

number of solutions to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ via generating function?

I will be very happy to understand how to solve this problem with generating function: How many solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 31$$ where $x_i$ is a nonnegative ...
1
vote
2answers
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 ...
5
votes
2answers
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 ...
0
votes
2answers
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 ...
3
votes
2answers
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), ...
0
votes
1answer
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 ...
4
votes
1answer
103 views

Proving a combinatorial identity “directly”

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 ...
1
vote
2answers
74 views

Use generating functions to find the number of partitions of $n>1$ that have an odd number of even parts $k=1,…,10$

Here are some examples where we find $f(n)$ - the number of partitions that satisfy our condition: $\boldsymbol{2} = (1+1) \rightarrow \boldsymbol{f(2)=0} $ $\boldsymbol{3} = (1+1+1) = ...
1
vote
2answers
54 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...