All Questions
Tagged with integer-partitions discrete-mathematics
120
questions
0
votes
1
answer
46
views
Give an argument using generating functions
Let $l_n$ be the number of partitions of $n$ which have exactly two parts of size $1$.
Let $L(x) = \sum l_n x^{n}$ be the generating function for $(l_n)$. (Let $l_0 = 1$ and $l_1 = l_2 = l_3 = 0.)$
...
- 41
1
vote
0
answers
272
views
Generating function for Durfee Squares
Let the Durfee Square of length $d$ of a partition of $n$ be the largest square that can be fit into the Ferrer's shape. Call the blocks in the Ferrer's shape on the right of the partition's Durfee ...
- 41
1
vote
1
answer
74
views
Urn Problem and Cartesian Product of Graphs
Consider a Graph $G=(V,E)$ with $|V|=n$ where each node $v\in V$ has a label $l_v\in\{1,...,n\}$. Denote by $G^k$ the k-fold Cartesian product of $G$ with itself where $k<n$. The set of nodes is ...
- 1,271
0
votes
1
answer
474
views
Proving that for all positive integers, the partitions $p(n) < p(n+1)$
Prove that the number of partitions of a number $n$ is less than the number of partitions of $n+1$. Now this seems quite trivial, but oddly enough, I'm not even sure how to go about proving it (...
- 365
0
votes
0
answers
25
views
Proof involving partitions [duplicate]
Prove that for fixed positive integers k and n, the number of partitions of n is equal to the number of partitions of 2n+k into n+k parts.
- 41
-1
votes
1
answer
90
views
Find a bijection to prove a fact about integer partitions
Prove that for fixed positive integers $k$ and $n$, the number of partitions of $n$ is equal to the number of partitions of $2n + k$ into $n + k$ parts.
I tried this with different values of n but ...
- 41
5
votes
0
answers
278
views
Expected Value for the Number of Parts of a Partition of n
Given a positive integer $n$, I want to know the expected value for the number of parts of a random partition of $n$.
I am aware that a similar question has been asked already: Expected number of ...
- 113
1
vote
4
answers
164
views
Number of solutions via generating function
How to find generating function for number of solutions
$x_1+x_2+x_3=n$ in set of positive integers such that $x_1 \ge x_2 \ge x_3$ and $x_1<x_2+x_3$.
- 473
0
votes
3
answers
66
views
Number of partitions of $12$
How can I calculate the coefficient of $x^{12}$ in the expression $$(1+x^2+x^4+x^6+x^8+x^{10}+x^{12})\cdot (1+x^4+x^8+x^{12})\cdot$$ $$ \cdot (1+x^6+x^{12})\cdot (1+x^8)\cdot (1+x^{10})\cdot (1+x^{12})...
user655901
1
vote
3
answers
33
views
Prove that the number of different ways to write an integer X as a sum of positive integers is $2^z$, if the order matters.
As an example for number 5, it is equal to $2^4$.
We can prove it by brute-forcing it, since it's a small number, as follows:
$1+1+1+1+1 $
$1+1+1+2 $
$1+1+2+1 $
$1+2+1+1 $
$2+1+1+1$
$1+1+3 $
$...
- 303
0
votes
2
answers
64
views
Partitions into Parts
Is it possible to express $p_m(n)$, the number of ways to write $n$ as a sum of $m$ parts, as some sum involving only $p(\cdot )$? I never seen such a formula before and was wondering whether this is ...
- 5,190
0
votes
1
answer
258
views
Counting the number of integer partitions
We start with a fixed partition of $[n]$, namely $(1,1...,1)=(1^{(n)})$.
We define an operation, say F, that takes two numbers within the partition and adds them up. So the first step leads to the ...
- 1,520
3
votes
3
answers
156
views
How to find effective partition of $n$ into $k$?
Here is a type of question that I find quite often on MO sites, that I couldn't quite solve:
How many ways can I put $n$ identical balls into $k$ identical boxes, with $n>>k$, such that each ...
- 442
1
vote
0
answers
40
views
Prove that the total number of ingredients in all $n$ divisions is equal $\sum _{k=0}^{n-1} P(k)r(n-k)$
Let $r(m)=\sum _{d|m} 1$ which is number of positive dividers $m$ and $P(a)$ which is number of possible divisions of $a$. Prove that the total number of ingredients in all $n$ divisions is equal $\...
- 3,205
5
votes
3
answers
140
views
Plain integer partitions of $n$ using $r$ parts
Division of number $n$ on parts $a_1,...,a_r$ where $a_1 \le ... \le a_r$ we call a plain if $a_1 = 1$ and $a_i - a_{i-1} \le 1$ for $2 \le i \le r$. Find enumerator (generating function) for plain ...
user677339