Hot answers tagged partitions
20
We can interpret this combinatorially as the number of ways to form a committee (of any size) with one chairman out of a group of $n$ people.
From $n$ people we first pick a committee of size $i$, then choose one the $i$ committee members to be the chairman. There are ${n \choose i}$ options for the members of the committee, after which there are $i$ ...
8
Hint: consider the the set of all subsets of $\{1,2,\dots,n\}$ (of which there are $2^n$) and try to find the total sum of the sizes of the subsets in two different ways. For example, the possible subsets of $\{1,2\}$ are $\{\},\{1\},\{2\},\{1,2\}$. Then adding up the sizes of each subset gives $0+1+1+2 = 4$.
More explicitly, if we add up the sizes of all ...
8
There are $89$ ways (and $89$ is the $11$th Fibonacci number).
You're looking for "restricted compositions" of $12$ (the restriction being that each part is at least $2$).
In Sage (doc):
sage: Compositions(12, min_part = 2).list()
[[12], [10, 2], [9, 3], [8, 4], [8, 2, 2], [7, 5], [7, 3, 2], [7, 2, 3], [6, 6], [6, 4, 2], [6, 3, 3], [6, 2, 4], [6, 2, 2, ...
7
The answer is yes, under the axiom of choice, such a partition is possible. There are several ways of seeing this. For example, choice gives us that any set is in bijection with an infinite ordinal. But, for any infinite ordinal $\alpha$, there is a bijection between $\alpha$ and $\alpha\times \{1,\dots,n\}$. The bijection is in fact canonical, in the sense ...
6
Perhaps this will help. We have $11$ identical candies, that we wish to distribute between $3$ children $C_1$. $C_2$, and $C_3$. (Possibly one or more of the children will get no candies.) For every solution of $x_1+x_2+x_3=11$, we have a way of distributing the candies, $x_1$ to $C_1$, $x_2$ to $C_2$, and $X_3$ to $C_3$. conversely, every distribution of ...
6
The idea of a partition is that you take a whole (the set $X$) and you divide it to parts.
Now if I cut off an apple into slices (and one core) I have several pairwise disjoint parts of the apple, but if I reassemble the parts I get a whole apple again.
Similarly we require this from a partition of a set. We want that the union of all the parts give us the ...
5
Denote by $$\rho=\{(1,1),(1,4),(2,2),(3,3),(4,1),(4,4)\}$$ your equivalence,if $(x,y)\in\rho$ then we write $x\rho y$ you have $1\rho1\rho4\rho4\rho1$ so first class of equivalence is $\{1,4\}$ then $2\rho2$ the second class is $\{2\}$ and $3\rho3$ the third class is $\{3\}$
definitely your equivalence defines a partition $$\{\{1,4\},\{2\},\{3\}\}$$ of set ...
5
The argument you give generalizes to show that
$$p(n) \ge (k+1)^{ \lfloor \sqrt{ n/k } \rfloor }$$
for any positive integer $k$. We repeat the same argument, but instead of subsets of $\{ 1, 2, ... \lfloor \sqrt{n} \rfloor \}$ we allow multisubsets of $\{ 1, 2, ... \lfloor \sqrt{n/k} \rfloor \}$, where each element occurs with multiplicity $0$ through $k$.
...
5
Here is how you can compute the coefficient you are after without using symbolic algebra software, just any programming language where you can handle an array of $101$ integers; I'll assume for convenience that the array is called $c$ and is indexed as $c[i]$ where $i$ ranges from $0$ to $100$, because then $c[i]$ records the coefficient of $x^i$ in a power ...
5
Any partition of $n$ into $4$ parts must have each part no bigger than $n-1$. But
$$a+b+c+d=3n \ \ \ \Leftrightarrow \ \ \ (n-a)+(n-b)+(n-c)+(n-d)=n,$$
so the number of partitions of $3n$ into $4$ parts, each between $1$ and $n-1$, equals the number of partitions of $n$ into $4$ parts, each between $1$ and $n-1$.
5
Recall exponential notation for partitions: $a^b$ signifies $b$ occurrences of $a$ in the partition. (Exponential notation can be useful for seeing the generating functions.) In exponential notation, every partition satisfying your constraints are of the form $m^k (m+1)^l$. In your $n = 4$ example, the partitions are $4^1 5^0$, $2^2 3^0$, $1^2 2^1$, and $1^4 ...
4
Not sure how simple it is, but Percy MacMahon devised a general way to do this as an application of generating functions he worked out for plane partitions. See Combinatory Analysis v2, $\S$X, ch11, paragraphs 497-498. These are in the second pages 245-246 of the 1960 Chelsea reprint.
The answer for a general $n$ part partition is the determinant of an $n ...
4
Well if you have the prime factorization for a number (let's use your example of 24), then any combination of its prime factors must be a factor.
$$24 = 3\times 2^3$$
So any combination of {3, 2, 2, 2} is a factor. The way you go about taking all subsets of a set in an efficient manner is more of a CS problem.
But just to drive home the point:
{{3}=2, {3, ...
4
Here's a large class of valid shapes. It's easiest to explain with a picture of a representative example:
$\hskip{2.5in}$
Formally, let $\gamma:[a,b]\to\mathbb R^2$ be a curve (the blue one). Let $T:[0,1]\to(\mathbb R^2\to\mathbb R^2)$ be a constant-speed rotation or translation of the plane. That is, either there is a fixed vector $x$ such that ...
4
The answer to 1) is, not necessarily. A 30-60-90 triangle can be divided into three congruent 30-60-90 triangles. If you can't see how to do this, see Figure 1 in this paper. Theorem 2 in that paper proves that this and the equilateral are the only triangles that can be divided into three congruent triangular shapes.
EDIT: If you don't insist on convexity, ...
4
$f(-2)=f(-1)=f(0)=0$ so if the domain is the integers it does not have an inverse. In fact, $f(n)=f(-2-n)$
However, this function is monotonic increasing on the non-negative integers, so it does have an inverse if the domain is the non-negative integers.
Suppose
$$
m=\frac18\left(1-(-1)^n+2n(2+n)\right)
$$
If $n$ is even, then $(n+1)^2=4m+1$
If $n$ is ...
4
Let be
$$a_0=1,a_{k}=\frac{z^{k}}{(1-z)(1-z^2)\cdots(1-x^{k})},k>0$$
and
$S_{k}=1+\sum_{i=1}^{k}a_i$. We want to show that
$$
S_{k}=\frac{1}{(1-z)(1-z^2)\cdots(1-z^{k})}.$$
$S_0=a_0=1$; and assuming it's true for $k=n$, we have
$$
\begin{eqnarray}
S_{n+1}&=&S_{n}+a_{n+1} \\ ...
4
There is a concept called amorphous sets, which becomes interesting when the axiom of choice fails. These sets are such that you cannot partition them into two distinct infinite sets.
One property of amorphous sets is that if we take an infinite partition of an amorphous set, then all but finitely many parts have the same size (and all these sizes are ...
4
Hint: It is the number of positive solutions of $x_1+x_2+ x_3+x_4 +x_5=100$.
For in how many ways can I distribute candies among $4$ kids, each kid getting one candy at least, and with $\lt 100$ candies distributed?
Imagine I have $100$ candies. I call myself the fifth kid, and if $k$ candies are distributed among the real four, I get the remaining ...
4
I do not think that there is terminology, which would be universally agreed.
However, Google search suggests that some people us the following names:
trivial partition for the partition $\{A\}$ and discrete partition or singleton partition for the partition the partition $\{\{a\};a\in A\}$.
Interestingly enough ProofWiki Article suggests that trivial ...
4
Suppose that $A$ is a non-empty set and $P_1,P_2$ are two partitions of $A$. We say that $P_1$ refines $P_2$ if for every $B\in P_1$ there is $C\in P_2$ such that $B\subseteq C$. This means that $P_1$ was a result of partitioning each part of $P_2$.
We also say that $P_1$ is finer than $P_2$; that $P_1$ is a refinement of $P_2$; or that $P_2$ is coarser ...
4
Indeed, you could use the Vitali set for such a partition but that would be overkill. Let $P_1=[0,1]\cap \mathbb Q$ and $P_2=[0,1] \setminus P_1$ then $P_1 \sqcup P_2=[0,1]$ but neither $P_1$ nor $P_2$ contain an open interval because any open interval contains both rational and irrational elements.
3
A few hints to get you started.
There is actually a direct generating function for $p_e(n) - p_o(n)$. It is given by
$$\prod_{n\ge1}\frac{1}{1 + x^n} = \sum_{n\ge0}(p_e(n)-p_o(n))x^n$$
Can you see why? (If you are familiar with a proof of Euler's pentagonal formula, then this should be somewhat familiar)
Similarly, there is a generating function for the ...
3
We have $\frac{1}{1-x^k}=1+x^k+x^{2k}+x^{3k}+\cdots$. These are combined formally in a process known as generating functions.
More details, as requested. We multiply out $(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)(1+x^3+x^6+x^9+\cdots)(1+x^4+x^8+\cdots)\cdots$, and gather the powers of $x$, as if they were polynomials. For example, $x^3$ has a ...
3
The paper Über die Charaktere der symmetrischen Gruppe by Frobenius is in the Sitzungsberichte der königlich preußischen Akademie der Wissenschaften zu Berlin of $1900$, available at archive.org in various formats. It begins on p. $516$; the formula you cite seems to correspond to the last formula of the paper on p. $534$. The notation ...
3
There's several ways to answer this problem computationally, and which is best depends on (a) personal preference, and (b) how, if at all, you're planning on re-using the code.
A brute force method is to have 8 nested for loops and, inside these for loops, have an if statement for the three conditions ($\sum_i a_i b_i \geq 8$, $\sum_i a_i=10$, and $\sum_i ...
3
First of all, for what you write to make sense, you're not picking two partitions and defining a relation between those particular two partitions. You're defining a single relation on the set of all partitions.
Second, I think you're overcomplicating things by considering a partition to be an indexed family of subsets of $U$. Indeed, if you consider the ...
3
Yes, your own observation nicely works. Start with ${\cal B}$.
First use the trick also mentioned in wikipedia (for partitions in odd parts) to show that
$\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\dots} =$ $ (1+x)(1+x^2)(1+x^3) \dots$; this is the product of the fractions of odd powers $\prod(\frac{1}{1-x^{4j-3}})(\frac{1}{1-x^{4j-1}})$.
Now you have to ...
3
George Andrews has contributed greatly to the study of integer partitions. (The link with his name will take you to his webpage listing publications, some of which are accessible as pdf documents.) Also see, e.g., his classic text The Theory of Partitions and the more recent Integer Partitions.
You can pretty much "jump right in" with the following, though ...
3
This is Perl:
sub partition {
print "@_\n";
my ($largest, @rest) = @_;
my $min = $rest[0] || 1;
my $max = int($largest/2);
for my $n ($min .. $max) {
partition($largest-$n, $n, @rest);
}
}
The code should be easy to translate into other languages, once you know that @_ is Perl's notation for the list of arguments to a function. To ...
Only top voted, non community-wiki answers of a minimum length are eligible
