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
5
votes
2answers
477 views

Number of partitions contained within Young shape $\lambda$

It is well known that the number of partitions contained within an $m\times n$ rectangle is $\binom{m+n}{n}$. Furthermore, it is not difficult to calculate the number of partitions contained within a ...
5
votes
1answer
718 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 + \...
5
votes
2answers
246 views

How many numbers of $10$ digits that have at least $5$ different digits are there?

In principle I resolved it as if the first number could be zero, to the end eliminate those that start with zero. The numbers that can use $4$ certain figures (for example, $1$, $2$, $3$ and $4$) are ...
5
votes
2answers
236 views

Prove that the number of partitions of $2010$ into $10$ parts is equal to the number of partitions of $2055$ into $10$ distinct parts.

Prove that the number of partitions of $2010$ into $10$ parts is equal to the number of partitions of $2055$ into $10$ distinct parts. How we can prove this?My idea is to construct a bijection but I ...
5
votes
2answers
614 views

Derivative of Schur function

In his answer to https://mathoverflow.net/questions/129854, R. Stanley says that the partial derivative (over the relevant x[i]) of the Schur function of a partition lambda of n equals the sum the ...
5
votes
4answers
132 views

How many times does $k$ occur in the composition of $n$?

How many times does the number $k$ occur in the composition of $n$? Composition of Integer In short, the difference between the partition of an integer and composition is the order of numbers. In ...
5
votes
1answer
79 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. ...
5
votes
1answer
156 views

Recently proposed problem by George Andrews on partitions in Mathstudent Journal (India)

Show that the number of parts having odd multiplicities in all partitions of $n$ is equal to difference between the number of odd parts in all partitions of $n$ and the number of even parts in all ...
5
votes
1answer
547 views

Integral of products of cosines

Given $m+1$ integers $\alpha_0,\ldots,\alpha_m\geq 1$, I was trying to get a nice closed formula for the integral $$ \int_0^\pi\cos(\alpha_1\theta)\cdots\cos(\alpha_m\theta)d\theta. $$ More precisely, ...
5
votes
1answer
84 views

A conjecture on partitions

While trying to prove a result in group theory I came up with the following conjecture on partitions: Let $b(i,j)$ be the number of partitions of $i$ with greatest part exactly equal to $j$ , for ...
5
votes
2answers
404 views

Natural set to express any natural number as sum of two in the set

Any natural number can be expressed as the sum of three triangular numbers, or as four square numbers. The natural analog for expressing numbers as the sum of two others would apparently be the sum ...
5
votes
1answer
156 views

Young projectors in Fulton and Harris

In Section 4 of Fulton and Harris' book Representation Theory, they give the definition of a Young tableau of shape $\lambda = (\lambda_1,\dots,\lambda_k)$ and then define two subgroups of $S_d$, the ...
5
votes
2answers
389 views

Combinatorics question based on ProjectEuler 606

Motivation The following text is from Problem 606 from Project Euler : A gozinta chain for $n$ is a sequence $\{1,a,b,...,n\}$ where each element properly divides the next. For example, there ...
5
votes
1answer
209 views

What am I missing about Schur functions?

Let's say I only know the following about Schur functions: you give me a partition $\lambda$ of $d$ such that $\lambda$ has $n$ parts $\lambda_1,\ldots,\lambda_n$, and I can compute the Schur function ...
5
votes
1answer
222 views

Are infinite products commutative?

While reading a textbook, I came across the following proof (for integer partitions into odd parts and distinct parts): The following steps can be justified by taking finite products and then ...
5
votes
1answer
149 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 ...
5
votes
1answer
248 views

Existence of a prime partition

I'm interested in finding out whether there exists a prime partition of a given positive integer $N>1$ such that the partition has specific number of parts. For instance, as given in another ...
5
votes
3answers
499 views

Number of ways of partitioning a number $n$ in unique ways.

Given any number $n$, what is the method of finding out how many possible ways (unique) are there in which you can partition it - with the condition that all the numbers in each 'part' must be greater ...
5
votes
1answer
244 views

Elementary proof of a bound on the order of the partition function

I am interested in the asymptotic order of the partition function $p(n)$. The paper Asymptotic Formulae in Combinatory Analysis proves there are constants $A$,$B$ such that $e^{A\sqrt{n}} < p(n) &...
5
votes
1answer
84 views

Partitions of $0$ and $1$ by integers in the interval $[-N,\ldots,N]$

Background Often one comes across the problem of trying to find the number of ways to partition a positive integer into a sum of nonnegative integers. There are three ways to partition the number 3, ...
5
votes
0answers
96 views

How was this result for integer partitions found

If you look at one of the comments on A053445 you'll see it mentions that the second difference of partition numbers is equivalent to the number of integer partitions with two largest parts equal and ...
5
votes
0answers
247 views

Proof of these identities

The following is a screenshot from a paper by Daniel B. Grunberg called On asymptotics, Stirling numbers, Gamma function, and polylogs. I only offer the page as a reference to explain equation 3.1. ...
5
votes
0answers
58 views

Towers of coins puzzle [duplicate]

Let $n$ be a natural number. You are given $\frac{n(n+1)}{2}$ coins which are arranged in towers. Every turn you pick up the top coin of each tower and gather all these into a new tower. Prove that ...
5
votes
1answer
340 views

Notation for the set of all integer partitions

I'm working on a project that involves that set $P = \{\{n_1, \ldots, n_k\} \mid k \in \mathbb{N}, n_i \in \mathbb{N} \text{ and } n_1 + \cdots +n_k = n\}$ of all integer partitions of a number $n$. ...
5
votes
0answers
292 views

Sum over subsets of a multiset

