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
0answers
4 views

On t-core partitions

How exactly can one define what is known as a t-core partition? I know (vaguely) that it involves the definition of what is known as "Hook numbers". Anyone cares to provide a link or explain it?
3
votes
4answers
24 views

Number of sequences formed of $k$ pairwise disjoint subsets of a set of $n$ elements is $(k+1)^n$.

Let $S=\{1,2,\dots,n\}$ and $P(S)$ the family of the $2^n$ subsets of $S$. Prove that the number of sequences $(S_1,S_2, \dots, S_k )$ formed by the subsets of $S$ that verify that $S_i \cap S_j = ...
1
vote
0answers
25 views

Terminology: Opposite of “refinement”

Let A be a partition of a set, and B a refinement of A. Fill in the blanks: A is a __________ of B. I know that A is coarser than B, but how does one turn that into a noun?
0
votes
2answers
21 views

Proving a family of sets is a partition of the set of integers.

I am trying to show that for $E_n = \{10n, 10n + 1, 10n + 2 . . . , 10n + 9\}$, $\{E_n\}$, $n ∈Z$ is a partition of $ Z$. Should this be broken down into cases or is there a more general way to ...
2
votes
0answers
40 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

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 ...
0
votes
0answers
25 views

dot diagram prove

I have to prove theorems using dot diagrams. a.- $P_n(k) = p_n(k-n)$ b.- $p_n(k) = p_{n-1}(k) + p_n(k-n)$ c.- The number $P_n(k)$ of partitions of $k$ into exactly $n$ parts is equal to the number ...
3
votes
0answers
64 views

Elementary proof of Ramanujan's “most beautiful identity”

Ramanujan presented many identities, Hardy chose one which for him represented the best of Ramanujan. There are many proofs for this identity. (for example, H. H. Chan’s proof, M. Hirschhorn's ...
1
vote
0answers
17 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?
0
votes
0answers
42 views

Proof of Ramanujan's Identities of Euler's Function

Consider Euler's Function defined as (and not to be confused with the totient!) $$ \phi(x) = (1-x)(1 - x^2) (1 - x^3 ) .... = \prod_{i=1}^{\infty} \left[(1 - x)^i \right] = (1;x)_{\infty}$$ ...
0
votes
0answers
19 views

Counting unordered partitions on nested concentric disks

The idea is to think of each layer outside of the [core] as a rotatable disk and then only count a single member from each of the resulting equivalence classes, which I think can be done by requiring ...
1
vote
1answer
48 views

Sample, randomly & uniformly the partitioning of $n$ objects into $K$ groups

I wish to sample randomly and uniformly from the set of partitions of $n$ objects into $K$ groups where the number to be assigned to each group, $n_k$ ($k = 1, 2, \dots, K$) is known. I know that the ...
1
vote
1answer
45 views

Partitioning a set to get a sum

I have a set of numbers: 2,2,4,4,4,4,4,4,6,6,6,6,6,6 I want to enumerate the possible ways to partition this set into 4 groups, each of which sum to 16. How can I approach this short of brute force? ...
2
votes
0answers
20 views

Link between partition function and ordered partition function

The partition function $p(n)$ measures the number of partitions of $n$, or the number of ways in which natural numbers can be summed to produce $n$, without regard to order. For example, the ...
1
vote
1answer
26 views

Generating function for set partitions

Let $k$ be fixed. For every $n$ denote by $p_{\leq k}(n)$ the number of partitions of the integer $n$, for which each part is at most $k$. a). Compute $p_{\leq 3}(5)$ b). Compute the generating ...
3
votes
0answers
45 views

Counting the number of partitions that are a distance d away from a fixed partition.

Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N ...
0
votes
0answers
17 views

Can I partition a non-separable set?

This question flashed in my mind, as I was studying quotient partition of a set. Is there any non-separability condition for which a topological set cannot be partitioned? Particularly, I tried ...
0
votes
1answer
45 views

Prove that A001399 == A069905

While solving PE and reading SICP I found, that there are two problems, that produce the same OEIS sequence: http://oeis.org/A001399 is a number of partitions of n into at most 3 parts ...
0
votes
0answers
46 views

Prove; regarding partitions and refinements

