Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [integer-partitions]

Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.

1
vote
0answers
28 views

Writing down consecutive natural numbers until a certain number of digits $k$ is reached.

A person starts writing consecutive natural numbers from $5$ until $k$ digits are reached. For some values of $k$, this will be impossible, for example $6$ or $8$ are impossible as then after writing ...
2
votes
1answer
20 views

Finding all natural number solution(s) to linear Diophantine equation of three variables

Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end. For those curious, this puzzle comes from the game West of Loathing. It's ...
-1
votes
2answers
38 views

Nine objects in non-empty boxes [on hold]

In how many ways 9 identical objects can be put in non-empty boxes of arbitrary size? Is solution integer partition of 9? That is 30?
3
votes
2answers
59 views

Decomposing an integer number into up to N (not necessarily prime) numbers with minimal sum

I am writing a program that processes data based on an integer factor. The process can either be done at once, or in multiple stages. For example, one stage with factor 500 could be replaced by three ...
0
votes
0answers
9 views

On some constrained partitions of $ k $-multiperfect numbers

Let $ n $ be a $ k $ -multiperfect number. Do we know an upper bound for the number of partitions of $ n $ whose all summands are at the same time multiples of $ k $ and the sum of distinct ...
3
votes
1answer
64 views

Combinatorial Proof that $p(n)/(1+\epsilon)^n \to 0$

I was thinking this morning about the identity $ \prod_{n=1}^{\infty} \left( \frac{1}{1-q^n} \right) = \sum_{n=0}^{\infty} p(n) q^n$. The product on the left converges for $|q|<1$, which implies ...
2
votes
1answer
24 views

Understanding Graham's proof of theorem on Unit Fractions.

In this paper by Ronald Graham, the theorem that every integer greater than 77 has a partition with the property that the sum of the reciprocals of the various "piles" in the partition is 1 (lovely!). ...
0
votes
2answers
24 views

limit of ratio of partition function

Does the following limit exists? $$\lim_{n \rightarrow \infty} \frac{p(n)}{p(n-5)}$$ where $p(n)$ denote the partition function. If this limit exists, is it equal to 1? Kindly share your thoughts....
0
votes
1answer
25 views

Number of ordered partitions of N into K distinct parts modulo P (with a “proof” using hyperplanes)

I've come across a combinatorics problem where I'm fairly certain that a solution exists, yet I'm unable to find it. I'm trying to find the number of vectors $(x_1,x_2,...,x_n)$ such that $\sum x_i ...
1
vote
2answers
29 views

Limit the maximum value of the composition of an integer

I was doing a coding test (already finished, so no cheating for me) and came across this problem, which I'll describe in few steps: We have a keypad, like on cellphones, with keys from 1 to 9, where ...
2
votes
0answers
42 views

An upper bound for integer partitions with unique summands

Let $p_\neq (n)$ be the number of all partitions of $n$ such that all summands are distinct (for example $p_\neq (6)=4$). How do we show that $p_\neq (n) \leq e^{2\sqrt n}$?
0
votes
1answer
25 views

Verifying that $ \prod_{j=1}^{\infty} \frac{1}{1-q^j} = \prod_{j=1}^{\infty} \frac{1}{(1-q^{2j-1})(1-q^{2j})}$

On page 165 of Chapter 13, how was the equality made from line 1 to line 2? https://archive.org/details/NumberTheory_862/page/n173 Namely, how $$ \prod_{j=1}^{\infty} \frac{1}{1-q^j} = \prod_{j=1}^{\...
2
votes
1answer
38 views

Find Integer Partition using only integers belonging to S = { 1, 2, 3 }

I spent all afternoon looking for this but I wasn't able to find anything, so... Is there a formula to know the NUMBER of partitions with a constraint on the integer domain ? E.g.: Find the number of ...
0
votes
0answers
23 views

Relation between partitions of $n$ into $k$ distinct parts and partitions of $n$ into at most $k$ parts [duplicate]

I'm working on a problem that I'm completely stuck on: Let $Q(n,k)$ be the number of partitions of $n$ into $k$ distinct (unequal) parts. Prove that the number of partitions of $n$ into at most $k$ ...
10
votes
2answers
816 views

Error in solution of Peter Winkler “red and blue dice” puzzle?

This question relates to the solution give in Peter Winkler's Mathematical Mind-Benders to the "Red and Blue Dice" problem appearing on page $23.$ You have two sets (one red, one blue) of $n\ n-$...
0
votes
1answer
36 views

Number of Partitions of n into 4 parts equals the number of partitions of 3n into 4 parts of size at most n-1.

Let $n\geq 4$. Prove that the number of partitions of $n$ into 4 parts equals the number of partitions of $3n$ into 4 parts of size at most $n-1$. I am stuck on this problem but I suspect I need to ...
4
votes
1answer
52 views

Ramanujan congruence mod 7

