All Questions
Tagged with integer-partitions set-partition
31
questions
3
votes
2
answers
114
views
high school math: summands
Let's say we have a question that asks you to find the amount of all possible integers adding up to a random number, lets just say 1287. However, the possible integers is restricted to explicitly 1's ...
- 31
0
votes
1
answer
31
views
A variant of the partition problem or subset sum problem
Given a target list $T = (t_1, t_2, \ldots, t_N)$ and a multiset $S = \{s_1, s_2, \ldots, s_M\}$, both with non-negative integer elements, $t_k\in \mathbb{N}_>$ and $s_k\in \mathbb{N}_>$, ...
- 125
0
votes
0
answers
28
views
Do we have recurrences for evaluating the Partition Function on Graphs?
Inspired by this question about defining the partition function on non integers, I was thinking about what sorts of other objects can a partition function be defined on.
I noticed that if we have an ...
- 17.5k
0
votes
1
answer
111
views
How to fill a set of container by partition of set?
Let $\{A,B,C,D\}$ be a table with $4$ containers of sizes respectively $5,5,3,2$. Let $\pi=\{B_1,B_2,\cdots B_k\}$ a partition of a set, where $k\in \mathbb{N}$. I wonder how to enumerate the ...
1
vote
1
answer
77
views
Another formulation for Stirling numbers of the second kind
I find another formulation for Stirling numbers of the second kind:
Let $n\ge k\ge 1$. Denote by
$$\mathbb N_<^n := \{ \alpha = (\alpha_1,\cdots,\alpha_n): 0\le \alpha_1\le\cdots\le\alpha_n, \...
- 1,972
0
votes
1
answer
44
views
Is the following Knapsack Variant NP-Hard?
The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
- 193
0
votes
1
answer
76
views
Derivation of Integer Partition from Partition of a Set
Definition.
Let $A$ be a non-empty set. A collection $P$ of subsets $A_1,A_2,A_3,\ldots$ of $A$ is called a partition of $A$ if the following three conditions hold:
$\emptyset \notin P$,
$A_1 \cup ...
- 447
0
votes
1
answer
201
views
Link Between Integer Partition and Partition of a Set
Definition.
Let $A$ be a non-empty set. A collection $P$ of subsets $A_1,A_2,A_3,\ldots$ of $A$ is called a partition of $A$ if the following three conditions hold:
$\emptyset \notin P$,
$A_1 \cup ...
- 447
2
votes
1
answer
138
views
A number partition problem
I have encountered the following interesting integer partitioning problem.
Let $n,k,t \in \mathbb{N}$ be given parameters and let $S_1,\ldots, S_t$ be a partition of the numbers $1,2,\ldots,n$ such ...
- 193
1
vote
0
answers
127
views
Minimizing the magnitude of the sum of a vector of complex numbers with an integer constraint
Let $h_{1}, ..., h_{N} \in \mathbb{C} $
Consider minimizing the function below:
$ \min \left| \sum\limits_{i=1}^N h_{i} x_{i} \right| $
with the constraints $x_{i}^2 = 1$
i.e., $x_{i}$ can only take ...
- 11
0
votes
1
answer
260
views
Number of integer $k$-tuples with sum $n$? [duplicate]
I wish to know how many elements are there in the set
$$
S_{n,k} = \left\{(n_1,\ldots, n_k): \forall i,n_i \in \mathbb Z, n_i \geq 0, \sum_i n_i = n\right\}.
$$
It appears to me that we have a simple ...
- 7,534
-3
votes
4
answers
129
views
Find a minimal set whose elements determine explicitly all integer solutions to $x + y + z = 2n$
Is there a way to exactly parameterise all the solutions to the equation $x + y + z = 2n$, for $z$ less than or equal to $y$, less than or equal to $x$, for positive integers $x,y,z$?
For example, for ...
- 67
3
votes
1
answer
109
views
Distributing $n$ distinct objects into $m$ types of urns with $k_1,k_2...k_m$ urns of each type
I came accross this (rather complex?) combinatorial problem:
I have $18$ distinct objects, $3$ red urns, $7$ blue urns, and $11$
green urns. In how many ways can I distribute the objects into those
...
- 1,022
2
votes
1
answer
415
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.
Question:
Given a set of positive, and negative numbers, how do I time optimally find two numbers whose sum is the mathematical ...
- 173
1
vote
1
answer
121
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}{...
- 3,679
0
votes
0
answers
28
views
Number of partitions with limited cardinality [duplicate]
We are given $k$ urns labeled from $1$ to $k$. What is the number of ways to put $n$ indistinguishable balls into the $k$ (distinct) urns, given that each urn has a limited capacity equal to $c$, ...
- 149
2
votes
2
answers
272
views
Find a bijection between the $(n-1)$ paths and the $n$-paths which have no downramps of even length.
So here is the Question :-
A Dyck $n$-path is a lattice path of n upsteps $(x,y)$ $\rightarrow$ $(x + 1,y + 1)$ and $n$
downsteps $(x,y) \rightarrow (x + 1,y-1)$ that starts at the origin and never ...
- 314
-1
votes
1
answer
2k
views
Consider the set $A=\{1,2,3,4,5,6,7,8,9\}$.A partition $\Pi $ of $A$ is collection of disjoint sets whose union is $A$
Consider the set $A=\{1,2,3,4,5,6,7,8,9\}$.A partition $\Pi $ of $A$ is collection of disjoint sets whose union is $A$. For example, $\Pi_1=\{\{1,2\},\{3,4,5\},\{6,7,8,9\}\}$ and $\Pi _2 =\{\{1\},\{2,...
- 1,248
0
votes
1
answer
795
views
How many way to partition a set of n number into k subsets (empty subset is allowed)
I am working on finding the upper bound iterations of k-means algorithm. Many research show that the trivial upper bound is $O(k^n)$ since it can be shown that no clustering occurs twice during the ...
0
votes
0
answers
149
views
Find all combinations of numbers from {x1,x2,...,xn} that sum of to sum S
Given a list of some integers, I would like to find every combination that can be summed to some sum S.
For example for the sum S=16, and the list of integers I={3,4,5}, I'd expect to get:
5,4,4,3 (=...
2
votes
1
answer
98
views
2-split of $n$ is $\left\{ \lfloor \frac{n}{2} \rfloor,\lceil \frac{n}{2} \rceil \right\}$. What about 3, 4, ...?
Clarification: $k$-split of $n$ is an ordered integer sequence $\left\{ a_1,\cdots,a_k \right\}\quad \text{s.t.}$
$0\le a_1\le\cdots\le a_k$
$a_1+\cdots+a_k=n$
${\left(a_k-a_1\right)}$ is minimized.
...
- 195
0
votes
0
answers
19
views
Constructing a partition of a finite nonempty set from a partition of its cardinality
Let $E$ be finite nonempty set of cardinality $n$. Let $(k_i)_{i\in I}$ be a finite family of integers $>0$ such that
$$\sum_{i\in I} k_i=n.$$
Since $|E|=n$, there exists a bijection $x:[1,n]\...
-1
votes
1
answer
115
views
I can not find out a formula for this :
Between 1 and 45, (and included, 1 and 45) ;
How many --5 set combinations-- are there from 1 to 45 with a total of 155?
*What are these combinations ?
(PS: each number can only be written once )
...
1
vote
0
answers
37
views
An interesting way of partitioning with inner ordered combinations
Assume $ K $ labeled blocks $ s_1, s_2, \dots, s_K $ ($ s_1 < s_2 < \dots < s_K $) that arrive sequentially and need to be accomodated as they arrive in $ N $ containers (partitions with ...
- 778
3
votes
2
answers
241
views
Ways of distributing passengers in ships
I need help with the following combinatorial problem. There are $ K $ passengers and $ K $ ships. The passengers are denoted by $ U_1, U_2, \dots, U_K $. The objective is to find in how many ways the $...
- 778
2
votes
1
answer
480
views
Find Integer Partition using only integers belonging to S = { 1, 2, 3 }
I spent all afternoon looking for this but I wasn't able to find anything, so...
Is there a formula to know the NUMBER of partitions with a constraint on the integer domain ?
E.g.: Find the number of ...
- 158
0
votes
1
answer
126
views
What is the appropriate weight ($W_k$) (for two arbitrary partitions)?
I already asked a similar question, And from the answer I received, another question came to my mind.
A positive integer can be partitioned, for example, the number 7 can be partitioned into the ...
- 41
3
votes
1
answer
67
views
Is this true for every partitioning?
I have two categories (category1 and category2 ) and The size of both categories is equal to each other. if we partition each categories arbibtrary .Is this proposition proven? or rejected?
$n_T \...
- 41
-1
votes
1
answer
89
views
Number of ordered set partitions with subset size $\leq 3$
For $n \ge 0$, let $h_n$ be the number of ways of taking $n$ (distinguishable)
rabbits, putting them into identical cages with one to three rabbits per
cage and then ordering the cages in a row. Find ...
- 434
0
votes
2
answers
992
views
disjoint Partition of sets
Hello I'm a bit confused by what this definition means
$$DT_n = \{ \{C,D \} \mid C,D ⊆ S_n \text{ and } C \cup D = S_n \text{ and } C \cap D = \emptyset \} $$
where $S_n = \{1,2....n\}$ and n is a ...
- 5