I have a sum that looks like the following for some multiset $S$ and some function $f$ of $n$ variables which does not depend on the ordering of its arguments: $$\sum_{\{k_1,\dots, k_n\}\subset S}f(...
5
votes
0answers
96 views

The number of partitions by distinct positive numbers

Let $N>0$ be a natural number and let $P(N)$ denote the number of ways to write $N$ as a finite sum of $a_i$ such that the $a_i$ are strictly decreasing positive natural numbers. There is a paper ...
5
votes
0answers
602 views

How many partitions of 12 that fit the requirements?

How many partitions of $12$ are there that have at least four parts, such that the largest, second-largest, third-largest, and fourth-largest parts are respectively greater than or equal to $4,3,2,1$? ...
5
votes
0answers
458 views

Which unordered partition of $n$ gives rise to the largest number of ordered partitions?

A quick look at the wikipedia article on partitions of $n \in \mathbb{N}$ shows that the number of ordered partitions is $2^{n-1}$, and the number of unordered partitions is asymptotically $ \sim \...
5
votes
0answers
212 views

On Applications of the Murnaghan-Nakayama rule

The question is located below. In short, I am looking for an accessible explanation of the Murnaghan-Nakayama rule in relation to the following problem. Pardon the long setup. Let $Y$ be a standard ...
4
votes
2answers
2k views

Keep getting generating function wrong (making change for a dollar) [duplicate]

Possible Duplicate: Making Change for a Dollar (and other number partitioning problems) I am working on the classic coin problem where I would like to calculate the number of ways to make change ...
4
votes
2answers
3k views

Same number of partitions of a certain type?

Is there a quick explanation of why the number of partitions of $n$ such that no parts are divisible by $d$ is the same as the number of partitions of $n$ where no part is repeated $d$ or more times, ...
4
votes
2answers
4k views

1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,… (partition numbers): What is the recurrence relation / recursive formula / closed formula for this?

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
4
votes
2answers
484 views

For which $k$ are there most partitions of $n$ into $k$ parts?

Let $P(n,k)$ denote the number of partitions of $n$ into $k$ parts. I would like to know for given $n$, which $k$ does maximize $P(n,k)$? Additionally, information on the maximum of $P(n,k)$, for ...
4
votes
1answer
134 views

Validity of a q-series theorem

Define the $q$-analog $(a;q)_n = \prod_{k=0}^n \left(1 - aq^k\right)$. I want to prove the identity $\frac{(q^2;q^2)_\infty}{(q;q)_\infty}=\frac{1}{(q;q^2)_\infty}$. I viewed the LHS this way: $$\...
4
votes
1answer
78 views

How To Apply and Understand the Generating Function for Number Partitioning

The function p(n) counts the number of ways a number can be made up of smaller numbers. For example, the p(5) = 7 because you ...
4
votes
1answer
1k views

How many permutations in S(n) have this particular type?

I'm working through the textbook A Course in Enumeration. In the section about permutations and Stirling numbers, I'm having trouble understanding problem 1.45. It is: We fix $n \in \mathbb{N}$, and ...
4
votes
1answer
48 views

Partition of number's squares

The problem is to divide $\{k^2\}_{k=1}^{1000}$ into two groups of 500 numbers each, such that they have equal sum. I know that $$ \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}, $$ but it isn't enough ...
4
votes
1answer
93 views

General term of $(1+x)(1+x^2)(1+x^3)…$?

Is there a closed for the coefficient of $x^n$ in $(1+x)(1+x^2)(1+x^3)\cdots$? If not, then what is the closest to a closed form that anyone has found? (An infinite series that approximates it perhaps?...
4
votes
2answers
134 views

A curious partitions coincidence $\sum_{n=0}^\infty P(n) q^{n+1}$?

Given the partition function $P(n)$ and let $q_k=e^{-k\pi/5}$. What is the reason why, $$\sum_{n=0}^\infty P(n) q_2^{n+1}\approx\frac{1}{\sqrt{5}}\tag{1}$$ $$\sum_{n=0}^\infty P(n) q_4^{n+1}\approx\...
4
votes
1answer
169 views

Prove that $10\mid A000793(n\ge16)$

Prove that if $n\ge16,$then $10\mid g(n),$where $g(n)$ is the largest LCM of partitions of $n$. For more information,see http://oeis.org/A000793 Here is the list of $g(n)$ for $n>0,$ $g(15)=105,g(...
4
votes
3answers
6k views

The number of ways to write a positive integer as the sum of distinct parts with a fixed length

I am a topologist and not terribly familiar with the combo literature so please forgive me if this is standard. I'm hoping for some sort of reference for this. Given a positive integer $n$, I wish ...
4
votes
1answer
553 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 a1=2,a2=...
4
votes
2answers
692 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 ...
4
votes
1answer
142 views

Is there a partition of an open square into closed segments (not reduced to a point)?

Let $C$ be an open square (for example $]0, 1[ \times ]0, 1[$)of the plane $\mathbf R^2$. Is there a partition of $C$ into closed segments (not reduced to a point) ?
4
votes
2answers
145 views

Partition bijections

How do I prove bijectively that the number of partitions of $n$ with largest part $k$ equals the number of partitions of n with exactly $k$ parts.
4
votes
2answers
6k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
4
votes
3answers
918 views

Number of partitions of $2n$ with no element greater than $n$

The number of partitions of $2n$ into partitions with no element greater than $n$ (copied and slightly adapted from http://mathworld.wolfram.com/PartitionFunctionq.html), so I'm looking for a nice ...
4
votes
4answers
219 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? $\sum_{i,j}\mathrm{min}(\lambda_i,\mu_j)=\sum_k\...
4
votes
2answers
2k 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 ...
4
votes
2answers
1k 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 between ...