All Questions
Tagged with integer-partitions discrete-mathematics
120
questions
4
votes
1
answer
255
views
Alternative way of writing the stars and bars formula where each bar is associated with at least one star.
I was looking for a different way of writing the formula of the number of different $k$-tuples of non-negative integers whose sum is equal to $n$ and I thought of this formula followed by this ...
- 51
1
vote
0
answers
62
views
Number of solutions to linear equation $x_1+x_2+\dots+x_n=m$ when the domain of $x_i\ne$ domain of $x_j$
In the lecture notes of one of my previous classes, it was used that if we have an equation of the form
$$\tag{1}
x_1+x_2+\dots+x_n=m
$$
then the total number of solutions, when each $x_i$ is a non-...
- 175
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
0
votes
1
answer
113
views
Counting number of possible sequences given two constraints
Consider a 6 sided dice which takes values from $\{1,2,...,6\}$. let $n_i$ denote the number of times $i \in [6]$ appears on the dice. From this dice we create a non-decreasing sequence $(a_1,...,a_6)$...
- 392
0
votes
1
answer
95
views
Prove combinatorially the recurrence $p_n(k) = p_n(k−n) + p_{n−1}(k−1)$ for all $0<n≤k$.
Recall that $p_n(k)$ counts the number of partitions of $k$ into exactly $n$ positive parts (or, alternatively, into any number of parts the largest of which has size $n$).
- 31
1
vote
1
answer
78
views
Identity with integer partitions
I have to prove that $p(n)=p(n-1)+\displaystyle\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}p_{k}(n-k)$ and I am quite stuck on it...
My first intuition was that, as $p(n)-p(n-1)$ is the number of partitions ...
- 763
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
1
vote
1
answer
172
views
Is a Standard Tableau determined by its descent set?
Suppose $\lambda\vdash n$ is a partition. Associated with this partition is the set of Standard Young Tableau $\text{SYT}(\lambda)$ such that the associated Young Diagram is filled in with the numbers ...
- 405
0
votes
1
answer
66
views
How can I prove this equation for my discrete math project?
Is there a way I can prove this? This is part of one of my discrete math classes. I need to prove:
${\displaystyle \prod_{i\geq1} \frac{1}{1-xq^i}} = {\displaystyle \sum_{k\geq0} \frac{x^kq^{k^2}}{(1-...
- 23
7
votes
3
answers
234
views
Prove that $\prod_{i\geq 1}\frac{1}{1-xy^{2i-1}} = \sum_{n\geq 0} \frac{(xy)^{n}}{\prod_{i=1}^{n}\left( 1-y^{2i} \right)}.$
Prove that
$$\prod_{i\geq 1}\frac{1}{1-xy^{2i-1}} = \sum_{n\geq 0} \frac{(xy)^{n}}{\prod_{i=1}^{n}\left( 1-y^{2i} \right)}.$$
Here I am trying the following
\begin{align*}
\prod_{i\geq 1}\frac{1}{1-xy^...
- 376
1
vote
1
answer
819
views
Partitions of $n$ into even number of parts versus into odd number of parts
I'm under the impression that if $n$ is even then the number of partitions of $n$ into an even number of parts exceeds the number of partitions of $n$ into an odd number of parts. And the opposite if $...
- 462
2
votes
2
answers
128
views
Counting the number of partitions such that every part is divisible by $k$.
I would like to do this using generating functions. I'm comfortable with the generating function for the number of partitions of $n$: $$(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\cdot\dots,$$ ...
- 462
0
votes
3
answers
256
views
How many ways can you pay $100 when the order in which you pay the coins matters?
Suppose there is a vending machine where you have to pay $100. You
have an unlimited amount of 1 dollar, 2 dollar and 5 dollar coins. How many ways
can you pay when the order in which you pay the ...
-6
votes
1
answer
69
views
Count the numbers of integer solutions of the ecuation $x_1 + x_2 + x_3 + x_4 = 21$ [duplicate]
How to count the number of nonnegative integer solutions to $x_1 + x_2 + x_3 + x_4 = 21$ such that $x_1$, $x_2$, $x_3$, $x_4 ≤ 7$
- 1
1
vote
1
answer
78
views
Computing problems and generating functions
Q. Find the generating function for the sequence $\{a_n\}$, where $a_n$ is the number of solutions to the equation: $a+b+c=k$ when $a, b, c$ are non-negative integers such that $a\ge2, 0\le b\le3$ and ...
