Questions related to the different ways of expressing an integer as a sum of integers; or, questions related to the subdivision of a set into smaller disjoint sets; questions related to the subdivision of an interval into smaller intervals that intersect only at the endpoints.
4
votes
1answer
70 views
HAKMEM 18(B): Cubic Partitions
Taken from HAKMEM 18.
Quoting...
A partition of $N$ is a finite string of non-increasing integers that add up to $N$. Thus 7 3 3 2 1 1 1 is a partition of 18. Sometimes an infinite string of ...
13
votes
2answers
248 views
A question on partitions of n
Let $P$ be the set of partitions of n. Let $\lambda$ denote the shape of a particular partition. Let $f_\lambda(i)$ be the frequency of $i$ in $\lambda$ and let $a_\lambda(i) := \# \lbrace j : ...
17
votes
3answers
396 views
An Inequality Involving Bell Numbers: $B_n^2 \leq B_{n-1}B_{n+1}$
The following inequality came up while trying to resolve a conjecture about a certain class of partitions (the context is not particularly enlightening):
$$
B_n^2 \leq B_{n-1}B_{n+1}
$$
for $n \geq ...
4
votes
2answers
292 views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
1
vote
1answer
296 views
Number of solutions of Frobenius equation
I have one problem which needs to count the number of solution of the equation $$2x+7y+11z=42$$
where $x,y,z \in \{0,1,2,3,4,5,\dots\}$.
My attempt:
I noticed that that maximum value of $z$ could ...
9
votes
1answer
261 views
Recurrence for the partition numbers
I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the $P_n$ — number of partitions of size $n$ (or coefficients in ...
2
votes
2answers
200 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}$ ...
3
votes
2answers
298 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 ...
1
vote
0answers
121 views
Jordan Measure, Semi-closed sets and Partitions
From earlier question here. Consider
$$\mu \left( (0,1) \cap \mathbb Q \right) = 0$$
where
$$(0,1) = (0,\frac{1}{3})\cup [\frac{1}{3}, \frac{2}{3}] \cup (\frac{2}{3}, 1)$$ so
$$ \mu ((0,1) \cap ...
2
votes
2answers
248 views
Jordan Measures, Open sets, Closed sets and Semi-closed sets
I cannot understand:
$$\bar{\mu} ( \{Q \cap (0,1) \} ) = 1$$
and (cannot understand this one particularly)
$$\underline{\mu} ( \{Q \cap (0,1) \} ) = 0$$
where $Q$ is rational numbers, why? I ...
24
votes
1answer
744 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 ...
3
votes
1answer
971 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 ...
2
votes
1answer
369 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 ...
5
votes
1answer
152 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 ...
0
votes
2answers
438 views
Partition Problem, verifying solution in polynomial time
I add a look at the partition problem, this problem is know as the Easiest hard problem since it is NP-complete and seems pretty easy.
From wikipedia on NP-complete:
In computational complexity ...
3
votes
1answer
712 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 ...
1
vote
1answer
93 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 ...
7
votes
1answer
198 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)$ ...
0
votes
2answers
81 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 ...
4
votes
2answers
150 views
Trouble understanding proof that the unit interval cannot be partitioned in a certain way
From the book "Putnam and Beyond."
The problem:
Show that the interval [0, 1] cannot be partitioned into two disjoint sets A and B such that B = A + a for some real number a.
Proof:
Assume ...
0
votes
0answers
45 views
Prove that single machine can reduce from 2-partition problem
I'm given the following problem:
Prove that single machine \sum U_i (number of tardy job) with release date constraints problem can reduce from 2-partition problem
...
3
votes
2answers
97 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
1answer
293 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
1answer
295 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 ...
3
votes
1answer
326 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
1answer
153 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 ...
20
votes
1answer
427 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)!$ — ...
1
vote
1answer
131 views
What is the standard way of writing this partition function? [closed]
What is the standard way of writing the number of partitions of n where each number is less than or equal to k. Is it $p(n,k)$ or $p(k,n)$?
So far in my reading, have seen both.
0
votes
3answers
261 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
3answers
166 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\\
...
1
vote
1answer
143 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 ...
4
votes
2answers
180 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)$ ...
7
votes
1answer
175 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 ...
3
votes
1answer
88 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:
...
4
votes
2answers
263 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 ...
6
votes
1answer
179 views
What is the number of ways to choose x groups from y items? (partitions with x cells of a multiset)
Where a group can consist of 1 or more items, groups don't have to be equally sized and items can be duplicates. Example - Choose 3 groups:
Items: 1 2 2 3
Groups:
(1) (2 2) (3)
(1 2) (2) (3)
(3 ...
2
votes
2answers
233 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 ...
1
vote
1answer
436 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
1answer
46 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 ...
8
votes
1answer
772 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 ...
8
votes
0answers
173 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 ...
2
votes
4answers
2k views
Algorithm for generating integer partitions
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 ...
8
votes
6answers
2k 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 one quoted ...
2
votes
1answer
108 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
...
2
votes
3answers
284 views
“Converting” equivalence relations to partitions
There is a direct relationship between equivalence relations and partitions.
Is there a way to simply use an equivalence relation's definition to get the matching partition? And what about the other ...
2
votes
1answer
323 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?
