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
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 + \...
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
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 &...
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 ...
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 ...
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,...
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$ ...
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\\...
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 $...
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)$ ...
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!
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 ...
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:
$$\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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
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?