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.
1
vote
1answer
155 views
Integer Partitions Formulas [duplicate]
Possible Duplicate:
Identity involving partitions of even and odd parts.
How would I go about to show the following: Let $pe(n)$ be the number of partitions of size n with an even number of ...
2
votes
3answers
69 views
Number decomposition
Recently I encountered a problem I was not familiar with. So hope someone can help me for this.
Here is the problem. Given any odd integer, how many different ways of decomposition into sum of three ...
0
votes
2answers
66 views
Combination Question
I currently have an open question about counting the possible ways of summing numbers. I am still exploring all the ideas provided - those within my level of understanding. This is a question ...
1
vote
1answer
500 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 ...
0
votes
1answer
54 views
What is minimum Eulerian partition?
I have a homework in my graph course. It asks something about minimum Eulerian partition but it doesn't give any information about it. I googled it but couldn't come up anything useful and clear. Is ...
1
vote
1answer
72 views
Nonnegative integers with unique restricted partitions
I have come over the following problem in elementary number theory: suppose that a positive integer $k$ is given. Is it possible to find, for every such $k$, a nonnegative integer $N(k)$ and a set of ...
0
votes
0answers
60 views
Knapsack like problem for product of distinct primes
While looking into ways of generating certain kinds of pseudo-random number sequences I came up with the issue of finding the maximum of products of distict primes with a sum less than N. I'm ...
0
votes
2answers
226 views
Distribution of the sum of a multinomial distribution
I have distilled an error analysis problem into the following:
I have a multinomial distribution, $X$, consisting of $n$ independent trials where each trial takes on the values $\{0,1,\ldots,k-1\}$ ...
3
votes
2answers
127 views
Enumeration of partitions
The Stirling number of the second kind $S(n,k)$, where
$S(n,k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\left(\begin{array}{l}k\\j\end{array}\right)j^n$
Gives the number of unique unlabeled, ...
2
votes
3answers
272 views
Partition of a set of size n into subsets of size 1 and 2.
Before I ask the question, I must admit that combinatorics has never been my forte.
I am given a set X of size $n$, we may assume assume $X=\{1,2,...,n\}$. I want to count the partition of this set ...
0
votes
0answers
50 views
Set of N Periodic & Non Negative Integer Sequences forming by summation, the series of Whole Numbers.
I'm interested in Set of N non negative and periodic/oscillating integer sequences,
that once summed forme the serie of whole numbers: 0,1,2,3,4,5,...,K
For exemple:
With N = 2 (A,B), K = 7 and ...
-2
votes
1answer
72 views
Count the number of integer solution to $\sum_{i=1}^ {4}{a_i\times b_i} \geq 8 $? [closed]
Count the number of integer solution to $\sum_{i=1}^ {4}{a_i\times b_i} \geq 8 $ such that
condition 1: $1 \leq a_i \leq 7$
condition 2: $1 \leq b_i \leq 4$
condition 3: $\sum_{i=1}^{4} {a_i} = ...
0
votes
1answer
90 views
Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ [closed]
Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ such that
condition 1: $1 \leq a_i \leq 7$
condition 2: $1 \leq b_i \leq 4$
condition 3: $\sum_{i=1}^{2} {a_i} = 8$
...
0
votes
0answers
98 views
Give an expression for lower and upper sum, concluding $f$ is integrable
$f : [a,b] \rightarrow \mathbb{R}$ is non-increasing, which means that $f(y) \le f(x)$ when $y>x$
The two questions are :
Give an explicit expression (without infima and suprema) of ...
1
vote
3answers
208 views
Partition of a set, definition not clear
From wikipedia:
Equivalently, a set P is a partition of X if, and only if, it does not contain the empty set and:
The union of the elements of P is equal to X. (The elements of P are said ...
1
vote
2answers
293 views
Equivalence Relations and Partitions
My university "textbook" for discrete math is Schaum's Outline. In this outline he goes over Equivalence Relations and Partitions, and I got confused at a particular theorem.
From the book:
Theorem ...
4
votes
3answers
629 views
How many ways to merge N companies into one big company: Bell or Catalan?
There's a famous interview question variously credited to Microsoft, Google and Yahoo:
Suppose you have given N companies, and we want to eventually merge
them into one big company. How many ...
1
vote
1answer
68 views
Combinatorics problem based on Ferrers graph
Need help with this proof using Ferrers' graph or otherwise.
Show that the number of partitions of $r+k$ into $k$ parts is equal to
The number of partitions of $r + {k+1 \choose 2}$ into $ k $ ...
3
votes
1answer
34 views
cosets aren't forming a partition?
If you have a group $G$ and $H \leq G$, the cosets of $H$ should partition $G$.
Suppose $G=\mathbb{Z}_2\times\mathbb{Z}_4$ and $H=\langle (0,1)\rangle = \{(0,0), (0,1),(0,2),(0,3)\}$. Then both ...
1
vote
2answers
467 views
How many ways you can make change for an amount
I am looking for a formula or at least something to use when trying to compute how many ways I can make change for an amount.
Example: there are $3$ ways to give change for $4$ if you have coins ...
1
vote
3answers
203 views
Finite or infinite set?
Due to my not-so-advanced math skills, this question may take a few attempts to state clearly:
Consider the unordered pair (2-tuple) partitions of n (e.g. with n=4, we have {{4,0},{3,1},{2,2}}). ...
0
votes
0answers
19 views
Reference request for papers concerning solid partitions.
I am looking for journal articles concerning solid partitions, which are the three-dimensional analogue of integer partitions.
Specifically, I am interested in papers which enumerate solid partitions ...
3
votes
0answers
52 views
Ordered integer partition [duplicate]
Possible Duplicate:
Proving an equality involving compositions of an integer
A sequence of natural numbers $\langle a_1,\ldots,a_k \rangle$ is an ordered partition of $n$ if ...
2
votes
1answer
52 views
Partitions of binary numbers into binary numbers with fixed digits?
If we are to have (two, for example) binary numbers, such that their sum is $100111010_2$, and given that the first number has 5 ones, and the second number has 3 ones, can I find the numbers that ...
0
votes
1answer
29 views
Partitioning a sequence of numbers based on a percentage
I have a sequence $s$ of rational numbers where $|s|=n$. I am given a percentage $p$ to partition the sequence $s$ into $\frac{1}{p}$ parts, such that each part contains $p\%$ number of elements of ...
1
vote
2answers
139 views
Integer partitions with restrictions for elements [duplicate]
Possible Duplicate:
Same number of partitions of a certain type?
Prove that the number of partitions of $n$ without elements divisible by $4$, is equal to the number of partitions of $n$ ...
3
votes
1answer
350 views
Number of partitions of a set with size constraints
One of my students made some experiments on partitions of sets. He found some results and I asked him, if he can prove some statements. After two weeks he had no result, so maybe one of you can help.
...
4
votes
2answers
182 views
Find all ways to factor a number
An example of what I'm looking for will probably explain the question best. 24 can be written as:
12 · 2
6 · 2 · 2
3 · 2 · 2 · 2
8 · 3
4 · 2 · 3
6 · 4
I'm familiar with finding all the prime ...
9
votes
1answer
272 views
Average Number of Blocks in a Partition Containing a Large Block
Notation
Let $[n]$ denote the set of integers from 1 up to $n$,
inclusive.
Let $A_n$ denote the average number of blocks over all partitions of $[n]$.
Let $B_n$ denote the number of partitions of ...
3
votes
1answer
163 views
Lower bounds for the partition function
In this question we consider the partition function $p(n)$ - that is, the number of ways to express $n$ as a sum of positive integers.
One easy exercise is to show that $$ p(n) \geq 2^{\lfloor ...
1
vote
3answers
112 views
Probability - multinomial partitioning
Question:
Joe is in his hunting blind when he locates $20$ geese, $25$ ducks, $40$ eagles, $10$ cranes, and $5$ flamingos. Joe randomly selects six birds to target, what is the probability that at ...
0
votes
5answers
349 views
General questions about equivalence classes and partitions
1) If a set is partitioned into non-overlapping, non-empty subsets, then those subsets are equivalence classes. If each element in a set is unique, how can a set be partitioned into subsets with ...
1
vote
0answers
79 views
Shifted Young tableaux & Hook numbers & Bulgarian Solitaire
I would like to find articles or documentation regarding this process:
Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
1
vote
1answer
92 views
Integer Partition by Counting Repetition : Conjecture ??
I would like to find informations regarding this way of doing Integer Partitions or
this conjecture,
Suppose you have all the ordered partitions of 5:
5
4 1
3 2
2 2 1
3 1 1
2 1 1 1
1 1 1 1 1
Then ...
2
votes
4answers
255 views
Two hard number partition problems
For every positive integer $n$, let $p(n)$ denote the number of ways to express $n$ as a sum of positive integers. For instance, $p(4)=5$. Also define $p(0)=1.$
Problem 1.
Prove that ...
1
vote
1answer
118 views
Two number partition problems
Let $p_k(n)$ be a number of ways to express $n$ as a sum of $k$ positive integers. For example $p_2(3)=1$.
Problem 1. Prove that following recurrences are correct:
...
1
vote
2answers
238 views
Proof of a Proposition on Partitions and Equivalence Classes
I stumbled upon a seemingly rudimentary proposition that I am having trouble writing out a proof for. The proposition goes something like,
Proposition: If $\{A_i|i\in I\}$ is a partition of ...
1
vote
2answers
106 views
Proving a relation between 2 sets as antisymmetric
Let $U = \{1,...,n\}$
And let $A$ and $B$ be partitions of the set $U$ such that:
$\bigcup A = \bigcup B = U$
and $|A|=s, |B|=t$
Let's define a relation between the sets $A$ and $B$ as follows:
$B ...
3
votes
0answers
57 views
Change the money [duplicate]
Possible Duplicate:
Making Change for a Dollar (and other number partitioning problems)
The problem is:
How many are ways to change one dollar using coins: 5,10,20,50 cents?
The ...
3
votes
2answers
262 views
Keep getting generating function wrong? [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 ...
5
votes
3answers
338 views
Putnam Problem: Partitioning integers with generating functions
We were given the following A-1 problem from the 2003 Putnam Competition:
Let $n$ be a fixed positive integer. How many ways are there to write $n$ as a sum of positive integers, $$ n= a_1+a_2+ ...
2
votes
1answer
134 views
How many circular distinct compositions of $n$ into $k$ parts at most $g$
how many circular distinct sequences (e.g. $(4124)\equiv(4412$)) are there that sum up to $n$, have $k$ elements may be non-negative integers at most $g$?
In other words: we're looking for the number ...
2
votes
3answers
191 views
Does there exist a function whose range is the complement of the range of this function?
Does this function have a complement on the positive integers in the sense that the range of the complement should be the complement of the range of the function?
$$\frac{1}{8} \left(1-(-1)^n+2 n ...
1
vote
2answers
114 views
How can I count partitions of X having N items?
I need to count the possible partitions where sum of it's members is X, but every set has N items.
For example X=5 and N=4:
{ 1,1,1,2 }
X=5, N=3:
...
0
votes
1answer
98 views
Conditional Combinations
Asking this question on SO, I have been advised to post it here. I will be using Javascript to implement :
Please consider a row of size 12. On that row, I want to place some items that have 3 ...
0
votes
0answers
106 views
Matrix & Partition & Natural Number & Pattern
I would like to know if someone know, how is called a matrix M*N, where m represents the row index in the matrix and the sum of the N columns at this row. Meaning that each row represents a possible ...
5
votes
0answers
121 views
Invariant element in the tensor product of rectangular Specht modules?
Denote by $\mathfrak{S}_k$ the symmetric group on $k$ elements. Let $\lambda=(n^2\times n)=(n^2,\ldots,n^2)$ be a rectangular partition and $k=n^3$. Denote by $S_\lambda$ the Specht module ...
2
votes
2answers
99 views
a formal name of this partition
Consider a set $A=\{1,2,3,4,5\}$,
is there any terminology for the following partitions of $A$ ?
(1) $A=\{ \{1\},\{2\},\{3\},\{4\},\{5\} \}$
(2) $A=\{\{1,2,3,4,5\}\}$.
2
votes
0answers
103 views
Generating Function of Integer Partition Such that at Least One Part is Even
I've been having a few issues coming up with a generating function for an integer partition such that at least one part is even. What I have got so far is:
The generating function with no ...
0
votes
1answer
34 views
The “theory of compound partitions”
I was reading a sort of mini-bio on Sylvester the other day and a "Theory of Compound Partitions" was mentioned in the discussion of his research interests. I wanted to ask, is this the same or the ...