If $ f $ is a bounded function, then for every $ \epsilon >0 $ there exists a partition of a real interval $ X $ such that if $ Y $ is a refinement of $ X $. Why is this true?
0
votes
2answers
45 views

Prove: Partitions and refinements

Problem: Let $ R $ be the set of partitions of a real interval. Then for all elements in $ R $, every pair of elements has an upper bound. I am having trouble structuring the proof; and intuitively ...
1
vote
1answer
30 views

A fast algorithm for a simple multi-objective minimization?

I have a set $S$ consists of n (arbitrary) integer numbers which I want to partition into $k$ subsets $S_i$ each of size $\frac{n}{k}$ (assume $k$ divides $n$). Let $A$ be the arithmetic mean of ...
0
votes
0answers
30 views

Generalization of Catalan numbers

I am looking for some kind of function describing the number of non-crossing partitions similar to those described by the Catalan numbers. Let's say $C_3$ would be the third Catalan number. $C_3=5$ ...
0
votes
1answer
13 views

Counting resticted partitions of a multiset with additional restrictions

Say I have some multiset of integers, for example $M1=\{6,6,4,4,4,2,2\}$. I have a second multiset that consists of some set of valid sums derived from picking without replacement from $M1$, say for ...
1
vote
0answers
29 views

Does Euler's recurrence relation for partitions imply that the partition function grows exponentially

Can one, just by manipulating the series, demonstrate that the partition function must be growing exponentially or at least that it is unbounded by any polynomial? If so, then how would it be done. ...
1
vote
0answers
16 views

What is wrong with this “inference” about partitions?

Given that: $p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+⋯$ Why can one not state: $p(n)≥p(n-1)+p(n-2)-p(n-5)-p(n-7)$ Here is the logic: the subsequent 2 terms of the relation are additive and the 2 ...
1
vote
0answers
21 views

Famous Arithmetic property of lotteries - restricted partition of integer into exactly k distinct parts between a given set

I would like to find a complete explanation regarding a famous arithmetic property of lotteries : Let´s say a friend of us is a regular player of a lottery where 5 numbers are taken from a box ...
1
vote
0answers
20 views

Determining probabilities of set of independent experiments from probability of different subsets?

I have a population C of candidates C1..Cn An event will occur to Ci with unknown probability Pi (Pi are independent) The population is divided into disjoint sets S1..Sm For each sub set Si, P(Si) is ...
-1
votes
1answer
50 views

What is the difference between decomposing a number and partitioning a number?

I see that the question has been answered for SETS in "The Decomposition VS. The Partition of a set" but I would like good definitions that distinguish between these terms when used for NUMBERS. I ...
1
vote
0answers
82 views

Is every integer $\geq5$ the sum of two primes and a power of a prime?

Is every integer $\geq5$ the sum of two primes and a power of a prime (where $1$ is included in the prime powers)? I don't really expect someone to prove this here, but I wonder if the question has ...
1
vote
1answer
55 views

Number of Partitioning a deck with m cards in n types into n-element sets.

For exsample, There are 2cards in 3type. AA,BB,CC. Partition 6cards into 2 3-element sets. [AAB,BCC],[AAC,BBC],[ABB,ACC],[ABC,ABC],... 4 ways or Partition 6cards into 3 2-element sets. ...
0
votes
1answer
27 views

Partitioning elements into sets

How many ways are there to partition $n$ unique elements into $2$ sets? What about for $k$ sets? I am specifically interested in how to calculate this for varying values of $n$. Moreover, what if ...
0
votes
0answers
32 views

the number of ways a planar graph can be partitioned

i have a connected planar graph to cut into k parts and want to know how many possible solutions there are. it clearly depends on the shape of the graph since nodes all in a row cannot be partitioned ...
1
vote
1answer
39 views

Solving the equations $x_1= 4 x_2$ and $x_3= 5 x_2$, with the sum of all three being $150$

Here is the problem. A set X is partitioned into subsets x1, x2, and x3. The number of elements in x1 is 4 times the number in x2. And the number in x3 is 5 times the number in x2. If n(x)=150, ...
2
votes
2answers
54 views

What is the number $p(n)$ of partitions of an abundant number $n$ into distinct, proper divisors of $n$?

