Questions tagged [integer-partitions]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
22 views

$\mathfrak{sl}(2)$ decomposition for classical nilpotent orbits

Consider the nilpotent orbit, $\mathcal{O}_X$, of a semi-simple Lie algebra, $\mathfrak{g}$, represented by a nilpotent element $X\in \mathfrak{g}$. We can then always find a triplet $\{H,X,Y\}$ ...
0
votes
0answers
27 views

Partitions into distinct even summands and partitions into (not necessarily distinct) summands of the form $4k-2,k\in\Bbb N$

Prove that the number of ways to partition $n\in\Bbb N$ into distinct even summands is equal to the number of ways of partitioning $n$ into (not necessarily) distinct summands of the form $4k-2,k\in\...
0
votes
2answers
77 views

Natural Boundary of Euler's Partition Generating Function

Let $\mathbb{D}=\{z\in\mathbb{C}:|z|<1\}$. Let's consider the analytic function $f:\mathbb{D}\to\mathbb{C}$ given by, for all $z\in\mathbb{D}$, $$f(z)=\prod_{n=1}^\infty (1-z^n)^{-1}.$$ For each ...
0
votes
1answer
55 views

Number of k-tuples of non-negative integers whose sum equals a given integer

Does the sum over the non-negative integers, $$ \sum\limits_{ {i_1, \ldots i_k \geq 0:\\\ i_1+\ldots i_k=L }} 1 $$ have a closed expression, where $L$ and $k$ are some integers?
2
votes
1answer
58 views

Error in my derivation of $\binom{2n-1}{n}$ as number of partitions of $n$

Does a formula for the number of partitions of an integer exist? Given that this sequence is in the OEIS (https://oeis.org/A000041) I would guess not. However I have an intuitive way of counting them, ...
0
votes
1answer
88 views

Counting number of possible sequences given two constraints

Consider a 6 sided dice which takes values from $\{1,2,...,6\}$. let $n_i$ denote the number of times $i \in [6]$ appears on the dice. From this dice we create a non-decreasing sequence $(a_1,...,a_6)$...
2
votes
1answer
68 views

Demonstration for the equal number of odd and unequal partitions of an integer

I'm having some problems trying to resolve one exercise from The art and craft of problem solving by Paul Zeitz. What this problem asks you is to prove that $F(x)$ is equal to 1 for all $x$, where $$F(...
0
votes
2answers
60 views

How many different ways are there to make n dollars with 1, 5, 10, 25, and 50 cent coins. [closed]

I am trying to figure out a formula for how many different ways you can make n American dollars with pennies, nickels, dimes, quarters, and half dollars. There has to be a formula for this, right? I ...
2
votes
1answer
46 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)...
1
vote
1answer
42 views

Express an integer $m$ as sum of 1, 0 and -1 for fixed number of summands $j$

Let $j \in \mathbb{N}_0$. I'm looking for the number of all possible combinations, such that for a given $|m| \leq j, m \in \mathbb{Z}$ $m = \sum \limits_{k=1}^{j} a_k\quad$ where $a_k \in {-1, 0, 1}$ ...
1
vote
2answers
35 views

Recurrence relations in the generating function of binary partitions

Let $b(n)$ denote the number of binary partitions of $n$, that is, the number of partitions of $n$ as the sum of powers of $2$. Define \begin{equation*} F(x) = \sum_{n=0}^\infty b(n)x^n = \prod_{n=0}^\...
0
votes
0answers
59 views

Number of ways to write 1 as sum of unit fractions

For an integer $n \in \mathbb{N}$, let $f(n)$ be the number of ways to write 1 as a sum of exactly $n$ unit fractions. For example: $f(1) = 1$ since there is only one way to write 1 as a sum of a ...
2
votes
1answer
50 views

Number of Jordan forms from given characteristic polynomial and partitions

Suppose I have a characteristic polynomial $$f(x) = (x-a_1)^{r_1}(x-a_2)^{r_2}\cdots(x-a_n)^{r_n}$$ of a matrix whose size is $m×m$, I began to think that how many Jordan forms are there corresponding ...
3
votes
0answers
101 views

Least common multiple of three integers.

Let $a_1,a_2,a_3\in\mathbb Z_{\geq1}$ be three integers and let $A$ be their least common multiple. I want to prove the following. If $m_1,m_2,m_3\in\mathbb Z_{\geq0}$ such that $m_1a_1+m_2a_2+m_3a_3=...
1
vote
2answers
138 views

What is the closed form solution to the sum of inverse products of parts in all compositions of n?

My question is exactly as in the title: What is the generating function or closed form solution to the sum of inverse products of parts in all compositions of $n$? This question was inspired by just ...
2
votes
1answer
45 views

Number of ways of distributing $n$ elements

Suppose we have $n$ elements that we want to distribute to people forming a queue, and we want to know the number of different ways we could make the distribution independently of the number of ...
0
votes
1answer
65 views

