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

2
votes
2answers
446 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
620 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
66 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 ...
4
votes
2answers
963 views

Keep getting generating function wrong (making change for a dollar) [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 ...
7
votes
3answers
815 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
252 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
222 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
153 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
367 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
136 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 ...
6
votes
0answers
233 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 ...
3
votes
2answers
144 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
263 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
38 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 ...
1
vote
0answers
165 views

Number of solutions (excluding permutations of variables' values) and solving in distinct positive integers the following system of equations

Questions and important info in italics, very important ones in bold. Here we have the system; $V_{1}+V_{2}\cdots+V_{k}=A$ and $V_{1}^{2}+V_{2}^{2}+\cdots +V_{k}^{2}=B$ where $V_{1}$, $V_{2}$, etc. ...
1
vote
0answers
124 views

Partition of unity. Functional analysis

Need to find partition of unity in case of oparator $A_{f}(x)=(|x-1|+x)f(x)$. Operator $A \in L_{2}[0,2]$ Partition of Unity is set of operators $E_{\lambda}=E((- \infty,\lambda]) $, where ...
5
votes
2answers
362 views

Number of partitions contained within Young shape $\lambda$

It is well known that the number of partitions contained within an $m\times n$ rectangle is $\binom{m+n}{n}$. Furthermore, it is not difficult to calculate the number of partitions contained within a ...
3
votes
2answers
221 views

Count the number of integer solution to $\sum_{i=i}^{n}{f_ig_i} \geq 5 $

How to count the number of integer solutions to $$\sum_{i=i}^{n}{f_ig_i} \geq 5$$ such that $\displaystyle \sum_{i=1}^{n}{f_i}=6$ , $\displaystyle \sum_{i=1}^{n}{g_i}=5$ , $\displaystyle 0 \leq f_i ...
4
votes
3answers
3k 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 ...
1
vote
1answer
654 views

partition a number N into K tuples

Given an integer $N ≥ 0$ and an integer $K ≥ 0$, how many tuples $(n_1,\ldots,n_k)$ are there such that $n_i ≥0$ and $\Sigma n_i = N$? In other words, how many way can you "partition" $N$ into $K$ ...
3
votes
1answer
896 views

proving that $P$ is a partition

On a practice exam, our teacher gave us this answer as the third point in proving: Let $n$ be a positive integer and let $P = \{$equivalence classes for is-congruent-to-mod-$n\}$. Show that $P$ is ...
2
votes
0answers
37 views

order of elements in a partition using Maple

I determined this whole partition but I just want to have the finer the partition for example: I have this ...
6
votes
1answer
205 views

When is the sum of first $n$ numbers equal to the sum of the next $k$ numbers?

When is the sum $1+2+\cdots + n = (n+1) + (n+2) + \cdots +(n+k)$? The easiest solution $(n,k)$ is $(2,1)$. For example, $1+2 = 3$. Do any others exist? Roots of $(n+k)^2 + (n+k) = 2n^2 +2n$ give ...
2
votes
1answer
122 views

What is the size of partitions versus subsets?

I know this might be a newbie question, but it's confusing to me. What is a partition, does it only apply to integers? And how does the size of it compare to the size of subsets? Also, suppose we ...
0
votes
1answer
222 views

Total number of solutions of an equation

What is the total number of solutions of an equation of the form $x_1 + x_2 + \cdots + x_r = m$ such that $1 \le x_1 < x_2 < \cdots < x_r < N$ where $N$ is some natural number and $x_1, ...
0
votes
1answer
132 views

Bijective Proof - partitions

what is a bijective proof of #93 in the link provided http://math.mit.edu/~rstan/bij.pdf: The number of partitions of $n$ with $k$ parts equals the number of partitions of $n + \binom{k}{2}$ with ...
4
votes
2answers
183 views

Number of ways of partitioning $a+b$ objects into $k $ partitions such that every partition has at least one object

Given 'a' identical objects of one kind and 'b' identical objects of other kind. Also, given 'k' indistinguishable buckets. In how many ways can one put the '(a+b)' objects into the 'k' buckets such ...
1
vote
2answers
145 views

Unique sum of $k$ triangular numbers into $k$ triangular numbers?

First things first. I've made this a seperate thread off my previous topic so that these topics don't conflict if I'd posted this to my previous question. I believe any $k$ triangular numbers will ...
1
vote
2answers
78 views

Partitions of sums of $k$ random odd/even $r$th powers from array of consecutive $r$th powers

Like my previous question, I'll pose this one too with an array. $1^r, 3^r, 5^r, 7^r, 9^r$ (all odd $r$th powers) That's array 1. And array 2; $2^r, 4^r, 6^r, 8^r, 10^r$ (all even $r$th powers) ...
5
votes
3answers
2k views

Partitioning a natural number $n$ in order to get the maximum product sequence of its addends

Sorry if i ask this question. probably it's already answered somewhere else but i didn't find it. Suppose to have a natural number $n \ge 0$. Given natural numbers $\alpha_1,\ldots,\alpha_k$ such ...
1
vote
2answers
76 views

Subsets of $\{1, 2,\ldots, n\}$ which add up to $n$

Problem: Given a number $n,$ we want to find out the subsets of $\{1,2,\ldots,n\}$ that add up to the given number $n.$ Example: If $n=6,$ then the output is: $\{1,5\}, \{2,4\}, \{1,2,3\}.$ ...
0
votes
1answer
457 views

Finding a partition $P'$ over an interval for which $U(f, P')-L(f,P') \lt 2 $

If $f:x \to 2x+1$ over the interval $[1,3]$ and $\mathcal P$ be a partition consisting of the points $\{1,\frac32,2,3\} $, how do I find a partition $\mathcal P'$ of $[1,3]$ for which ...
1
vote
1answer
379 views

How does $P(n)$ (Partition Function P) work?

I am trying to do Project Euler #78, which is about the different ways of splitting up coins into piles. I realized that this is just the number of integer partitions of the number of coins, ...
0
votes
1answer
107 views

Given a positive integer, find the maximum distinct positive integers that can form its sum

For example, 6 has a max of 3 distinct integers excluding 0 that can form its sum (1,2,3). I can't think of any property that that I could exploit, even the recursions do not have good base cases.
1
vote
0answers
140 views

Given $x = \sum_{i \in k} a_i$ from $\{ a_1, \ldots, a_n \}$, partition $x$ as $\sum_{j \in k} a_j$

Let me put this into an example. We have an array of the first $r$ (example $r=7$) natural numbers; $1, 2, 3, 4, 5, 6, 7$ and given $k=3$, so you get to select any three integers from the pool ...
3
votes
2answers
397 views

For which $k$ are there most partitions of $n$ into $k$ parts?

Let $P(n,k)$ denote the number of partitions of $n$ into $k$ parts. I would like to know for given $n$, which $k$ does maximize $P(n,k)$? Additionally, information on the maximum of $P(n,k)$, for ...
1
vote
1answer
688 views

Notation of partition

I look for an elegant way to notate a partition $\mathcal{Q}$ based on another partition $\mathcal{P}$. Two elements who are already in the same partition in $\mathcal{P}$ also belong to the same ...
5
votes
3answers
2k views

Number of cycles of all even permutations of $[n]$ and number of cycles of all odd permutations differ by $(-1)^n (n-2)!$

I'm trying to solve task 44 of the first chapter of Stanleys Enumerative Combinatorics (found here). Show that the total number of cycles of all even permutations of $[n]$ and the total number ...
1
vote
2answers
184 views

Partition of a Nonempty Set $X$

Let $X$ be a nonempty set, and $\{A_\alpha : \alpha\in I\}$ be a partition of $X$. If $B\subseteq X$ such that $A_\alpha\cap B\neq\emptyset$ for every $\alpha\in I$, is $\{A_\alpha\cap B : \alpha\in ...
2
votes
1answer
137 views

Equality of times blocks of size $k$ appear in a partition with the number of distinct parts appearing $\geq k$ times?

I've been reading up on combinatorics in my spare time recently. Suppose $\lambda$ is a partition of $n$, and $f_k(\lambda)$ the number of times that $k$ appears as a part of $\lambda$. Also, let ...
1
vote
2answers
117 views

Verifying That A Collection Is A Partition of $\mathbb R^3$

Can someone possibly explain this to me, I'm having difficulties visualizing it: For each $r\in\mathbb{R}$, let $A_r=\{(x, y, z)\in\mathbb{R}^3 : x+y+z=r\}$. How can I tell if this is a partition of ...
1
vote
1answer
338 views

How do I approach this combinatorics problem about composition?

The question is from Bogart's A composition of the integer k into n parts is a list of n positive integers that add to k. How many compositions are there of an integer k into n parts. To ...
1
vote
3answers
558 views

Proof of the duality of the dominance order on partitions

Could anyone provide me with a nice proof that the dominance order $\leq$ on partitions of an integer $n$ satisfies the following: if $\lambda, \tau$ are 2 partitions of $n$, then $\lambda \leq \tau ...
5
votes
1answer
169 views

Combinatorial interpretation of $ n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j}$?

By logarithmic differentiation, one can deduce that \[ n P_n = \sum_{j=1}^n \, \sigma(j) P_{n-j} \] where $P_n$ is the $n$-th partition number, and $\sigma(j)$ the sum of the divisors of $j$. I see ...
5
votes
1answer
323 views

Using Durfee squares to prove partition identities?

I was surprised to learn of Durfee squares, which can be visually explained as the largest square contained within a partition's Ferrers diagram. Moreover, partition identities have always amused me ...
10
votes
1answer
2k views

For what coinage systems does a greedy algorithm not work in providing change?

For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins. However, for a coinage system with 12 cent coins, a greedy ...
5
votes
2answers
513 views

Why does $S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$?

I've been trying to get back into some combinatorics, and in my reading, I find that $$ S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1} $$ where the sum is taken over all compositions ...
1
vote
1answer
602 views

Partition function without repetitions of parts and largest part $k$

Um, well, I think the title pretty much says it all. Nevertheless, allow me to explain. I am aware of a certain partition function $Q(n, k)$ that is supposed to remove duplication of parts and $k$ ...
4
votes
1answer
558 views

Partitions of $\{1,\dots,n\}$ with no consecutive integers in each block is counted by $B(n-1)$?

I'm trying to understand why $B(n-1)$ also counts the number of partitions of $[n]$ where not two consecutive integers appear in the same block. Now the bell number $B(n-1)$ counts the number of ...
3
votes
1answer
749 views

Generating Function for Even Number of Odd Parts

How I would write the generating function for a partition of a positive integer n with an even number of odd parts? Any hints or suggestions will be greatly appreciated.