All Questions
Tagged with integer-partitions elementary-number-theory
76
questions
1
vote
1
answer
101
views
On $(0,1)$-strings and counting
Consider a binary string of length $n$ that starts with a $1$ and ends in a $0$. Clearly there are $2^{n-2}$ such bit strings. I would like to condition these sequences by insisting that the number of ...
- 339
1
vote
1
answer
62
views
Computing integer partitions subject to certain constraints
Context:
I am programming a videogame.
Background:
Let $I$ be a set of named items such that each is assigned a difficulty score, and each is tagged either as "food" or "obstacle". ...
- 1,312
1
vote
1
answer
44
views
Graded ring generated by finitely many homogeneous elements of positive degree has Veronese subring finitely generated in degree one
Let $S=\bigoplus_{k\ge 0}S_n$ be a graded ring which is generated over $S_0$ by some homogeneous elements $f_1,\dotsc, f_r$ of degrees $d_1,\dotsc, d_r\ge 1$, respectively. I want to show that there ...
- 620
0
votes
1
answer
44
views
The Asymptotic formula of the generating function related with the partition of a positive integer
This question may be duplicate with this answer_1 and here I referred to the same paper by Hardy, G. H.; Ramanujan, S. referred to by wikipedia which is referred to in answer_1.
But here I focused on ...
- 416
19
votes
1
answer
1k
views
Can we partition the reciprocals of $\mathbb{N}$ so that each sum equals 1
Let $S = \{1, 1/2,1/3,\dots\}$
Can we find a partition $P$ of $S$ so that each part sums to 1, e.g.
$$P_1 = {1}$$
$$P_2 = { 1/2,1/5,1/7,1/10,1/14,1/70}$$
$$P_3 = {1/3,1/4,1/6,1/9,1/12,1/18}$$
$$P_4 = \...
- 702
6
votes
1
answer
84
views
Partition of a number $n$ whose each part is coprime with this number
I'm trying to solve the following problem: given an integer $n$, under which conditions of $n$ the following statement is true:
For any $1 < k \leq n$, there is always a partition of $k$ parts of $...
- 598
0
votes
0
answers
77
views
Factoring an integer $N$ using its random partition of length $3$
While working on this MSE question that I had posted, I wondered what would be a minimal base of numbers that we could work with the algorithm described in that question.
I conjectured that a ...
- 3,341
3
votes
0
answers
50
views
$\sum_{n=1}^m \frac{1}{n!} \sum_{\sum_{i=1}^n m_i = m, \\ m_i \in \mathbb N_+} \frac{1}{m_1\cdots m_n} = 1$? [duplicate]
I found an equation accidentally when doing my research about branching processes. I think it is correct but I don't know how to prove it:
\begin{equation}
\sum_{n=1}^m \frac{1}{n!} \sum_{\sum_{i=1}^n ...
- 1,972
0
votes
0
answers
60
views
Books for developing an intuitive understanding of the partitions of numbers
I understand from the fundamental theorem of arithmetic that every number can be written as a product of its prime factors,but I’m curious about partitions,how numbers can be broken up into sums and ...
0
votes
1
answer
33
views
Can I always split a friendly partition into two subpartitions, one of which is composed solely of 1, 2, 3, 4, and the largest part?
Suppose I have a partition $p$ of a positive integer $n$, $p$ is defined to be a friendly partition if and only if the following hold:
$n$ is divisible by $4$.
The length of $p$ is $\frac{n}{2}$.
...
- 11.9k
1
vote
1
answer
161
views
How to make this proof rigorous by introducing partition of numbers?
Question: Let $n$ be a positive integer and $ H_n=\{A=(a_{ij})_{n×n}\in M_n(K) : a_{ij}=a_{rs} \text{ whenever }
i +j=r+s\}$. Then what is $\dim H_n$?
Proof:
For $n=2$
$H_2=\begin{pmatrix} a_{11}&...
- 13k
-3
votes
4
answers
129
views
Find a minimal set whose elements determine explicitly all integer solutions to $x + y + z = 2n$
Is there a way to exactly parameterise all the solutions to the equation $x + y + z = 2n$, for $z$ less than or equal to $y$, less than or equal to $x$, for positive integers $x,y,z$?
For example, for ...
- 67
2
votes
0
answers
214
views
Maximize sum of ceiling functions
I need to find the maximum of a sum of ceiling functions. The following are given
$$N,C\in\mathbb{Z}\text{ with }0\leq N\text{ and }1\leq C$$
$$\frac{p}{q}\in\mathbb{Q}\text{ with }p,q \text{ coprime ...
- 87
0
votes
0
answers
41
views
Partitions of integers with finite uses in combinatorics
I've done some research into partitions and am yet to find any resources to understand the following:
Given a number $n$ and the restrictions that:
Using only the numbers $1, 2, ..., m$;
A maximum of ...
- 25
1
vote
0
answers
62
views
Number of solutions to linear equation $x_1+x_2+\dots+x_n=m$ when the domain of $x_i\ne$ domain of $x_j$
In the lecture notes of one of my previous classes, it was used that if we have an equation of the form
$$\tag{1}
x_1+x_2+\dots+x_n=m
$$
then the total number of solutions, when each $x_i$ is a non-...
- 175
2
votes
1
answer
74
views
Sum of Prime Factorizations and Primes
If I partition an integer and get the prime factorization of each partition, is there a way to tell if my original integer was a prime? For example, given the factorization of my partitions
$$71 = (56)...
- 157
0
votes
1
answer
81
views
Sum of how many numbers should N be partitioned.
Partition of integer:
4 = 4 p(4,1) = 1
= 1+3, 2+2 p(4,2) = 2
= 1+1+2 p(4,3) = 1
= 1+1+1+1 p(4,4) = 1
$max(p(...
user960916
1
vote
3
answers
141
views
Partitioning into products
Consider partitions where every summand has a factor in common with its neighbors and only $x_n$ can be one:
$$x_0 x_1 + x_1 x_2 + x_2 x_3 + \cdots + x_{n-1} x_n = N \qquad x_i \in \mathbb{N}$$
...
- 2,125
2
votes
1
answer
135
views
Integer partition asymptotics for a finite set of relatively prime integers.
I need to get approximations for partition functions in order to limit the expansion of the generating series used to work out the exact value.
The unrestricted partition function $ p(n) $ counts the ...
- 151
1
vote
2
answers
119
views
Unique ways to write $n$ as sum of three distinct nonnegative integers up to the order of the summands
How many ways are there to express a natural number, $n$, as the sum of three whole numbers, $a,b,c$, where $a,b,c$ are allowed to be 0 but are unique?
For example: $n=9$ there are only seven ways: $1+...
- 64
0
votes
1
answer
109
views
Find number of solutions for equation: $~x+y+z=n~$ where $~x,~y,~z~$ are non-negative whole numbers and $~x\le y\le z~$.
Find number of solutions for equation: $~x+y+z=n~$ where $~x,~y,~z~$ are non-negative whole numbers and $~x\le y\le z~$.
First I used substitution $~y=x+k,~ z=y+k~$ where $~k\ge 0~$(that is $y=x+k, z=...
- 533
4
votes
3
answers
315
views
Computing Ramanujan asymptotic formula from Rademacher's formula for the partition function
I am trying to derive the Hardy-Ramanujan asymptotic formula
$$p(n) \sim \frac{1}{4n\sqrt{3}}e^{\pi\sqrt{\frac{2n}{3}}}$$
from Radmacher's formula for the partition function $p(n)$ given by
$$p(n)=\...
0
votes
1
answer
55
views
Inequality relying on integer partitions and dominance ordering
Let $\lambda$, $\mu$ be two partitions of a natural number $n$, such that $\lambda$ dominates $\mu$ in the usual dominance order on partitions.
I would like to prove that if $q\geq 2$ is a natural ...
- 488
6
votes
2
answers
241
views
$p\equiv 1\pmod 4\Rightarrow p=a^2+b^2$ and $p\equiv 1\pmod 8\Rightarrow p=a^2+2b^2$, what about for $p\equiv 1\pmod {2^n}$ in general
Primes $p$ with $p\equiv 1\pmod 4$ can be written as $p=a^2+b^2$ for some integers $a,b$. For $p\equiv 1\pmod 8$ we have $p=a^2+2b^2$. Can primes that satisfy $p\equiv 1\pmod{2^n}$ for $n>3$ be ...
- 1,950
1
vote
1
answer
152
views
Distribution of number of terms in integer partitions
SOLVED: This is the Gumbel distribution
Let $\pi^n_i$ be set containing the terms in the $i$-th integer partition of the natural number $n$, according to whatever enumeration. For example, for $n = 5$ ...
- 11
1
vote
2
answers
398
views
A question about integer partitions
Lets say that $p(n)$ is the number of ways of partitioning $n$ into integers (order doesn't matter).
How does one prove that $$p(n) \equiv p(n|\text{distinct odd parts}) \mod 2$$?
For $n=1$, there's ...
- 5,215
0
votes
0
answers
30
views
Satisfiability of a congruence modulo the greatest prime dividing $n$
Let $n=2^km\ \ ,k\ge1$ be a positive integer with $m$ odd ($>1$ )and $r$ the greatest prime that divides $m$. Now, are there $\frac{r-1}{2}$ numbers $a_i$, less than $\frac{n}{2}$ and coprime to $...
- 7,085
1
vote
0
answers
121
views
Expressing a sum over the sizes of the parts of every partition of n
Let $(a_1^{r_1},\ldots,a_{p}^{r_{p}})\vdash n$ be the multiplicity representation of an integer partition of n. Each $a_{i}$ is a part of the partition and $r_{i}$ is its corresponding size. We ...
- 1,401
2
votes
1
answer
60
views
Can a number be partitioned into parts satisfying this condition? [closed]
Let $a,b,c,d,e,f$ be distinct decimal digits, with $ab,cd,ef$ being two-digit numbers formed from these digits (so that, for example, $ab=10a+b$).
How may I prove that the expression $ab+cd+ef$ ...
- 33
17
votes
0
answers
255
views
For what $n$ can $\{1, 2,\ldots, n\}$ be partitioned into equal-sized sets $A$, $B$ such that $\sum_{k\in A}k^p=\sum_{k\in B}k^p$ for $p=1, 2, 3$?
This is a recent problem in American Mathematical Monthly. The deadline for this question just passed:
$\textbf{Problem:}$ For which positive integers $n$ can $\{1,2,3,...,n\}$ be partitioned into ...
- 1,914
4
votes
1
answer
243
views
How to count all the solutions for $\sum\limits_{i=1}^{n} \frac{1}{2^{k_i}}= 1$ for $k_i\in \Bbb{N}$ and $n$ a fixed positive integer?
After reading this question, I would like to just count all solutions for:
$$\frac{1}{2^{k_1}} + \frac{1}{2^{k_2}} + \frac{1}{2^{k_3}} + \dots + \frac{1}{2^{k_n}}=1$$
for $k_i\in \Bbb{N}$ (we can ...
- 2,103
1
vote
1
answer
243
views
Is it possible to use partitions of an odd integer to generate primes in a given interval?
We start with the partition of $N=5$.
$$5$$
$$4+1$$
$$3+2$$
$$3+1+1$$
$$2+2+1$$
$$2+1+1+1$$
$$1+1+1+1+1$$
Then we form the sum of squares (no limit on the number of elements) to get:
$$4^2+1^2=17$$
...
- 1,058
2
votes
1
answer
77
views
Maximizing $\sum\left(\lfloor \frac{n_i}{2} \rfloor+1\right)$ for a partition $\{n_i\}$ of $N$
Let $N$ be a natural number and $\{n_i\}$ be a partition of $N$; by this we mean $1\leq i\leq k$ for some natural number $k$ and $N=n_1+n_2+\cdots+n_k$ where $n_1\geq n_2\geq\ldots\geq n_k\geq1$.
For ...
- 1,107
2
votes
3
answers
249
views
How to count all restricted partitions of the number $155$ into a sum of $10$ natural numbers between $[0,30]$? [closed]
How to count all restricted partitions of the number $155$ into a sum of $10$ natural numbers between $[0,30]$?
I really have no clue what to do with this one. Thanks for any help!
- 29
0
votes
0
answers
181
views
A generating function $G(x)=-\frac{\frac{1}{x^5}(1+\frac{1}{x})(1-\frac{1}{x^2})}{((1-\frac{1}{x})(1-\frac{1}{x^3}))^2}$ related to partitions of $6n$
Fix a sequence $a_n={n+2\choose 2}$ of triangular numbers with the initial condition $a_0=1$,such that
$1,3,6,10,15,21,\dots$
given by
$F(x)=\frac{1}{(1-x)^3}=\sum_{n=0}^{\infty} a_n x^n\tag1$
...
- 2,813
0
votes
1
answer
33
views
Converse of Ramanujan's Congruences
Of Ramanujan's famous congruences for the partition function, $p(5k+4)\equiv0\mod 5$, $p(7k+5)\equiv0\mod7$, and so on, does the converse also hold? For example, if $p(n)\equiv0\mod5$, does that mean $...
- 101
0
votes
1
answer
43
views
Equation to approximate a Partition-like function
The partition function for $n$, $P(n)$ gives the number of partitions that exist for $n$.
I've been trying to find a function that gives the number of partitions where order matters, e.g. $1+2+3$ is ...
- 109
2
votes
0
answers
133
views
Equal and unequal partition?
Can someone please tell me what equal and unequal partition is? And if the question, I'm just putting an example here, is asking you to find at least 3 equal and unequal partitions of 2020 into 4 ...
- 21
5
votes
1
answer
231
views
A Conjectured Mathematical Constant For Base-10 Normal Numbers.
Question 1: Let $a$ be a real number with a base-10 decimal
representation $a_1a_2\ldots a_n \ldots$ Denote the number of ways to
write $a_n$ as the sum of positive integers as $p(a_n)$ - also ...
- 3,758
9
votes
2
answers
264
views
P-graph of partition elements of 100 under common divisibility relation
Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than ...
- 1,162
10
votes
3
answers
3k
views
Number of partitions of $50$
Does someone know the number of partitions of the integer $50$? I mean, in how many ways can I write $50$ as a sum of positive integers?
I know that there's a table by Euler, which is useful to know ...
- 315
2
votes
0
answers
69
views
Is there accepted notation for the set of ways of partitioning a natural number $a$ into $b$ parts?
Recall the following:
Multinomial Theorem. For all finite sets $X$, we have:
$$\left(\sum_{x \in X} x\right)^n = \sum_{a}[a](X)^a$$
where $a$ ranges over the set of partitions of $n$ into ...
- 68.1k
1
vote
1
answer
241
views
Elementary proof of: Any integer is a sum of distinct numbers in {1,2,3,5,7,11,13,17,...}
Let $\mathbb P^1=\{1\}\cup\mathbb P$, the set of positive non composites. I have reason to believe that it is proved that all numbers greater than $6$ is a sum of distinct primes, and hence all $n\in\...
- 13.9k
2
votes
0
answers
719
views
$4\sum_{m,n=1}^{\infty}\frac{q^{n+m}}{(1+q^n)(1+q^m)}(z^{n-m}+z^{m-n})=8\sum_{m,n=1}^{\infty}\frac{q^{n+2m}}{(1+q^n)(1+q^{n+m})}(z^m+z^{-m})$
To prove the identity $$4\sum_{m,n=1}^{\infty}\frac{q^{n+m}}{(1+q^n)(1+q^m)}(z^{n-m}+z^{m-n})=8\sum_{m,n=1}^{\infty}\frac{q^{n+2m}}{(1+q^n)(1+q^{n+m})}(z^m+z^{-m})$$ I replaced $m-n$ by $k$ in LHS ...
1
vote
1
answer
133
views
Partitions of 2017 natural numbers [closed]
Suppose we have 2017 natural numbers, such that each 2016 can be grouped into 2 groups with equal sum and equal number of elements. Prove that all numbers are equal.
- 193
6
votes
2
answers
212
views
Partitions of n that generate all numbers smaller than n
Consider a partition $$n=n_1+n_2+\cdots+n_k$$ such that each number $1,\cdots, n$ can be obtained
by adding some of the numbers $n_1,n_2,\cdots,n_k$.
For example, $$9=4+3+1+1,$$
and every number ...
- 415
1
vote
1
answer
490
views
Sum over partitions
I want to calculate the following sum over non-negative integer partitions
$$
\sum_{l_1+\cdots +l_n=s} \frac{1}{(l_1!)^2 \cdots (l_n!)^2}.
$$
for fixed $n$ and $s.$
I tried to use Vandermonde's ...
- 321
1
vote
0
answers
49
views
Number of equivalent partitions
This is probably very elementary, but is there a way to get the number of equivalent (not necessarily ordered) partitions of an ordered $k$-fold partition $p=(p_1,..,p_k)$ of $n \in \mathbb{N}$ ...
- 1,460
7
votes
1
answer
233
views
What is the significance of this identity relating to partitions?
I was watching a talk given by Prof. Richard Kenyon of Brown University, and I was confused by an equation briefly displayed at the bottom of one slide at 15:05 in the video.
$$1 + x + x^3 + x^6 + \...
- 1,866
0
votes
2
answers
101
views
Number of partitions of $n$ formed by combinations of $2$ and $4$
I'm trying to find the number of partitions of a natural number that are a combination of $2$ and $4$.
For example: $$6 = 2+2+2 = 2+4
\Rightarrow p_6 = 2$$
So I start by defining $p_n$ as the ...
- 330