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.

learn more… | top users | synonyms

4
votes
5answers
2k views

Count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$

How to count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$ such that $x_1\ge 4,x_3 = 11,x_4\ge 7$ And how about $x_1\ge 4, x_3=11,x_4\ge 7,x_5\le 5$ In both cases, ...
1
vote
2answers
125 views

Every number $n^k$ can be written as a sum of $n$ distinct odd numbers

I wish to prove that for $n,k\in\mathbb{N} > 1$, we can always write $n^k$ as a sum of $n$ odd positive integers. I have an idea of how to approach this, but my method seems to cumbersome. I am ...
12
votes
4answers
2k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
2
votes
2answers
246 views

Number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s

How do I find the number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s? I think the title is self-explanatory. E.g., if I have to represent $13$ as a sum of only ...
1
vote
1answer
179 views

Number of perturbations of the Jordan form

I am looking for information about the number of Jordan forms that can be obtained from a given Jordan form of a small perturbation. For example, if a Jordan form consists of a single cell $2 \times ...
1
vote
1answer
399 views

The coin change problem in the quantitative way

Today,I came across this problem: Suppose you have a currency, named miso, in three denominations, $1, 10$ and $50$. In how many ways can $107$ miso be given in this currency if you have ...
2
votes
2answers
180 views

On the path diagram of a partition

A path diagram is a Ferrers diagram for a partition $\lambda$ in which the dots have been replaced with numbers computed as follows. The number in position $(i,j)$ the number of paths (going either ...
4
votes
3answers
189 views

A formula on partitions

Suppose that $\lambda,\mu$ are integer partitions, with conjugates $\lambda^*,\mu^*$. Could you help me to prove the following formula, please? ...
1
vote
2answers
449 views

Proving that exactly half the partitions of $n$ into powers of 2 have an even number of parts

Could you help me how to prove that exactly half the partitions of $n$ into powers of 2 have an even number of parts, please?
6
votes
2answers
263 views

Is an algebraic formula for the number of cyclic compositions of n known?

From Wikipedia: In January 2011, it was announced that Ono and Jan Hendrik Bruinier, of the Technische Universität Darmstadt, had developed a finite, algebraic formula determining the value of p(n) ...
4
votes
1answer
408 views

Exponential generating function for restricted compositions

I wanted to know if it is possible to use exponential generating functions to evaluate composition of N using K distinct numbers (where the supply of numbers is infinite)? For e.g if N=10 and ...
2
votes
4answers
264 views

Summing up Problem (Combinations)

This is a part of a bigger problem I was solving. Problem: $N$ is a positive integer. There are $k$ number of other positive integers ($\le N$) In how many ways can you make $N$ by summing up any ...
3
votes
2answers
1k views

Number of ways to represent a number from a given set of numbers

I want to know in how many ways can we represent a number $x$ as a sum of numbers from a given set of numbers $\{a_1.a_2,a_3,...\}$. Each number can be taken more than once. For example, if $x=4$ and ...
2
votes
1answer
122 views

Partition function with restrictions

What is the number of ways of partitioning a positive number $k\leq mn$ using non-increasing parts such that the number of parts can be at most $n$ and the value of each part can be at most $m$?
3
votes
2answers
138 views

Infinitely many $n$ such that $p(n)$ is odd/even?

We denote by $p(n)$ the number of partitions of $n$. There are infinitely many integers $m$ such that $p(m)$ is even, and infinitely many integers $n$ such that $p(n)$ is odd. It might be proved ...
4
votes
2answers
557 views

Some other ways to prove a partitions problem

Show that the number of partitions of the integer $n$ into three parts equals the number of partitions of $2n$ into three parts of size $< n$. I can only prove it by building a bijection ...
5
votes
3answers
229 views

Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
4
votes
1answer
142 views

Partition and power of 2s

I'm trying to find a partition of natural number N whereby we can generate a partition for all natural numbers less than N from the partition elements. The number of elements in the partition should ...
4
votes
1answer
107 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 ...
14
votes
2answers
278 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 : ...
18
votes
3answers
553 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 ...
5
votes
2answers
372 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
429 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
570 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
222 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}$ ...
4
votes
2answers
439 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
161 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) = \left(0,\frac{1}{3}\right)\cup \left[\frac{1}{3}, \frac{2}{3}\right] \cup \left(\frac{2}{3}, ...
2
votes
2answers
398 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 ...
26
votes
1answer
865 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 ...
6
votes
1answer
4k 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 ...
3
votes
1answer
453 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
288 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
977 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 ...
4
votes
1answer
2k 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
114 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 ...
9
votes
2answers
539 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
112 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
233 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 ...
3
votes
2answers
123 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
476 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
523 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 ...
5
votes
1answer
970 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
157 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 ...
21
votes
1answer
580 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)!$ — ...
0
votes
3answers
459 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
220 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
285 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
279 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
210 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 ...