What is the generating function for the number of partitions of an integer in which each part is used an even number of times?

What is the generating function for the number of partitions of an integer in which each part is used an even number of times? I'm trying to prove the number of partitions of an integer in which each ...
0
votes
1answer
40 views

Proving coefficient of $x^n$ in an infinite product of $(1+x^k)$ is the number of partitions of $n$ where each summand is distinct [closed]

Consider the number $q_n$ of partitions of n with all summands distinct. Prove that $q_n$ is the coefficient of $x^n$ in the infinite product $$\prod_{k=1}^\infty (1+x^k)$$ I solved a similar problem ...
0
votes
0answers
34 views

A counting problem with Young Diagrams

Let $n$ and $d$ be natural numbers. How many Young diagrams of size $n$ are there such that each diagram has less than or equal to $d$-rows ?
2
votes
0answers
39 views

Is $ \prod_{i=1}^{\infty} \frac{1}{(1-\frac{1}{2p_i^3})} $ equivalent to this sum of partitions?

$$\prod_{i=1}^{\infty} \frac{1}{(1-\frac{1}{2 p_i^3})} = \sum_{n=0}^{\infty} 2^{-n} \sum_{k=0}^{\infty} (\frac{1}{2} ; \frac{1}{2})_k \: \frac{Par(n-\Omega(k+1)+k, k)}{(k+1)^3} $$ where $p_i$ is the $...
0
votes
0answers
15 views

Distribution of integer partitions by number of parts

I imagine someone has studied this already so I'm just looking for resources: what sort of asymptotic behavior does the distribution of integer partitions of $n$ counted by the number of parts exhibit?...
1
vote
0answers
22 views

Partition With Ranking to Solve A Clustering Problem

I have r restaurants and f friend where no of f >> no of r. Basically this is a clustering problem. I want to find the nature of clusters(i.e which restaurant consists how much no of friends) ...
0
votes
1answer
50 views

Partition of $N$ into integers $a_1,\cdots a_M$ for fixed $M$: how to define an index on [0,1] closest to 1 when the $a_i$ are almost the same?

Given a fixed integer $N$ that is divided into $M$ (integer sized) pieces, I am looking for an expression which is closer to 1 when the sizes of the $M$ pieces are as equal as possible, and closer to $...
0
votes
1answer
40 views

Prove combinatorially the recurrence $p_n(k) = p_n(k−n) + p_{n−1}(k−1)$ for all $0<n≤k$.

Recall that $p_n(k)$ counts the number of partitions of $k$ into exactly $n$ positive parts (or, alternatively, into any number of parts the largest of which has size $n$).
4
votes
1answer
109 views

"On the Probability of Sequences in the Genoese Lottery" by Euler. How did he do it?

This a problem solved by Leonard Euler. Translated English version is available in Euler archives.[E338]On the Probability of Sequences in the Genoese Lottery Euler. I have difficulty in understanding ...
1
vote
1answer
59 views

Identity with integer partitions

I have to prove that $p(n)=p(n-1)+\displaystyle\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}p_{k}(n-k)$ and I am quite stuck on it... My first intuition was that, as $p(n)-p(n-1)$ is the number of partitions ...
0
votes
1answer
24 views

Partitions of $n$ where every element of the partition is different from 1 is $p(n)-p(n-1)$

I am trying to prove that $p(n|$ every element in the partition is different of $1)=p(n)-p(n-1)$, and I am quite lost... I have tried first giving a biyection between some sets, trying to draw an ...
0
votes
1answer
23 views

Partition function of multi-particle canonical ensemble

According to the orthogonality of function basis, Why can't the partition function be written directly as the following form \begin{align} \begin{split} Z & = \frac{1}{N!} \sum_{p_{1},p_{2}, \...
0
votes
1answer
58 views

Let g_n equal the number of lists of any length taken from {1,3,4} having elements that sum to n.

For example, g_3 = 2 because the lists are (3) abd (1,1,1). Also g_4 = 4 because the lsits are (4), (3,1), (1,3), and (1,1,1,1). Define g_0 = 1. (a) Find g_1, g_2, and g_5 by complete enumeration. (b) ...
0
votes
2answers
82 views

Understanding a solution of USAMO 1999 (Integers having numerous partitions of a certain type)

For what values of $n≥1$ do there exist a number $m$ that can be written in the form $$a_1 + \cdots+ a_n$$ with $$a_1 \in \{1\}, a_2 \in \{1,2\},\cdots , a_n \in \{1,\ldots,n \}$$ in $(n-1)!$ or ...
0
votes
1answer
75 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(...
2
votes
1answer
148 views

Given a set of both positive and negative numbers, what is a time optimal approach to find the two numbers whose sum, plus a third number is zero

Coming from an engineering background I want to solve this question. I have isolated two keywords, dynamic programming and number partitioning (number theory) and a reference to this hard problem I ...
0
votes
0answers
19 views

Number of partitions of a positive integer with largest part not exceeding k

What is the number of partitions of $n\in \mathbb{N}$ so that the largest part is at most $k$? I tried it for a few small cases, but I am unable to find a general way.
1
vote
3answers
130 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}$$ ...
1
vote
1answer
81 views

