Questions tagged [integer-partitions]
Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.
1,440
questions
1
vote
1
answer
84
views
Solving a recursion formula involving products of compositions of an integer
I have the following recursive formula that I want to solve in order to find a general, non-recursive expression for arbitrary $S_N$ (real positive number). Here it is:
\begin{equation*}
S_{N+1} = \...
- 147
2
votes
0
answers
18
views
Optimal balanced ternary set of weights - infinite version
A fairly well known puzzle is to pick the optimal weights for use in a simple, symmetric balance. It is assumed that any combination of weights with or without the sample will fit in either pan. The ...
- 8,627
2
votes
3
answers
50
views
Generating all sorted positive integer sequences of given length that sum to a given total
In this thread, a bijective function is requested which, given two positive integers $n$ and $k$, maps between natural-number identifiers and sequences of $k$ positive integers that sum to $n$. Due to ...
- 389
0
votes
1
answer
121
views
Bounding the Dirichlet inverse of $f(n) = e^{-mn}$.
Suppose we have an arithmetic function defined as $f(n) = e^{-m n}$, for some $m > 0$.
Then we have that the Dirichlet inverse is given by:
$f^{-1}(n) = \displaystyle{\sum_{k=1}^{\Omega(n)}} (-1)^k ...
- 383
0
votes
1
answer
56
views
Maximizing $\sum_{i<j} \frac{x_i x_j}{\sum_{k=i}^j x_k}$ over compositions of $m$
I'm interested in the one-parameter family of optimization problems, parametrized by $m \in \mathbf{Z}^+$
$$\max_{n, x_1,x_2,\dots,x_n \in \mathbf{Z}^+ \\ x_1+x_2+\cdots + x_n=m} \sum_{i=1}^{n-1} \...
- 24.6k
4
votes
1
answer
237
views
Series about coefficients of multiplicative inverse of power series
Let be an integer $d\geqslant 2$ and a real number $L\in(0,1)$. I consider the following formal power series
$$T(x) := 1-L\,\sum_{1\leqslant j < d} x^j =: \sum_{n\geqslant 0} {a_n}x^n$$
with $a_0=1$...
- 341
10
votes
3
answers
344
views
Can you do better than partial fraction decomposition?
Consider the function $f_3(x)=\frac1{(1-x)(1-x^2)(1-x^3)}$. We can think of computing some sort of partial fraction decomposition for $f_3(x)$. For example,
$$f_3(x)=\frac{1/6}{(1-x)^3}+\frac{1/2}{(1-...
- 433
1
vote
1
answer
42
views
Given a partition of $r$, find the number of partitions of $s$ such that each part of $s$ is coprime to each part of $r$.
I encountered the following problem.
Suppose $r,s\in\mathbb{N}$ and consider a partition $\sum_{i=1}^k r_i$ of $r$.
Question: How many partitions $\sum_{j=1}^l s_j$ of $s$ exist such that $\...
- 11
1
vote
0
answers
55
views
Proof of a statement in OEIS A260533 about partitions
Defining the coefficient of a partition $p=(p[1]\geq p[2] \geq \dots \geq p[m])$ of $n=p[1]+\dots+p[m]$ as $c(p)=\binom{p[1]}{p[2]} \binom{p[2]}{p[3]}\dots\binom{p[m-1]}{p[m]}$ A260533 states that ...
- 1,389
-1
votes
1
answer
72
views
Number of ways to write n as a sum of k different nonnegative integers
I need find a recursive function ( Withdrawal formula ) $\operatorname{f}\left(n,k\right)$ for the problem:
What is the number of ways to write $n$ as a sum of $...
- 43
0
votes
0
answers
31
views
Basis for skew-symmetric polynomials in $n$ variables
I am reading from Introduction to Group Characters by Walter Ledermann [2nd edition]
On page $113$, the proposition $4.4$ states
The set $V=\{V_l\}$ where $l$ ranges over all strictly decreasing ...
- 326
0
votes
0
answers
19
views
Value of $k$ that gives the highest Restricted-Part Integer Partition Number for $n$
Let $p_k(n)$ be the number of possible partitions of an Integer $n$ into exactly $k$ parts. We know that for any given $n$, $p_k(n)$ gives a non-zero result for $0<k\leq n$, and that the size of ...
0
votes
0
answers
66
views
How to define initial values for recurrence relation
I was given the following problem : let $f(n,k)$ be the number of possible partitions of $n$ into $k$ different non-negative integers. Find a recurrence relation and initial values for $f(n,k)$.
So I ...
3
votes
2
answers
65
views
$(w_{1},w_{2},w_{3},\dots,w_{7})$ integers with $20\le w_{i} \le 22$ such that $\sum_{i=1}^{7}w_{i} = 148$
How many $(w_{1},w_{2},w_{3},\dots,w_{7})$ where each of the $w_{i}$'s are integers and $20\le w_{1},w_{2},w_{3},\dots,w_{7}\le 22$ such that they satisfy
$$w_{1}+w_{2}+w_{3}+\dots+w_{7}=148$$
ATTEMPT
...
- 453
1
vote
0
answers
66
views
Finding formula for $a+b+c=n$ where $(a,b,c)$ are positive integers.
I'm currently studying a book by Paul Zeitz and currently stuck on exercise 6.2.23, below is the problem:
Find a formula for the number of different ordered triples $(a,b,c)$ of positive integers ...
- 453
0
votes
0
answers
22
views
dominance order of conjugate partition
Let $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n $ be two sets of non-strictly decreasing non-negative integers such that $\sum_{i=1}^n a_i = \sum_{i=1}^n b_i = m > 0 $. Let $a_i'$ and $b_i'$ ...
- 129
1
vote
1
answer
50
views
Confusion between relation of stars and bars and q-binomial coefficient
Suppose we want to know the number of integer solutions to the equation $$x_1 + \cdots x_m = N$$ where $0 \leq x_i \leq t - 1$ for $1 \leq i \leq m$. One way to do this is by finding the coefficient ...
- 1,011
5
votes
3
answers
173
views
The number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers
For each integer $n$, let $a_n$ be the number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers.
I found (by listing) that $ a_1, a_2, a_3, a_4$ are $1, 2, 5, 15$ ...
- 829
0
votes
1
answer
85
views
Generating function and currency
We assume that we have a country's currency that contains three coins worth 1, 3, and 4. How many ways can we get an amount of $n$ using these three pieces?
In others words what is the number of ...
- 35
1
vote
1
answer
107
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 ...
- 433
1
vote
2
answers
160
views
high school math: summands
Let's say we have a question that asks you to find the amount of all possible integers adding up to a random number, lets just say 1287. However, the possible integers is restricted to explicitly 1's ...
user1339058
1
vote
1
answer
52
views
Generating function of partitions of $n$ in $k$ prime parts.
I have been looking for the function that generates the partitions of $n$ into $k$ parts of prime numbers (let's call it $Pi_k(n)$). For example: $Pi_3(9)=2$, since $9=5+2+2$ and $9=3+3+3$.
I know ...
0
votes
0
answers
12
views
Conjugate of a Gel'fand pattern
Background:
A Gel'fand pattern is a set of numbers
$$
\left[\begin{array}{}
\lambda_{1,n} & & \lambda_{2,n} & & & \dots & & & \lambda_{n-1,n}...
- 300
2
votes
1
answer
166
views
About the product $\prod_{k=1}^n (1-x^k)$
In this question asked by S. Huntsman, he asks about an expression for the product:
$$\prod_{k=1}^n (1-x^k)$$
Where the first answer made by Mariano Suárez-Álvarez states that given the Pentagonal ...
0
votes
1
answer
42
views
A variant of the partition problem or subset sum problem
Given a target list $T = (t_1, t_2, \ldots, t_N)$ and a multiset $S = \{s_1, s_2, \ldots, s_M\}$, both with non-negative integer elements, $t_k\in \mathbb{N}_>$ and $s_k\in \mathbb{N}_>$, ...
- 124
2
votes
0
answers
26
views
Bell numbers - Cardinality of odd number of parts in partitions of the finite set $[n]$.
As it well known, Bell numbers denoted $B_{n}$ counts distinct partitions of the finite set $[n]$. So for example if $n=3$ there are 5 ways to the set $\left\{ a,b,c\right\}$ can be partitioned:
$$\...
- 119
2
votes
1
answer
41
views
Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$.
Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$, and that it equals $(1+q)(1+q^{3})\cdot\cdot\cdot(1+q^{2n-1})$.
For the first part, ...
- 807
0
votes
0
answers
89
views
Need help with part of a proof that $p(5n+4)\equiv 0$ mod $5$
Some definitions:
$p(n)$ denotes the number of partitions of $n$.
Let $f(q)$ and $h(q)$ be polynomials in $q$, so $f(q)=\sum_0^\infty a_n q^n$ and $h(q)=\sum_0^\infty b_n q^n$. Then, we say that $f(q)\...
- 350
0
votes
0
answers
82
views
How to prove the following partition related identity?
So I want to show that the following is true, but Iam kidna stuck...
$$
\sum_{q_{1}=1}^{\infty}\sum_{q_{2}=q_{1}}^{\infty}\sum_{q_{3}=q_{1}}^{q_{2}}...\sum_{q_{k+1}=q_{1}}^{q_{k}}x^{q_{1}+q_{2}+...+q_{...
- 1
0
votes
1
answer
46
views
Is there a closed form method of expressing the *content* of integer partitions of $n$?
I know that the question of a closed form for the number of partitions of $n$, often written $p(n)$, is an open one (perhaps answered by the paper referred to in this question's answer, although I'm ...
- 107
2
votes
1
answer
94
views
MacMahon partition function and prime detection (ref arXiv:2405.06451)
In the recent paper arXiv:2405.06451 the authors provide infinitely many characterizations of the primes using MacMahon partition functions: for $a>0$ the functions $M_a(n):=\sum\limits_{0<s_1&...
- 747
0
votes
1
answer
49
views
There are allways $q_1,q_2,...,q_n$ such that $f'(q_1)+f'(q_2)+...+f'(q_n)=n$ for every natural n [duplicate]
Let $f$ be a differentiable between $(0,1)$ and take $f(1)=1, f(0)=0$. Prove that then there exist $q_1,q_2,...,q_n$ distinct points such that $f'(q_1)+f'(q_2)+...+f'(q_n)=n$ for every natural n. By ...
- 345
1
vote
0
answers
48
views
Is this connection of (increasingly exclusive) integer partitions to the the Euler-Mascheroni constant useful?
$\mathbf{SETUP}$
From this previous question, I quote Cauchy's formula for the number of all possible cycle types
\begin{align}
N_{\lambda} =
\frac{n!}
{1^{\alpha_1} 2^{\alpha_2} ... n^{\...
- 107
3
votes
1
answer
71
views
Why does this connection of increasingly exclusive partitions $P_{n,k}$ to the harmonic series $H_k$ exist?
$\mathbf{SETUP}$
In this previous question, I show how the sum of all cycles of type defined by non-unity partitions of $n$ relates to the derangement numbers / subfactorial $!n$ (number of ...
- 107
1
vote
0
answers
42
views
How to explain arithmetic form of surprising equality that connects derangement numbers to non-unity partitions?
$\mathbf{SETUP}$
By rephrasing the question of counting derangements from
"how many permutations are there with no fixed points?"
to
"how many permutations have cycle types that are non-...
- 107
0
votes
0
answers
24
views
Congruences of partition function
I'm trying to understand Ken Ono's results showing Erdös' conjecture for the primes $\ge5$. He first shows the following: let $m\ge5$ be prime and let $k>0$. A positive proportion of the primes $\...
- 73
1
vote
0
answers
47
views
Proving an Identity on Partitions with Durfee Squares Using $q$-Binomial Coefficients and Generating Functions
Using the Durfee square, prove that
$$
\sum_{j=0}^n\left[\begin{array}{l}
n \\
j
\end{array}\right] \frac{t^j q^{j^2}}{(1-t q) \cdots\left(1-t q^j\right)}=\prod_{i=1}^n \frac{1}{1-t q^i} .
$$
My ...
- 185
5
votes
1
answer
68
views
Recursion regarding number-partitions
I am learning about partitions of numbers at the moment.
Definition:
Let $n \in \mathbb{N}$. A $k$-partition of $n$ is a representation of $n$ as the sum of $k$ numbers greater than $0$, (i.e.
$n=a_1+....
- 889
0
votes
0
answers
43
views
Find generating function for the number of partitions which are not divisible by $3$. [duplicate]
I'm trying to find the generating function for the number of partitions into parts, which are not divisible by $3,$ weighted by the sum of the parts. My idea is that we get the following generating ...
- 121
0
votes
0
answers
20
views
Estimate the order of restricted number partitions
There are $k$ integers $m_l,1\leq l\leq k
$(maybe negetive), satisfiying $|m_l|\leq M$ and $\sum_l m_l=s$.
I want to get an order estimate of the number of solutions for $k, M$ when fixing $s$.
I came ...
- 127
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
0
votes
0
answers
60
views
A generalized subset sum problem
I'm looking at a problem I believe is combinatorial.
Find all possible solutions $\mathbf{x}$ to:
$$\mathbf{a} = [a_1, a_2, ..., a_n], a_k \in \mathbb{N^+}$$
$$\mathbf{l} = [l_1, l_2, ..., l_n], l_k \...
- 231
0
votes
0
answers
56
views
Name of such combinatorial numbers. [duplicate]
Let $k,n\in\mathbb{N}$. Let $N(k,n)$ denote the size of the finite set
$$\{(x_1,\cdots,x_k)\in\mathbb{N}^k:x_1+2x_2+\cdots+kx_k=n\}. $$
I feel it special and important. Do $N(k,n)$ have names? Is ...
- 1,469
0
votes
1
answer
34
views
Partial Orders on Integer Partitions
My question is the following: An integer partition $\lambda$ can be represented as an integer sequence $(f_1,f_2,f_3, \cdots)$ where $f_i$ is the number of parts used in $\lambda$. For instance, $4 + ...
- 439
2
votes
0
answers
41
views
Has anyone found a closed-form expression for the strict partition function?
More precisely, if anyone has found it, could they provide links, please? I have been trying to find such a solution and have not seen one.
For context, when I try to solve the strict partition ...
- 21
1
vote
1
answer
56
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 ...
- 640
1
vote
0
answers
32
views
Congruences of partitions and Legendre symbol.
Let $(\frac{a}{p})$ denote the Legendre symbol, and let $\psi(q)=\sum_{n\geq 0} q^{n(n+1)/2}$.
We define Ramanujan's general theta function $f(a,b)$ for $\mid ab \mid <1$ as
$$
f(a,b)=\sum_{n=-\...
- 21
1
vote
0
answers
80
views
"Factorization" of the solutions set of a system of linear diophantine equations over non-negative integers
Suppose we have a system of linear diophantine equations over non-negative integers:
$$
\left\lbrace\begin{aligned}
&Ax=b\\
&x\in \mathbb{Z}^n_{\geq0}
\end{aligned}\right.
$$
where $A$ is a ...
- 11
0
votes
0
answers
26
views
irregularities in partition function modulo n
It is an open problem whether the partition function is even half the time. Inspired by this, I wrote some Sage/Python code to check how many times $p(n)$ hits each residue class:
...
- 379
1
vote
0
answers
34
views
Show the partition function $Q(n,k)$, the number of partitions of $n$ into $k$ distinct parts, is periodic mod m
Let $Q(n,k)$ be the number of partitions of $n$ into $k$ distinct parts.
I want to show that for any $m \geq 1$ there exists $t \geq 1$ such that
$$Q(n+t,i)=Q(n,i) \mod m \quad \forall n>0 \forall ...
- 103