# Tagged Questions

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.

11k views

### Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
2k 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 ...
5k views

### Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
1k views

### Identity involving partitions of even and odd parts.

First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions ...
116 views

### Exploring $\sum_{n=0}^\infty \frac{n^p}{n!} = B_pe$, particularly $p = 2$.

I was exploring the fact that $$\sum_{n=0}^\infty \frac{n^p}{n!} = B_pe,$$ where $B_n$ is the $n$th Bell number. I found this result by exploring the series on wolframalpha and looking up the ...
456 views

### Multiplication partitioning into k distinct elements

Let's say I have a list with the prime factors of a number $n$ and their corresponding exponents. Is there a formula to calculate how many multiplications with $k$ distinct factors of $n$ are possible?...
5k views

### The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts

This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
1k views

### Partitions of $n$ into distinct odd and even parts proof

Let $p_\text{odd}(n)$ denote the number of partitions of $n$ into an odd number of parts, and let $p_\text{even}(n)$ denote the number of partitions of $n$ into an even number of parts. How do I ...
1k views

### Counting integer partitions of n into exactly k distinct parts size at most M

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$? The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
2k views

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

Suppose we have a natural number $n \ge 0$. Given natural numbers $\alpha_1,\ldots,\alpha_k$ such that $k\le n$ $\sum_i \alpha_i = n$ what is the maximum value that $\Pi_i \alpha_i$ can take? I'...
1k 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 ...
540 views

### How solutions of distinct non-negative solutions are there to $k_1+\cdots+k_n=k$?

How many distinct $n$-tuples with distinct non-negative integer elements are there that add to $k$. For example there are $6$ triples that add to $4$. Namely $(0, 1, 3)$ and its $6$ permutations. Is ...
2k views

### Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
403 views

### How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
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 ...
165 views

### A formal name for “smallest” and “largest” 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\}\}$.
1k views

### Same number of partitions of a certain type?

Is there a quick explanation of why the number of partitions of $n$ such that no parts are divisible by $d$ is the same as the number of partitions of $n$ where no part is repeated $d$ or more times, ...
629 views

### Feeding real or even complex numbers to the integer partition function $p(n)$?

Like most people, when I first encountered $n!$ in grade school, I graphed it, then connected the dots with a smooth curve and reasoned that there must be some meaning to $\left(\frac43\right)!$ — and,...
587 views

108 views

### Partition problem for consecutive $k$th powers with equal sums (another family)

This is the partition problem as applied to a special set, namely the first $n$ $k$th powers. Assume the notation, $$[a_1,a_2,\dots,a_n]^k = a_1^k+a_2^k+\dots+a_n^k$$ I. Family 1 The following ...
441 views

### Jordan Measures, Open sets, Closed sets and Semi-closed sets

I cannot understand: $$\bar{\mu} ( \{Q \cap (0,1) \} ) = 1$$ and (cannot understand this one particularly) $$\underline{\mu} ( \{Q \cap (0,1) \} ) = 0$$ where $Q$ is rational numbers, why? I ...
157 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 ...
87 views

### Sums of Consecutive Cubes (Trouble Interpreting Question)

Show that it is possible to divide the set of the first twelve cubes $\left(1^3,2^3,\ldots,12^3\right)$ into two sets of size six with equal sums. Any suggestions on what techniques should be used to ...
638 views

358 views

### Generating functions of partition numbers

I don't understand at all why: $$\sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1}$$ Where $p_n$ is the number of partitions of $n$. Specifically ...
186 views

### Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
89 views

### Partitioning the edges of $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs

Why is it impossible to partition the edges in $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs for $n \ge 6$? I'm just stuck at the beginning and can't figure out how to go about this problem. ...
56 views

### Construct matrix of ones and zeros based on sequences

We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers. Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and zeros("0"...
233 views

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, ... 1answer 897 views ### Ellipse 3-partition: same area and perimeter Inspired by the question, "How to partition area of an ellipse into odd number of regions?," I ask for a partition an ellipse into three convex pieces, each of which has the same area and the same ... 0answers 806 views ### Is this determinant identity known? Let$A$be an$n \times n$matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ... 1answer 267 views ### Integer parts of multiples of irrationals Let$\alpha>0$and define $$S(\alpha)=\big\{\lfloor n \alpha \rfloor: n\in\Bbb Z^+ \big\}.$$ Here$\lfloor x\rfloor$is the integer part of$x$and$\mathbb Z^+$the set of positive integers. ... 2answers 2k views ### How many combinations of$3$natural numbers are there that add up to$30$? How many combinations of$3$natural numbers are there that add up to$30$? The answer is$75$but I need the approach. Although I know that we can use$_{(n-1)}C_{(r-1)}$i.e.$_{29}C_2 = 406$but ... 6answers 951 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 ... 4answers 5k views ### Algorithm for generating integer partitions I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ... 1answer 378 views ### Minimum square partitions for 4x3 and 5x4 rectangles Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first$w$such that a rectangle,$R_{w\times w−1}$is minimally-square-partitioned by less than$w$squares.. Yes, ... 4answers 3k views ### How many solutions does the equation$x_1 + x_2 + x_3 = 11$have, where$x_1, x_2, x_3$are nonnegative integers? Help me understand problems of this type a bit more intuitively. The solution$C(3+11−1,11)$seems simple enough, but I got stuck thinking about how many integers you are choosing from within$x_1$, ... 2answers 762 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)$... 1answer 730 views ### Recurrence for the partition numbers I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the$P_n$— number of partitions of size$n$(or coefficients in ... 1answer 136 views ### Characters of the symmetric group corresponding to partitions into two parts Let$n\in\mathbb N$be a natural number and$\lambda=(a,b)\vdash n$a partition of$n$into two parts, i.e.$a\ge b$and$a+b=n$. In this special case, is there a simple description of the character$\...
There are exactly 18 partitions of the integer 13 into 4 parts, as on the left of the table, and also 18 partitions into 5 parts, as on the right of the table: \begin{array}{c|c} 10+1+1+1 & 9+1+...
### # of partitions of $n$ into at most $r$ positive integers $=$ # of partitions of $n + r$ into exactly $r$ positive integers?
How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?