Questions related to the different ways of expressing an integer as a sum of integers; or, questions related to the subdivision of a set into smaller disjoint sets; questions related to the subdivision of an interval into smaller intervals that intersect only at the endpoints.

learn more… | top users | synonyms

5
votes
1answer
119 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 ...
3
votes
2answers
439 views

How many combinations of $3$ natural numbers are there that add up to $30$?

How many combinations of $3$ natural numbers are there that add up to $30$? The answer is $75$ but I need the approach. Although I know that we can use $_{(n-1)}C_{(r-1)}$ i.e. $_{29}C_2 = 406$ but ...
4
votes
0answers
221 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 ...
4
votes
3answers
83 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 ...
1
vote
1answer
53 views

Prove : $P(n | \text{ number of parts $\le m$}) = P(n | \text{ all parts $\le m$})$

I'm trying to prove both sides of : $$P(n | \text{ number of parts $\le m$}) = P(n | \text{ all parts $\le m$}).$$ First side: Given a partition where all parts $\le m$, we can build a Ferrer's ...
1
vote
1answer
212 views

Prove : $p$(n│even number of ODD parts)=$p$(n│distinct parts ,number of ODD parts is even )

I'm trying to prove the following Integer Partition claim : $p$(n│even number of ODD parts) = $p$(n│distinct parts ,number of ODD parts is even) . So I tried to prove a stronger claim : ...
4
votes
4answers
318 views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
0
votes
1answer
71 views

Partition of a set and Hall's theorem

I have been wrestling with an exercise concerning latin squares from the textbook A First Course in Discrete Mathematics by Ian Anderson. The exercise is formulated thus: A set $S$ of $mn$ ...
4
votes
1answer
77 views

Partitions of a prime power into powers of the same prime

Fix a prime $p$, and $k$ a natural number. The question is then: How many partitions of $p^k$ are there into powers of $p$? So, for instance, if $p = 2$ and $k = 2$, there are 4, namely (4), (2, 2), ...
1
vote
1answer
223 views

Generating function of the number of integer partitions of $n$ into all distinct parts

Let $p_d (n)$ denote the number of integer partitions of $n$ into all distinct parts. I am given the following equation, but I can't figure out why it holds: $$\sum_{n \ge 0} p_d(n)x^n = \prod_{i \ge ...
35
votes
0answers
827 views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
2
votes
1answer
133 views

Number of even parts of a partition

Fix a positive integer $n$. For a partition $\lambda$ of $n$, let $e(\lambda)$ be the number of even parts in $\lambda$. Using generating functions or bijections, we can show the statistic ...
3
votes
1answer
109 views

What will be time complexity using dynamic programming

If I were to find a set of 10 positive integers whose sum = 87248 and the sum of their squares = 447804117. Using an efficient dynamic programming, what will be time complexity of this kind of ...
1
vote
2answers
76 views

Compute all the sets of 87248 into 10 parts