For lack of a better symbol, $p_{\sigma\tau}(n)$ (feel free to suggest something better). For example, $p_{\sigma\tau}(12) \geq 2$ since $12 = 1 + 2 + 3 + 6 = 2 + 4 + 6$. Of course if $n$ is ...
0
votes
1answer
80 views

Generating Functions of Partitions?

Show that $2(1-x)^{-3} [(1-x)^{-3} + (1+x)^{-3}]$ is the generating function for the number of ways to toss $r$ identical dice and obtain an even sum. Workings: I'm not too sure on this problem. ...
2
votes
2answers
51 views

how interpret this partition identity?

use the symbol $P(N)$ to denote the set of all partitions of a positive integer $N$ and denote by $P_k$ the number of occurrences of $k$ in the partition $P \in P(N)$, so that $$ N = \sum kP_k $$ by ...
2
votes
0answers
38 views

how to count possible planar bipartitions?

i want to find out what small fraction of a solution space a metaheuristic search is actually covering. this case comes down to the number of possible bipartitions for a non-bipartite, undirected ...
2
votes
1answer
71 views

How to find the restricted partition of n into k *distincts* parts between a finite set [1;r]?

It seems to be an opened question. Indeed, it is easy to find: the number of partitions of n into k distinct parts the number of partitions of n into k parts the number of partitions of n into k ...
1
vote
0answers
32 views

How to partition into more than two subsets

Given a set $A$ of numbers and the number of desired subsets, $n$, how can I divide the numbers in set $A$ into $n$ subsets where each number in $A$ is used in one and only one subset and the sum of ...
0
votes
1answer
50 views

Coin Change Problem - Find the number of ways to make change

I read the solution here http://www.algorithmist.com/index.php/Coin_Change basically to find the number of ways to make change: We are trying to count the number of distinct sets. it says " Since ...
3
votes
1answer
53 views

Does and where to does $\lim_{n\to\infty}\sum_{m} \prod_k \frac{1}{\lambda_{k,m}!}$ converge?

Given $n$ you get a number of partitions of $n$ and let's denote $\lambda_{k,m}$ to be the $k$th part of the $m$th partition. Now I built the following sum, that stimulated the following question: $$ ...
1
vote
0answers
34 views

Partitioning items into fixed size sets

I have the following problem: Given $n$ items, where each item has weight $w_{i}$, $i=1,2\ldots n$, what is the number of ways to partition these items into boxes of fixed size $C$, such that the sum ...
4
votes
0answers
91 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 ...
4
votes
1answer
49 views

How to denote sum over partitions?

How does one denote a sum of partitions of an integer when writing an article? For example, I have a formula regarding an integer-valued variable (say q=5), and I need to write an expression of the ...
1
vote
0answers
44 views

partitions of finite set in same-size parts having at most one element in common

Given g ≥ 2, k ≥ 1 and a population of p = kg workers, I'm trying to figure out the longest series of work shifts such that: during each shift, all workers work in k teams of g people; any two ...
1
vote
0answers
52 views

Expansion for r-associated Stirling numbers of the second kind

I am looking for a paper or guidance for expanding the r-associated Stirling numbers of the second kind $S_r(n,k)$. $S_r(n,k)$ is the number of ways to partition a set of n objects into k subsets, ...
1
vote
0answers
42 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = ...
2
votes
2answers
93 views

Counting Set Partitions with Constraints

I'm trying to count set partitions under the following constraints: The number of partitions on $n$ elements where the largest cell(s) have exactly $k$ elements All cells have at least two elements ...
0
votes
0answers
47 views

Truncation of partitions generating function question

$A (x)$ is the generating function for partitions. $B(x)=\sum_{n=0}^{\infty}b_nx^n $ $$b_n =\binom{\text{number of partitions of }n}{\text{into an even number of parts}}-\binom{\text{number of ...
1
vote
1answer
29 views

Union of each family is not the whole set

Let $n\geq k>0$, and consider all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. We want to partition it into families so that the union of each family is not equal to $A$. At least ...
6
votes
1answer
207 views

Number of Sets of Partitions

I looked at the partitions of numbers, like let's say $n=5$. You get $$ \begin{eqnarray} 5&=&5\\ \hline &=&4+1\\ &=&3+2\\ \hline &=&3+1+1\\ &=&1+2+2\\ \hline ...