Questions tagged [integer-partitions]
Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.
1,433
questions
2
votes
2
answers
378
views
Two combinatorics problems. I'm not 100% confident in my answers
These are two problems from my combinatorics assignment that I'm not quite confident in my answer. Am I thinking of these the right way?
Problem 1: On rolling 16 dice. How many of the $6^{16}$ ...
- 821
4
votes
2
answers
1k
views
Learning about partitions and modular forms
I'm interested in learning about partitions and modular forms. I already know algebra and analysis (complex and real). Can any one suggest me books or other materials from where I can learn these ...
- 15.1k
24
votes
1
answer
1k
views
Ellipse 3-partition: same area and perimeter
Inspired by the question,
"How to partition area of an ellipse into odd number of regions?,"
I ask for a partition an ellipse into three convex pieces,
each of which has the same area
and the same ...
- 30.4k
27
votes
1
answer
34k
views
The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts
This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
- 497
3
votes
1
answer
599
views
Partition number problem
Denote by $I_m=\{0,1,2,…m\}$, by $N_s=\{1,2,…,s\}$ , by $\overline s$ least common multiple of elements of set $N_s$ and by $p(k,N_s)$ the number of partitions of natural number $k$ in parts used ...
- 17k
7
votes
1
answer
1k
views
Number of ways to sum square numbers to yield a given number
I would like to know how many choices of $x_i$ there are such that $$\sum_{i=1}^{n}x_i^2=m$$
where $n$, $m$ are given. The $x_i$ can be any nonnegative integer and need not be unique and the order is ...
- 319
10
votes
2
answers
5k
views
Hardy Ramanujan Asymptotic Formula for the Partition Number
I am needing to use the asymptotic formula for the partition number, $p(n)$ (see here for details about partitions).
The asymptotic formula always seems to be written as,
$$ p(n) \sim \frac{1}{4n\sqrt{...
- 4,660
3
votes
1
answer
141
views
Something basic in "l-adic properties of the partition function" paper
I am trying to understand the basic result in this paper:
http://www.aimath.org/news/partition/folsom-kent-ono.pdf
My problem is with the example at the end of page 2. I understand it's supposed to ...
- 19.4k
21
votes
3
answers
3k
views
Closed-form Expression of the Partition Function $p(n)$
I feel like I have seen news that a paper was recently published, at most a few months ago, that solved the well-known problem of finding a closed-form expression for the partition function $p(n)$ ...
- 364
0
votes
2
answers
447
views
List all 3 part compositions of 5
I am looking at a past exam written by a student. There was a question I believed he got correct but received only 1/4. The marker wrote down "4 more compositions, order matters".
This is the problem:...
- 3,117
3
votes
2
answers
230
views
Generating sequences of numeric partitions
Definition: A tuple $\lambda = (\lambda_1, \ldots, \lambda_k)$ of natural numbers is called a numeric partition of $n$ if $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + \...
- 2,889
5
votes
1
answer
885
views
identity proof for partitions of natural numbers
Definition:
A tuple $\lambda = (\lambda_1, \cdots, \lambda_k)$ of Natural Numbers is called a numeric partition of n if $1 \leq \lambda_1 \leq \cdots \leq
\lambda_k$ and $\lambda_1 + \cdots + \...
- 2,889
2
votes
1
answer
706
views
How to find the coefficient of a term in this expression
How to determine the coefficient of z3q100 in
I stumbled upon this problem while trying to solve this type of partition problem:
Find the number of integer solutions to x + y + z = 100 such that 3 &...
- 613
7
votes
1
answer
4k
views
Number of permutations with a given partition of cycle sizes
Part of my overly complicated attempt at the Google CodeJam GoroSort problem involved computing the number of permutations with a given partition of cycle sizes. Or equivalently, the probability of a ...
- 294
6
votes
1
answer
262
views
Why is there a derivative in this formula?
This is a very simple question. Why is Rademacher's formula presented with d/dx in it?
Why not just "do" the derivative?
Then replace x with n?
Is it so there is only one transcendental function ...
- 6,268
27
votes
1
answer
1k
views
Feeding real or even complex numbers to the integer partition function $p(n)$?
Like most people, when I first encountered $n!$ in grade school, I graphed it, then connected the dots with a smooth curve and reasoned that there must be some meaning to $\left(\frac43\right)!$ — and,...
- 6,268
0
votes
3
answers
735
views
Partition an integer $n$ by limitation on size of the partition
According to my previous question, is there any idea about how I can count those decompositions with exactly $i$ members? for example there are $\lfloor \frac{n}{2} \rfloor$ for decompositions of $n$ ...
- 197
1
vote
3
answers
365
views
Decomposition by subtraction
In how many ways one can decompose an integer $n$ to smaller integers at least 3? for example 13 has the following decompositions:
\begin{gather*}
13\\
3,10\\
4,9\\
5,8\\
6,7\\
3,3,7\\
3,4,6\\
3,5,5\\...
- 197
1
vote
1
answer
365
views
Seeking some details about what is denoted by the partition function $P(n,k)$
Quoting from Wolfram MathWorld, "$P(n,k)$ denotes the number of ways of writing $n$ as a sum of exactly $k$ terms or, equivalently, the number of partitions into parts of which the largest is exactly $...
- 2,048
7
votes
3
answers
3k
views
Asymptotics for partitions of $n$ with largest part at most $k$ (or into at most $k$ parts)
Let $\bar p_k(n)$ be the number of partitions of $n$ with largest part at most $k$ (equivalently, into at most $k$ parts). Is there an elementary formula for the asymptotic behavior of $\bar p_k(n)$ ...
- 485
11
votes
4
answers
19k
views
number of ordered partitions of integer
How to evaluate the number of ordered partitions of the positive integer $ 5 $?
Thanks!
- 5,622
9
votes
1
answer
363
views
Seeking a textbook proof of a formula for the number of set partitions whose parts induce a given integer partition
Let $t \geq 1$ and $\pi$ be an integer partition of $t$. Then the number of set partitions $Q$ of $\{1,2,\ldots,t\}$ for which the multiset $\{|q|:q \in Q\}=\pi$ is given by \[\frac{t!}{\prod_{i \geq ...
- 21.1k
4
votes
1
answer
152
views
Validity of a q-series theorem
Define the $q$-analog $(a;q)_n = \prod_{k=0}^n \left(1 - aq^k\right)$.
I want to prove the identity $\frac{(q^2;q^2)_\infty}{(q;q)_\infty}=\frac{1}{(q;q^2)_\infty}$.
I viewed the LHS this way:
$$\...
- 12.5k
5
votes
2
answers
459
views
Natural set to express any natural number as sum of two in the set
Any natural number can be expressed as the sum of three triangular numbers, or as four square numbers. The natural analog for expressing numbers as the sum of two others would apparently be the sum ...
- 2,301
3
votes
2
answers
2k
views
Graph coloring problem (possibly related to partitions)
Given an undirected graph I'd like to color each node either black or red such that at most half of every node's neighbors have the same color as the node itself. As a first step, I'd like to show ...
- 484
3
votes
1
answer
2k
views
Upper bound on integer partitions of n into k parts
Recent news piqued my interest in integer partitions again. I'm working my way back through an old text and I'm completely hung up on this problem:
Recall that $p_k(n)$ is the number of partitions ...
user7463
1
vote
1
answer
65
views
Notation for "duplicating" partitions
I'm using Macdonald's "Symmetric Functions and Hall Polynomials" as a reference and did not find what I was looking for -- apologies if I only missed it.
As an example, let us consider the partition ...
- 878
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
34
votes
0
answers
710
views
Visualizing the Partition numbers (suggestions for visualization techniques)
So Ken Ono says that the partition numbers behave like fractals, in which case I'd like to try to find an appropriately illuminating way of visualizing them. But I'm sort of stuck at the moment, so ...
- 5,698
15
votes
5
answers
14k
views
Algorithm for generating integer partitions up to a certain maximum length
I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
- 757
35
votes
7
answers
27k
views
Making Change for a Dollar (and other number partitioning problems)
I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the ...
- 465
2
votes
1
answer
166
views
Number of distributions leaving none of $n$ cells empty
The solution for the number of distributions leaving none of the $n$ cells empty (with unlike cells and $r$ unlike objects) is given by
$$A(r,n)=\sum_{\nu=0}^{n-1}(-1)^{\nu}\binom{n}{\nu}(n-\nu)^{r}$$...
- 2,934
2
votes
1
answer
630
views
Matrix representation of a partition
Is there a natural way to represent all the partitions of an integer set $\{1,2,3,...,n\}$ as a matrix in the similar way permutations can be mapped to group of matrices?
- 6,697