How many sets are possible? I have to compute all the sets of 87248 into 10 parts (Additional conditions which may be useful are: integers can be repeated, every integer is less than or equal to ...
3
votes
0answers
85 views

On Applications of the Murnagham Nakayama rule

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

How to determine the no. of integral partitions into $k$ parts?

I wanted to know, if I was to partition $500$ into positive $k$ integers, not necessarily distinct under the following constraints 1.k is +ve. 2.all k parts need not be distinct. 3.the first ...
1
vote
1answer
30 views

Resource allocation with minimal differences

Let $N$ be a finite set. Let $\prec$ be a strict partial order over $N$. I am interested in designing a function $f : N \to \mathbb{R}$ such that: $\sum_{n_i \in N} f(n_i) = 1$ $\forall i,j : n_i ...
0
votes
1answer
327 views

Generating function of partition with restriction [duplicate]

Let $c(m,n)$ denotes number of partitions $n$ into parts not greater than $m$, where order of elements does matter (so they are not classic partitions). Prove that: $$\sum_{n\ge 0}c(m,n)x^n = ...
2
votes
1answer
123 views

sum factors of natural numbers

Using natural numbers 1,2,...n, in how many ways can the number n be formed from the sum of one or more smaller natural numbers? I thought it would be an easy problem but i couldn't figure it out. ...
0
votes
0answers
303 views

Number of ways to divide a stick of integer length $N$, take 2

This is a follow up and motivated by this question, Number of ways to divide a stick of integer length $N$, Suppose we have a stick of integer length $N$. I'm looking for (preferably closed-form) ...
4
votes
1answer
334 views

In how many ways can you split a string of length n such that every substring has length at least m?

Suppose you have a string of length 7 (abcdefg) and you want to split this string in substrings of length at least 2. The full enumation of the possibilities is the following: ...
3
votes
1answer
79 views

Bounds on Young Tableau Element locations

I'm having trouble finding some elementary results on the following. Let $Y$ be a standard Young Tableau of shape $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_n)$ with $N:=\sum_{i=1}^n\lambda_i$. My ...
1
vote
1answer
120 views

Contructing a $\delta$-fine tagged partition from the old ones

Let $[a,b]\subset \mathbb{R}$. A tagged partition of $[a,b]$ is a set $D=\{(t_i,I_i)\}_{i=1}^m$ where $\{I_i\}_{i=1}^m$ is a partition of $[a,b]$ consisting of closed non-overlapping subintervals of ...
3
votes
1answer
152 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,$ ...
3
votes
1answer
88 views

Is partition function increasing function?

I have some exercises which require knowing the number of partitions of particular numbers, so I used some python code which I found on internet to compute the values of the partition function for the ...
1
vote
1answer
50 views

Partitioning a set

I have this question: Is this collection of subsets a partition on the set of bit strings of length 8: The set of bit strings that end with 111, the set of bit strings that end with 011, ...
0
votes
1answer
211 views

How many compositions of $n \in N$ are there where each part is greater than $1$?

Can someone help me with this? Let $n \in N$. How many compositions of $n$ are there where each part is greater than $1$? (Number of parts are not restricted)
1
vote
1answer
37 views

How does this line work in a problem about restricted compositions of $n$?

I'm trying to follow an example problem of calculating how many $k$-part compositions of $n$ are there, with the restriction that each part is at most 5. During the calculation there is this mess: ...
1
vote
0answers
61 views

Restricted Partitions of $n$ [duplicate]

The original question was to find the number of ways to split an integer, $n$, into any number of partitions where each of the parts belong to the set $\lbrace 1,3,4,9\rbrace$. Assuming I did this ...
6
votes
1answer
168 views

Representations of an integer as the sum of other integers

Given a finite set $S$ of (distinct) integers $s_1, \dots, s_n$ and an integer $x$, I'm looking for all representations (where order is important) $$ x=\sum_{i=1}^ks_{t_i} (t_i\in\{1,\dots,n\}) $$ ...
0
votes
1answer
29 views

Partition set to contain the same number of elements distributing the remainder

Given $|B| = 23$ and number of partitions $P=4$. We want to partition the given set $B = B_1\cup\dots\cup B_P$ so that every partition $B_i$ contains the same amount of elements where the remaining ...
1
vote
3answers
320 views

Frobenius coin problem

Suppose that you only have coins worth, say 3 and 5 euros. According to Sylvester result we can find the Frobenius nr $g(3,5)=15-3-5=7$ so 7 is the largest integer that cannot be written as ...
1
vote
2answers
120 views

Enumerate partitions of identical objects

I have a problem concerning enumerating partitions of a set of identical objects. I know, now someone is going to talk about Stirling number of second kind, but I'm quite sure this is not the answer. ...
-1
votes
1answer
70 views

Prove that this set (involving fractional part of any rational number) is a partition of the set of rationals.

For any rational number $x$, we can writte $x=q+\,n/m$ where $q$ is an integer and $0\le n/m<1$. Call $n/m$ the fractional part of $x$. For each rational $r\in \{x : 0\le x<1\}$ ,let $A_r = \{ ...
3
votes
1answer
149 views

Upper and lower integration inequality

I would like to learn how to prove that the following inequality holds. Let $F$ be a bounded function on an interval $[a,b]$, so that there exists $B\geq 0$ such that $|f(x)| \leq B$ for every $x\in ...
3
votes
1answer
47 views

Symmetry of Plancherel measure (for $S_n$)

For each $n \geq 1$ consider the reverse lexicographical order on the set $P(n)$ of partitions of $n$. Example for $n=7$: $$ \begin{pmatrix} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 ...
2
votes
2answers
169 views

Partitions of $n$: proving $p(n+2)+ p(n) \geq 2p(n+1)$

For $n \geq 2$ give an alternative description of $p(n) - p(n-1)$ as the number of partitions of $n$ which have a certain property. I have done that part, it is fine. I have not included it here ...
11
votes
3answers
630 views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
0
votes
1answer
30 views

Partitions of an interval and convergence of nets

Let $\mathscr{T}$ be the set ob partitions $\tau = (\tau_0 = 0 < \tau_1 < \dots < \tau_N = 1)$ of the interval $[0,1]$ (where $N$ is not fixed). This becomes a directed set by setting $\tau ...
5
votes
2answers
188 views

Derivative of Schur function

In his answer to http://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 ...
2
votes
1answer
309 views

Count the number of unique equal sized partitions of a set.

Given the integers $[1, ck]$, they will be partitioned into $c$ subsets of size $k$. I want to count the number of unique versions of each subset (where order matters). Clearly, there are ${ck ...
10
votes
6answers
582 views

Can every infinite set be divided into pairwise disjoint subsets of size $n\in\mathbb{N}$?

Let $S$ be an infinite set and $n$ be a natural number. Does there exist partition of $S$ in which each subset has size $n$? This is pretty easy to do for countable sets. Is it true for ...
0
votes
1answer
29 views

Make a partition that contains a set of points??

I am given a set of $M$ points in a segment (the edges are also points in this set) I would like to partition the segment (with equidistant points), in such a way that my partition contains all these ...
1
vote
1answer
136 views

Generating functions of partition numbers

I don't understand at all why: \begin{equation} \sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1} \end{equation} Where $p_n$ is the number of partitions of $n$. Specifically ...
1
vote
1answer
46 views

Can a p-core of a partition be reached by repeated stripping of p-rimhooks?

in http://mathoverflow.net/questions/42562 I read : "If you strip p-rimhook after p-rimhook off of a partition, this always results in the same p-core, and the choices don't matter." But I must be ...
3
votes
2answers
97 views

Probability distribution of product of integers

I have a scoring system based on 5 factors with integer values from 1 to 5: Score = A * B * C * D * E So the Score can range from 1 to 3125. Each of the factors ...
0
votes
2answers
51 views

Question on combinatorics, partitions. [duplicate]

Let $p$ ($n|$distinct odd parts) be the number of partitions of $n$ into distinct odd parts. Prove that $p(n)$ is odd if and only if $p$($n|$distinct odd parts) is odd by using the theorem on ...
1
vote
1answer
61 views

Partition parts

Consider the partitions of $n$. For $n = 5,7,9,\ldots$, it appears as if the number of pairwise partitions $\{a,b\}$, where both $a$ and $b$ are composite, equals the total number of individual odd ...
3
votes
5answers
341 views

In how many ways i can write 12?

In how many ways i can write 12 as an ordered sum of integers where the smallest of that integers is 2? for example 2+10 ; 10+2 ; 2+5+2+3 ; 5+2+2+3; 2+2+2+2+2+2;2+4+6; and many more
1
vote
1answer
112 views

conjugate partition definition

i would like to understand basic definition of conjugate partition,this is what is said in my book Let $υ = (u_1, u_2, . . . , u_n)$ be a sequence of integers such that $u_1 ≥ u_2 ≥ · · · ≥ u_n ≥ ...