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

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
74 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
207 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 ...
9
votes
2answers
384 views

Closed-form Expression of the Partition Function $p(n)$

I feel like I have seen news that a paper was recently published, at most a few months ago, that solved the well-known problem of finding a closed-form expression for the partition function $p(n)$ ...
2
votes
1answer
125 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
108 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
0answers
154 views

Jordan Measure, Semi-closed sets and Partitions

From earlier question here. Consider $$\mu \left( (0,1) \cap \mathbb Q \right) = 0$$ where $$(0,1) = \left(0,\frac{1}{3}\right)\cup \left[\frac{1}{3}, \frac{2}{3}\right] \cup \left(\frac{2}{3}, ...
3
votes
1answer
186 views

Bell number. Combinatorial proof.

$B_m$ is the Bell's number (the # of all partitions of the set $m$) and $B_m^*$ is the number of partitions of set $m$ with no singleton block We need to prove that $B_m = B_m^* + B_{m+1}^*$. ...
3
votes
0answers
84 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 ...
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 ...
1
vote
2answers
75 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 ...
2
votes
1answer
88 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 ...
0
votes
1answer
315 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 = ...
6
votes
1answer
225 views

What is the number of ways to choose x groups from y items? (partitions with x cells of a multiset)

Where a group can consist of 1 or more items, groups don't have to be equally sized and items can be duplicates. Example - Choose 3 groups: Items: 1 2 2 3 Groups: (1) (2 2) (3) (1 2) (2) (3) (3 ...
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 ...
0
votes
0answers
282 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) ...
2
votes
3answers
1k 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 ...
2
votes
1answer
120 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. ...
1
vote
1answer
114 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 ...
1
vote
1answer
138 views

A partition of an interval to reduce the difference between the upper and lower Darboux sums

Let $$ f(x) = \begin{cases} 2x+1, & x\in [2,4] \\ 7-x, & x\in(4,4.5) \\ 3, & x \in[4.5,6] \end{cases} $$ For $q = 1/4$, find a partition of $[2, 6]$ such that the difference between the ...
3
votes
1answer
78 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 ...
4
votes
1answer
280 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: ...
0
votes
1answer
65 views

General term of this sequence

I wanted to know the General term or the function to generate this sequence I found on OEIS. It is the number of ways to express $2n+1$ as $p+2q$; where $p$ and $q$ can be odd prime number and even ...
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,$ ...
11
votes
3answers
527 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 ...
3
votes
1answer
83 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
48 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, ...
1
vote
3answers
297 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 ...
0
votes
1answer
202 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
36 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
2answers
114 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
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 ...
3
votes
1answer
148 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
46 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
164 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 ...
5
votes
2answers
181 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 ...
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 ...
2
votes
1answer
290 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
534 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
117 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
44 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
94 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
50 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
58 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 ...
-2
votes
1answer
156 views

From a Generating Function find $R(x)$ as an infinite product of Quotients

Let $r(n)$ be the number of partitions of $n$ so that no multiple of $3$ appears as a part. For example, $r(8) = 13$. Let $R(x) =\sum_0^\infty r(n)x^ n $ be the generating function for $r(n)$. Find ...
-2
votes
1answer
203 views

Find a form for $Q(x)$ as an infinite product of polynomials

Let $q(n)$ be the number of partitions of $n$ so that no part appears three or more times. For example, $q(8) = 13$ Let $Q(x) = \sum\limits_{n=0}^\infty q(n) x^n$ be the generating function for ...
3
votes
1answer
213 views

bijection between number of partitions of 2n satisfying certain conditions with number of partitions of n

Suppose $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ is a partition of $2n$ where $n\in\mathbb N$ satisfying the following conditions: (1) $\lambda_k=1$. (2) $\lambda_i−\lambda_{i+1}\leq 1$ for ...
1
vote
1answer
97 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 ≥ ...