Hello I am trying to prove this congruence: $$P(7n+5)\equiv 0 \pmod{7}$$ In order to do that I have done the next thing: We have that $\displaystyle\sum_{n\geq0}\;P(n)q^{n}=\frac{1}{(q;q)_{\infty}}...
0
votes
1answer
34 views

What is the appropriate weight ($W_k$) (for two arbitrary partitions)?

I already asked a similar question, And from the answer I received, another question came to my mind. A positive integer can be partitioned, for example, the number 7 can be partitioned into the ...
1
vote
1answer
44 views

Partitions in Combinatorics

Let $2\leq k\leq n$. Prove that $p_k(n)=p_{k-1}(n-1)+p_k(n-k)$ where $p_k(n)$ is the number of partitions of $n$ into $k$ pieces. Here's my proof: Proof: Let $2\leq k\leq n$. Let $p_k(n)$ be the ...
3
votes
1answer
48 views

Is this true for every partitioning?

I have two categories (category1 and category2 ) and The size of both categories is equal to each other. if we partition each categories arbibtrary .Is this proposition proven? or rejected? $n_T \...
0
votes
0answers
29 views

Expected number of parts of a uniformly selected partition of $n$

I have a very basic question on partition theory, which I feel should be very well known. Suppose that you fix a natural number $n$ and select a random partition $P$ of $n$ by choosing uniformly from ...
1
vote
1answer
43 views

Combinations of flowers using the counting method for integer partitions.

I have this problem to complete that wants to know how many combinations of flowers can there be in a bouquet of 25 flowers, such that: $r+c+d+t=25$ where $r=$roses, $c=$carnations, $d=$daisies and $...
1
vote
1answer
39 views

What is the coefficient of $ x^{i}$ in the product $ \ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq 1} \frac{1}{1+x^{2i-1}}$?

What is the coefficient of $ x^{i}$ in the product $ \ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq 1} \frac{1}{1+x^{2i-1}}$? Answer: $\ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq ...
0
votes
0answers
27 views

Generating Function for partition of r into distinct parts

My combinatorics class is learning about generating functions and partitions of numbers into summands. One exercise we are working on for tomorrow's lecture to better understand the concept is to find ...
0
votes
1answer
29 views

show number of partitions of $n$ equals to number of partitions of $n-k$