Why is the following not $S(n,3)$ where $S(n,k)$ is a Stirling number of the second kind? (almost solved)

In an attempt to relate the number of partitions of integers to that of partitions of distincts objects I stumbled, in the particular case of $k:=3$, on the following sum $$\sum_{\genfrac{}{}{0pt}{1}{...
2
votes
1answer
56 views

Coin change issue with additional restrictions

I'm working on the coin change problem with specific coins. Which I understand how to solve, but now there is an additional condition, where each coin has a different weight in grams, and I need to ...
2
votes
1answer
50 views

Set of non-negative integers with fixed sum and other constrain [closed]

everyone. Suppose I have a set of non-negative integers $\{x_1,\dots,x_N\}$ and they have fixed sum $\sum_i x_i = A_1$. Also, the quantity $\sum_i i x_i = A_2$ is also fixed. Suppose I know $N$, $A_1$ ...
2
votes
1answer
77 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 ...
3
votes
1answer
39 views

Parity of hooklengths in a partition diagram

Main Question Let $\lambda\vdash n$ be a partition, with hooklengths $\{h_1,\dots,h_n\}$ in its partition diagram. Is there a formula for determining $$\#\{h_i\text{ even}\}-\#\{h_i\text{ odd}\}?$$ ...
2
votes
0answers
38 views

Express number of partitions into prime numbers using partitions into natural numbers.

Let $P(n)$ is number of partitions of $n$ into natural numbers. $R(n)$ is number of partitions of $n$ into prime numbers. Is there any expression that relates $P(n)$ , and $R(n)$? I look for ...
1
vote
2answers
82 views

Euler's partition method. How does someone use it?

I came across partitions recently and am not very much informed about it but I have a question regarding Euler's method for this. I came to know about this formula from a YouTube video so, it may not ...
3
votes
2answers
160 views

How many different ordered triples are there such that $a+b+c = 50$ and $a\geq b\geq c\geq 0$? What if $a>b>c>0$?

How many different ordered triples are there such that $a+b+c = 50$ and $a\geq b\geq c\geq 0$? What if $a>b>c>0$? a,b, and c are all integers I found this question from a textbook, but the ...
0
votes
0answers
27 views

Enumerating lattice paths with diagonals

Consider the set of integer lattice paths starting on the non-negative y-axis and ending on the non-negative x-axis with the following moves: Right by $1$, Down by $1$, Diagonals going from $(a,b)$ ...
0
votes
0answers
21 views

Change in Partition for Weighted Geometric Mean if Sum Increases

I previously asked a question Change in Partition for Geometric Mean if Sum Increases, to show that if the sum increases by 1, then all we need to do is increase one of the partitions by 1 to increase ...
5
votes
2answers
307 views

Maximizing product of three integers

It is well-known that, if we want to partition a positive number $m$ into a sum of two numbers such that their product is maximum, then the optimal partition is $m/2, ~ m/2$. If the parts must be ...
1
vote
1answer
50 views

Breaking up a sum

Imagine we are adding two numbers: $$ 5+3 $$ But, we decide to break up and re-arrange the sum as follows: $$ \underbrace{(1+1+3)}_{\text{First Part}}+\underbrace{(1+1+1)}_{\text{Second part}} $$ ...
0
votes
1answer
29 views

Finding maximum weighted geometric mean in integer partition with fixed number of partitions

In trying to find the maximum geometric mean given an integer $n$ and $k$ target partitions, where $n = \sum_{i=1}^k n_i$ and $\Pi_{i=1}^k n_i$ is maximal, we can find such $n_1, ..., n_k$ by ...
1
vote
1answer
39 views

Change in Partition for Geometric Mean if Sum Increases

Suppose we have a fixed constant $k$, and a number $x$, where we need to partition $x$ into the sum of $k$ integers: $$x = x_1+\cdots+x_k$$ such that the geometric mean $\prod_{i=1}^k x_i$ is ...
1
vote
1answer
59 views

Using generating functions to count number of ways to plan a semester

This is the question: The semester of a college consists of n days. In how many ways can we separate the semester into sessions if each session has to consist of at least five days? My work: If $A(x)$ ...
2
votes
1answer
24 views

Sum of $k-tuple$ partition of $d$. $k$ and $d$ are both positive integers.

I am trying to understand this paper by Bondy and Jackson and in it I found the following calculation in which I cannot figure out how we got from 2nd last step to last step. I have referred the paper ...

1
2 3 4 5
25