All Questions
Tagged with integer-partitions generating-functions
210
questions
0
votes
1
answer
83
views
Generating function and currency
We assume that we have a country's currency that contains three coins worth 1, 3, and 4. How many ways can we get an amount of $n$ using these three pieces?
In others words what is the number of ...
- 37
1
vote
1
answer
49
views
Generating function of partitions of $n$ in $k$ prime parts.
I have been looking for the function that generates the partitions of $n$ into $k$ parts of prime numbers (let's call it $Pi_k(n)$). For example: $Pi_3(9)=2$, since $9=5+2+2$ and $9=3+3+3$.
I know ...
2
votes
1
answer
155
views
About the product $\prod_{k=1}^n (1-x^k)$
In this question asked by S. Huntsman, he asks about an expression for the product:
$$\prod_{k=1}^n (1-x^k)$$
Where the first answer made by Mariano Suárez-Álvarez states that given the Pentagonal ...
2
votes
1
answer
38
views
Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$.
Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$, and that it equals $(1+q)(1+q^{3})\cdot\cdot\cdot(1+q^{2n-1})$.
For the first part, ...
- 795
0
votes
0
answers
81
views
Need help with part of a proof that $p(5n+4)\equiv 0$ mod $5$
Some definitions:
$p(n)$ denotes the number of partitions of $n$.
Let $f(q)$ and $h(q)$ be polynomials in $q$, so $f(q)=\sum_0^\infty a_n q^n$ and $h(q)=\sum_0^\infty b_n q^n$. Then, we say that $f(q)\...
- 350
1
vote
0
answers
34
views
Proving an Identity on Partitions with Durfee Squares Using $q$-Binomial Coefficients and Generating Functions
Using the Durfee square, prove that
$$
\sum_{j=0}^n\left[\begin{array}{l}
n \\
j
\end{array}\right] \frac{t^j q^{j^2}}{(1-t q) \cdots\left(1-t q^j\right)}=\prod_{i=1}^n \frac{1}{1-t q^i} .
$$
My ...
- 195
0
votes
0
answers
43
views
Find generating function for the number of partitions which are not divisible by $3$. [duplicate]
I'm trying to find the generating function for the number of partitions into parts, which are not divisible by $3,$ weighted by the sum of the parts. My idea is that we get the following generating ...
- 121
0
votes
1
answer
81
views
Integer partitions with summands bounded in size and number
This book says it's easy, but to me, it's not. :(
As for 'at most k summands', in terms of Combinatorics, by using MSET(),
$$ MSET_{\le k}(Positive Integer) = P^{1,2,3,...k}(z) = \prod_{m=1}^{k} \frac{...
- 185
1
vote
0
answers
60
views
Generating Function for Modified Multinomial Coefficients
The multinomial coefficients can be used to expand expressions of the form ${\left( {{x_1} + {x_2} + {x_3} + ...} \right)^n}$ in the basis of monomial symmetric polynomials (MSP). For example,
$$\...
- 51
4
votes
1
answer
339
views
Why do Bell Polynomial coefficients show up here?
The multinomial theorem allows us to expand expressions of the form ${\left( {{x_1} + {x_2} + {x_3} + {x_4} + ...} \right)^n}$. I am interested in the coefficients when expanding ${\left( {\sum\...
- 51
1
vote
0
answers
47
views
Congrunces of partitions into distinct parts
Let $P_{d}(n)$ denote the number of partitions of n into distinct parts. The generating function of $P_{d}(n)$ s given by:
$$ \sum_{n \geq 0}P_{d}(n)q^{n}= \prod_{n \geq 0} (1+q^{n}).$$
Now let $P_{2,...
- 21
0
votes
1
answer
76
views
Generating function of number of partitions of $n$ into all distinct parts
I am trying to grasp this example from the book A Walk Through Combinatorics:
Show that $\sum_{n \ge 0} p_d(n)x^n = \prod_{i \ge 1}(1+x^i)$ where
$p_d$ stands for partitions of $n$ into all distinct ...
- 309
1
vote
1
answer
319
views
Generating function of number of partitions of $n$ into parts at most $k$
I am trying to grasp the intuition behind this example.
Show that $\sum_{n \geq 0} p_{\leq k}(n)x^n = \prod_{i=1}^k \frac{1}{1-x^i}$
where $p_{\leq k}(n)$ denotes the number of partitions of the ...
- 309
3
votes
1
answer
111
views
Finding the number of integer composition using only a specific pair of numbers [closed]
I want to find the number of integer compositions of 19 using numbers 2 and 3.
If I wanted to find the number of integer compositions of 19 using 1 and 2, I could write it as $F(n)=F(n-1)+F(n-2)$ ...
- 309
1
vote
1
answer
53
views
The product of components in the partition of a number.
Let $f(n,k)$ be the sum of expressions of the form $x_1 \cdot x_2 \cdot \ldots \cdot x_k$, where the sum counts over all solutions of the equation $x_1 + \ldots + x_k = n$ in natural numbers. Find ...
- 675
4
votes
1
answer
134
views
The total number of all different integers in all partitions of n with smallest part $\geq 2$
I want to show that the total number of all different integers in all partitions of $n$ with smallest part $ \geq 2$ is $p(n-2)$.
Example: partitions of $7$ with smallest part $ \geq 2$ are (7), (5,2),...
- 53
2
votes
2
answers
168
views
Finding the generating function.
Find the generating function for the number of solutions for the equation $x_1+x_2+x_3+x_4 = n$, where $x_1,x_2,x_3,x_4\geq1$, and $x_1 < x_2$.
My attempt so far: I have tried putting a $y$ value ...
- 165
1
vote
1
answer
143
views
Generating function of ordered odd partitions of $n$.
Let the number of ordered partitions of $n$ with odd parts be $f(n)$. Find the generating function $f(n)$ .
My try : For $n=1$ we have $f(1)=1$, for $n=2$, $f(2)=1$, for $n=3$, $f(3)=2$, for $n=4$, $...
user1137804
1
vote
1
answer
92
views
Identity about generating function related to binary expression of integers
For any nonnegative integer $n$, let $\mu(n)$ be $1$ if the binary expression of $n$ contains even number of ones; and $-1$ if the binary expression of $n$ contains odd number of ones. For example, $\...
user1089451
1
vote
1
answer
96
views
Representation of number as a sums and differences of natural numbers
Lets consider all the combinations of:
$$1+2+3+4=10,\ \ 1+2+3-4=2,\ \ 1+2-3+4=4,\ \ 1+2-3-4=-4, $$
$$1-2+3+4=6,\ \ 1-2+3-4=-2,\ \ 1-2-3+4=0,\ \ 1-2-3-4=-8,$$
$$-1+2+3+4=8,\ \ -1+2+3-4=0,\ \ -1+2-3+4=2,...
- 1,818
1
vote
0
answers
49
views
Generating function of sequence related to binary expression of integer as follows
For any $n \in \Bbb N$, let $O(n)$ be $1$ if the binary expression of $n$ contains even number of ones; and $-1$ if the binary expression of $n$ contains odd number of ones, and $Z(n)$ be $1$ if the ...
user1089451
0
votes
0
answers
178
views
Generating function of integer partitions at most m parts
The generating function of partition integer with the maximum number is m is $$
\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}
$$
It's quite easy to understand if you expand it $$
(1+x+x^2+\cdots)(1+x^2+x^4+\...
2
votes
1
answer
178
views
two-variable generating function for all number partitions
I'm stuck to solve the problems below:
(a) Let $p(n, k)$ be the number of partitions of $n$ into exactly $k$ parts. Show that
$$
\sum_{n, k \geq 0} p(n, k) x^{n} t^{k}=\prod_{i \geq 1} \frac{1}{1-x^{i}...
- 143
1
vote
3
answers
73
views
Partitions without repetition
I want to know how many partitions without repetition 19 has. I know I should see the coefficient of $x^{19}$ in $$\prod_{k=1}^\infty(1-x^k),$$
but i'm having trouble finding it. Ay hint?
- 153
1
vote
1
answer
86
views
Number of partitions with distinct even parts/parts with multiplicity $\leq 3$
I am supposed to solve a problem regarding partitions of $n \in \mathbb{N}$ into:
distinct even parts
parts with multiplicity $\leq 3$
I am supposed to prove that 1. and 2. are equal.
So I tried ...
- 333
7
votes
1
answer
167
views
How to prove the following resummation identity for Erdős–Borwein constant?
Question:
How to prove
$$\sum_{m=1}^{\infty}\left(1-\prod_{j=m}^{\infty}(1-q^j)\right) = \sum_{n=1}^{\infty}\frac{q^n}{1-q^n} \tag{1}$$
for all $q \in \mathbb{C}$ such that $\left|q\right| < 1$?
...
- 3,132
1
vote
0
answers
49
views
Coefficients in Gaussian polynomials [duplicate]
Let
$$
\binom{n}{k}_{\!q} = \frac{(1-q^n) \cdots (1-q^{n-k+1})}{(1-q) \cdots (1-q^k)}
$$
be the Gaussian polynomials. For example,
$$
\binom{6}{3}_{\!q} = 1+q+2q^2+3q^3+3q^4+3q^5+3q^6+2q^7+q^8+q^9.
$$
...
- 175
-3
votes
4
answers
129
views
Find a minimal set whose elements determine explicitly all integer solutions to $x + y + z = 2n$
Is there a way to exactly parameterise all the solutions to the equation $x + y + z = 2n$, for $z$ less than or equal to $y$, less than or equal to $x$, for positive integers $x,y,z$?
For example, for ...
- 67
0
votes
1
answer
138
views
Infinite product expression of partition function
I'm working on a problem (specifically, I'm using an exam paper without course notes to prepare for a course starting in September),
Define the partition function $P(q)$ and give its infinite product ...
- 2,281
1
vote
1
answer
74
views
Counting Partitions of $k$ into $j$ distinct parts, with sizes restricted by a sequence.
This question has come up in my research, but since I usually do not do combinatorics, I am struggling to find out any information regarding these sequences of numbers.
Let $L_n = L_1, L_2\dots$ be a ...
- 2,349
1
vote
1
answer
164
views
Prove that number of partitions of $n$ into parts $2,5,11$ modulo $12$ is the same as the number of partitions into distinct parts $2,4,5$ modulo 6
Let $A(n)$ denote the number of partitions of the positive integer $n$ into parts congruent to $2$, $5$, or $11$ modulo $12$. Let $B(n)$ denote the number of partitions of $n$ into distinct parts ...
- 1,248
0
votes
0
answers
75
views
Question about number of generating functions
I know that the generating function for the number of integer partitions of $n$ into distinct parts is
$$\sum_{n \ge 0} p_d(n)x^n = \prod_{i \ge 1}(1+x^i)$$
I'm trying to use this generating function ...
- 27
0
votes
0
answers
141
views
OGF for partitions of integer r-N into even parts less than or equal to 2m (N is some integer that may depend on m).
Let $a_r$ be the number of partitions of the integer r-N into even parts, the largest of which is less than or equal to 2m, where N is some integer that may depend on m. Find the ordinary generative ...
- 1
3
votes
2
answers
212
views
Integer partition generating functions problem
This is a homework question so I'd prefer to not receive a full solution but rather a hint.
The question is that $r_3(n)$ denotes the number of partitions of an integer $n$ into parts that are not ...
- 296
2
votes
1
answer
112
views
Integer partitions using generating functions
For each natural number $ n $ we consider the equation
$$x_{1}+2x_{2}+\dots+nx_{n}=n$$
Where $x_{1},\dots,x_{n}$ are nonnegative integers. Prove that this equation has the same number of solutions ...
user1009942
1
vote
3
answers
141
views
Number of integer solutions of linear equation.
I have the following problem.
Assume we have an unlimited number of blocks of 1cm, 2cm and 3cm height. Ignoring the position of the blocks, how many towers of 15cm height can we build?
I know I must ...
- 51
1
vote
2
answers
327
views
Partitions into distinct even summands and partitions into (not necessarily distinct) summands of the form $4k-2,k\in\Bbb N$
Prove that the number of ways to partition $n\in\Bbb N$ into distinct even summands is equal to the number of ways of partitioning $n$ into (not necessarily) distinct summands of the form $4k-2,k\in\...
- 4,670
2
votes
1
answer
86
views
Demonstration for the equal number of odd and unequal partitions of an integer
I'm having some problems trying to resolve one exercise from The art and craft of problem solving by Paul Zeitz. What this problem asks you is to prove that $F(x)$ is equal to 1 for all $x$, where
$$F(...
- 73
1
vote
2
answers
161
views
Recurrence relations in the generating function of binary partitions
Let $b(n)$ denote the number of binary partitions of $n$, that is, the number of partitions of $n$ as the sum of powers of $2$. Define
\begin{equation*}
F(x) = \sum_{n=0}^\infty b(n)x^n
= \prod_{n=0}^\...
- 2,238
1
vote
2
answers
193
views
What is the closed form solution to the sum of inverse products of parts in all compositions of n?
My question is exactly as in the title:
What is the generating function or closed form solution to the sum of inverse products of parts in all compositions of $n$?
This question was inspired by just ...
- 171
0
votes
1
answer
848
views
What is the generating function for the number of partitions of an integer in which each part is used an even number of times?
What is the generating function for the number of partitions of an integer in which each part is used an even number of times? I'm trying to prove the number of partitions of an integer in which each ...
- 1
0
votes
1
answer
83
views
Partitions of $n$ where every element of the partition is different from 1 is $p(n)-p(n-1)$
I am trying to prove that $p(n|$ every element in the partition is different of $1)=p(n)-p(n-1)$, and I am quite lost...
I have tried first giving a biyection between some sets, trying to draw an ...
- 763
0
votes
1
answer
129
views
Let g_n equal the number of lists of any length taken from {1,3,4} having elements that sum to n.
For example, g_3 = 2 because the lists are (3) abd (1,1,1). Also g_4 = 4 because the lsits are (4), (3,1), (1,3), and (1,1,1,1). Define g_0 = 1.
(a) Find g_1, g_2, and g_5 by complete enumeration.
(b) ...
- 61
2
votes
0
answers
45
views
Express number of partitions into prime numbers using partitions into natural numbers.
Let $P(n)$ is number of partitions of $n$ into natural numbers.
$R(n)$ is number of partitions of $n$ into prime numbers.
Is there any expression that relates $P(n)$ , and $R(n)$? I look for ...
- 1,382
1
vote
1
answer
134
views
Using generating functions to count number of ways to plan a semester
This is the question:
The semester of a college consists of n days. In how many ways can we separate the semester into sessions if each session has to consist of at least five days?
My work:
If $A(x)$ ...
- 13
0
votes
3
answers
80
views
Proving that $t_n = r_n$
Given a non-negative integer $n,$ let $t_n$ be the number of ways to partition $n$ using only powers of $2$ where each power is used at most three times, and let $r_n$ be the number of ways to ...
- 1,150
0
votes
0
answers
55
views
Number of integer partitions of $n$ with exactly $k$ parts from the set $S = \{s_1, s_2, \ldots, s_m\}$.
Specifically, I want to find the number of integer partitions of 1000 into exactly 100 parts of sizes {5, 20, 100} ignoring different orderings. I am trying to find the generating function. I have ...
2
votes
1
answer
144
views
An identity involving partitions
I have been trying to prove an identity using a combinatorial argument or another technique. I need to define the following first:
$$R(n,m) = \{ (r_1,r_2,...,r_n): \sum_{i=1}^n r_i = m \text{ and } ...
1
vote
0
answers
43
views
Systematic vertex information about finite Young's lattice
Suppose that I have Young's lattice $Y_{\mu}$ (finite sublattice for everything included in $\mu$). See the red area in the linked picture I found online where $\mu=[22]$ and note that the arrows ...
- 21
0
votes
0
answers
56
views
Finding Generating Function of Series, Coefficients Relate to Partitions
Let $\displaystyle p_{\leq c}(n)$ represent the number of partitions of $n$ into at most $c$ parts. What is the generating function of $\displaystyle\sum_{n \geq 0} p_{\leq c}(n)x^n$?
I'm completely ...