Let $n,k\in\mathbb{Z}^+$ and $n\geq k$. Suppose $n = \lambda_1 + \lambda_2 + \cdots + \lambda_k$ is an integer partition of $n$, and $\lambda_1 \geq\lambda_2\geq\cdots\geq\lambda_k$. Show (the number ...
-1
votes
1answer
724 views

Represent $N$ as the sum of exactly $K$ distinct positive integers

You are given two integers $N$ and $K$. Find all ways to represent $N$ as the sum of exactly $K$ distinct positive integers $x_1,x_2, \ldots,x_K$ — in other words. $xi_>0$ for each valid $i$; ...
0
votes
0answers
174 views

Partition a number $n$ in exactly sum of $k$ distinct numbers such that product of the numbers should be maximum.

The question is to partition a given number $n$ in exactly sum of $k$ distinct positive numbers such that the product of $k$ distinct number become maximum. $k$ will be given optimally so that it will ...
0
votes
1answer
44 views

Question on generating function of integer partitions

How can I show that $$\prod_{k \ge 1}(1+z^{2k}) = \prod_{k \ge 1}(1+z^k+z^{2k}+z^{3k}) \quad ?$$ I have worked on this for a while and I am even doubting that maybe both are not equal
1
vote
1answer
34 views

Number of compositions of a natural number $n \in \mathbb{N}$ with at least two parts.

So I have to show that the number of partitions of $n \in \mathbb{N}$ is $2^{n-1} -1 $. ( the order is important ). So here is my attempt. Please be strict. If you find any mistake or something that ...
1
vote
1answer
26 views

How many ways to make change using specific amounts.

I am trying to figure out a recurrence relation or any kind of formula really that returns the number of ways to calculate a specific amount $n$ using only $3, 4, 5$. So for $8$ you can do either $4+4$...
0
votes
0answers
21 views

Maximal Goldbach Partitions?

A Goldbach partition $2n = p + q$ with $p$ and $q$ primes and $p \leqslant q$ is usually called minimal if the numbers $2n - k$ ($k = 1,\ldots, p-1$) are all composite. Reading through the literature,...
0
votes
0answers
49 views

Compatible partitions with laws of compositions?

An exercise from Artin's Algebra: Let S be a set with a law of composition: A partition $\Pi_1 \cup \Pi_2 \cup ...$ of S is compatible with the law of composition if for all i and j, the product ...
0
votes
1answer
28 views

Building a Generating Function to Represent an Integer Partition

From a Miklos Bona combinatorics textbook, I'm at an almost total loss. My professor recently discussed products of generating functions, so I suspected this problem might relate. The only strategy ...
1
vote
2answers
57 views

Proving correspondence and partitions via generating functions, or at least I think so.

Let $A=\{2,6,10,14,\ldots\}$ be the set of integers that are twice an odd number. Prove that, for every positive integer $n$, the number of partitions of $n$ in which no odd number appears more than ...
1
vote
0answers
33 views

Number theoretic calculation of probability problem involving partitions.

This question asks for a specific miscalculation of how large chance that I get at least one call every day of the week if I in total get 12 calls during a week. If we instead consider the question ...
1
vote
1answer
76 views

How many different ways to pay $2018, using only quarters, dimes, nickels, and pennies?

I have seen solutions that show how this is done for amounts such as $1. Namely I consulted this webpage's explanation-- https://www.maa.org/frank-morgans-math-chat-293-ways-to-make-change-for-a-...
0
votes
0answers
27 views

How to calculate the partitions of a concrete number? [duplicate]

This might be a super stupid question, but my math courses are long gone and I am stuck completely solving some math puzzles for fun. Just as a hobby, no homework involved. I want to calculate the ...
1
vote
0answers
26 views

Time complexity of finding the largest Goldbach partition

Suppose we are given a large even integer $N$, and we want to determine primes $p$ and $q$ such that $N = p + q$, subject to the conditions that $p \geqslant q$ and $p - q$ is as small as possible. (...
3
votes
2answers
85 views

Two Recurrences for Counting Rooted Trees

The number of unlabeled rooted trees with $n$ nodes is given by the sequence A000081 in the OEIS. They provide the following recurrence relation: $$ a_{n+1} = \frac{1}{n} \sum_{k=1}^n \left( \sum_{d \...
0
votes
0answers
45 views

Bijection Partition identity [duplicate]

Hello I have a doubt about the next partition identities $P(n: even \; number \; of \; odd \; parts)=P(n: distinct\; parts, \; number \; of \; odd\; parts\; is\; even)$ Also for the case when both ...
1
vote
1answer
17 views

Partitions of integers, but ignoring commutativity and restricted to only using the first $3$ positive integers

My question involves the number of ways to add up to a positive integer $n$ such that the order in which we add the terms up matter (so ignoring commutativity) and we are restricted to only using $1$'...
0
votes
2answers
54 views

Truncating a generating function

It is true that the generating function for the number of ways to partition an integer $n$ into a sum of ones is \begin{align} f(x) = 1 + x + x^2 + x^3 + \cdots \end{align} But I don't see how the $1$ ...
1
vote
1answer
14 views

Combinatorial proof of $P(n|p|q+1) = P(n-q|p|\le q+1) - P(n-p-q|p|\le q)$

A recent question asked for a proof of an identity of restricted partition numbers which looks at first glance like an application of inclusion-exclusion, but for which I have only been able to find a ...
1
vote
1answer
20 views

Sum of partition's product modulo 5 up to 41

If we define $S(n)$ as $4=3+1=2+2=2+1+1=1+1+1+1$ $S(4)=3\cdot1+2\cdot2+2\cdot1\cdot1+1\cdot1\cdot1\cdot1=3+4+2+1=10$ $5=4+1=3+2=2+2+1=2+1+1+1=1+1+1+1+1$ $S(5)=4\cdot1+3\cdot2+2\cdot2\cdot1+2\cdot1\...
1
vote
1answer
86 views

Number of partitions with restriction on the greatest part and on the number of parts

I apologise that my original question wasn't clear . I've made some improvements to make it more understandable (hopefully) . I need help about the following two theorems from G. Chrystal's "...
2
votes
1answer
146 views

Polynomial recursion from sequence recursion

Let $P(n,d)$ denote the number of partitions of $n$ with Durfee square of size $d$ (the largest square that fits inside the diagram of the partition). The sequence $P(n,d)$ is known to satisfy the ...
5
votes
1answer
76 views

Sharing a pie evenly among an unknown number of people. [duplicate]

This is a question inspired by the question "Nine gangsters and a gold bar" on the Puzzling Stack Exchange. Suppose you're throwing a party, and you know that either 7, 8, or 9 people will arrive. ...
0
votes
0answers
9 views

Uniformly bounded function in Newman's proof of the partition formula

In chapter II of his book Analytic Number Theorey, D.J. Newman states that the function $F'(xe^{i\theta}) = \frac{-e^{xe^{i\theta}}}{xe^{i\theta}(e^{xe^{i\theta}}-1)^2} + \frac{2}{x^3e^{2i\theta}} - \...
2
votes
2answers
57 views

How many compositions does 40 have (with up to 5 addends), with each positive integer addend between 2 and 12?

I was on Youtube and found a show called Monopoly Millionaires' Club. I thought it would be interesting to try to calculate the probability of winning the million dollars. The contestant starts on ...
2
votes
2answers
90 views

Proof of an identity about integer partition

I'd like to know how to prove the following identity, $$\sum_{k=1}^n k\, p(n, k) = \sum_{r,s\ge 1, rs\le n} p(n-rs)$$ where $n\in N^+$. Here, $p(n)$ counts the number of possible partitions of $n$. ...