Tag Info

Hot answers tagged

10

Hint: Try to understand why $$P(x)=\frac{1}{\prod_{n=1}^{\infty}\left(1-x^n\right)},$$ and what are the corresponding expressions for $Q(x)$ and $R(x)$. Spoiler:


3

Your picture shows $A_n$ as a subset of $\Bbb Z$, which is not true for any $n$: the only integer in $A_n$ is the integer $n$ itself. The rest of $A_n$ consists of the rational numbers between $n$ and $n+1$. Here’s a better picture: --)[-------)[-------)[-------)[-------)[-------)[-------)[-------)[----- -2 -1 0 1 2 ...


3

For even $n$, the number of $3$ in each partition is even. So, let $2k$ be the largest number of $3$ in the partition of even $n$, i.e. $$3\cdot 2k\le n\lt 3(2k+2)\Rightarrow k\le \frac{n}{6}\lt k+1\Rightarrow k=\left\lfloor\frac n6\right\rfloor.$$ Hence, the number of partitions of $\color{red}{\text{even}\ n}$ is ...


3

Hint: Create an explicit bijection between the two sets of partitions. A partition that satisfies both conditions will map to itself. A partition that satisfies only one of them can map to one that satisfies the other.


2

Note that $u_n$ is the number of ordered pairs $\langle k,\ell\rangle$ of non-negative integers such that $k+\ell=n$ and $k\le\ell$. It’s not hard to show that $$u_n=\left\lfloor\frac{n}2\right\rfloor+1$$ for all $n\in\Bbb N$. Thus, $$\begin{align*} U(x)&=\sum_{n\ge 0}\left(\left\lfloor\frac{n}2\right\rfloor+1\right)x^n\\ &=\sum_{n\ge ...


2

Hint: First show that (think about how the partitions of $n$ are related to those of $n-2$) $$u_{n} = u_{n-2}+1$$ By multiplying the recurence relation above by $x^{n}$ and summing over $n=2,3,\ldots$ we get $$U(x)-1-x = x^2 U(x) + \frac{x^2}{1-x}$$ Showing that $\frac{1}{U(x)}$ is a polynomial is now just simple algebra.


2

Certainly $|m|=|m|$. If $|m|=|n|$ then $|n|=|m|$ by the reflexive property of $=$. Finally, if $|m|=|n|$ and $|n|=|p|$ then we have $|m|=|p|$ because $=$ is transitive. Since $|-n|=|n|$ we have $-n\sim n$. If $m\neq n$ and $m\neq -n$, then $|m|\neq |n|$ so $m\not\sim n$ (this last observation is not a proof, it is only a claim). This is in line with what ...


2

The expression $\{x,y\}\subset A$ has its usual meaning here: $\{x,y\}$ is a subset of $A$, so $x,y\in A$. This makes perfectly good sense: $A$ is an element of a partition of $X$, so $A\subseteq X$, and therefore $x$ and $y$ are elements of $X$.


2

In the comment section, you suggested that it does not exactly correspond to $n$-digit ternary numbers. I think it does, but maybe I misinterpreted your question. Here is what I think, then we can discuss it: Write ternary digits $d_1,d_2,...,d_n$. Then form the three sets $S_1,S_2,S_3$ as follows: $$ i\in\begin{cases} S_1&\text{ if }d_i=0\\ ...


2

This is the bars and stars problem. Your problem is equivalent to this one: How many ways are there to rearrange $N$ stars and $K-1$ bars? Answer: $\binom {N+K-1}{K-1}$ Think in the stars as balls that you have to put in a row of boxes, and think in the bars as the walls between boxes.


2

The number of partitions of $n$ into parts in the set $\{2,3\}$ is the coefficient of $x^n$ in $$\left(1+x^2+x^4+x^6+\ldots\right)\left(1+x^3+x^6+x^9+\ldots\right)=\frac1{(1-x^2)(1-x^3)}\;.$$ For $n=10$, for instance, we can ignore powers of $x$ higher than $10$, so we need only consider $$(1+x^2+x^4+x^6+x^8+x^{10})(1+x^3+x^6+x^9)\;,$$ and by inspection ...


2

I suppose that you know that, given an equivalence relation on a set $S$ , the set of its equivalence classes is a partition of $S$. In your case the equivalence relation, defined for $m,n $ integers,is: $n \sim m $ iff $m$ and $n$ have the same units digit (in decimal notation). This is the relation that define the sets of the partition, that are ...


2

This is the same as the number of sequences of nonnegative integers $x_1,\ldots,x_l$ whose sum is $k$, or equivalently the number of sequences of positive integers of this length whose sum is $k+l$. This is the number of ways to choose $l-1$ partitions between $k+l$ elements to divide them into $l$ nonempty groups. The answer is $$\binom{k+l-1}{l-1}$$


2

In plain English: $A_0\cup A_1\cup A_2\cup A_3\cup A_4 =\mathbf Z$: Any integer has a remainder upon division by $5$, and this remainder is an integer between $0$ and $4$, hence any integer lies in one of the $A_i$ No $A_i$ is empty since it contains $i$. Any two $A_i$s are disjoint since the remainder is unique (Euclid's theorem).


1

For small numbers of cells $3,4,5,..$ there may be a possibility of finding explicitly the optimal partition (the Y 120 degrees partition in the case $n=3$, etc). For large numbers of cells in the partitions, analytical results are not known. In order to find candidates for the optimal partitions, some numerical studies were performed: Cox and Fikkema: ...


1

You need to show that $\mathbb{R} \times \mathbb{R} = \cup_{r \in \mathbb{R}} A_r$ and that $A_r \cap A_s = \varnothing$ whenever $r \neq s$. For the first of these, it should be fairly clear that given a pair $(x,y)$, it belongs in some $A_r$ (which one?). For the second part, show that if we assume that $(x,y) \in A_r \cap A_s$ when $r \neq s$ then we ...


1

One can show that a finite group which is generated by elements of order two is the intersection of such stabilizers. Every finite simple non-abelian group falls into that class of groups I think. But I am not sure how relevant this is for the theory of finite groups.


1

I would call the result you're asking about the "fundamental theorem for equivalence relations" (relevant Wikipedia link; also, take a look here), but the result is also tantamount to the "first isomorphism theorem for sets". The intuition for this theorem is extremely simple: If you've defined "related", you can group objects according to whether ...


1

A simple counterexample is $V = \mathbb R^2$, $$ S = \left\{\begin{bmatrix} 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \end{bmatrix} \right\} $$ and $$ U = \left\{\begin{bmatrix} x \\ x \end{bmatrix} \, | \, x\in \mathbb R\right\}. $$


1

Try to describe for any $n \in \mathbb{Z}$ its class of equivalence and this describe the partition of $Z$ in this case is $n, -n$ so the particion is given by this sets.


1

Let $X$ be a set and $\sim$ a relation amongst the elements of $X$. Then $\sim$ is an equivalence relation if $\sim$ is symmetric, reflexive and transitive. Symmetric: $ x \sim y \Rightarrow y \sim x$ Reflexive: $\ x \sim x$ Transitive: $\ x \sim y, y \sim z \Rightarrow x \sim z$. $\\$ In your example we take $\ \mathbb{Z}/\sim$ where $x \sim y \iff ...


1

Hint: It is pretty easy to see that $$ u_n=\left\lfloor\frac n2\right\rfloor+1 $$ This will be a useful series here $$ \begin{align} \frac1{(1-x)^2} &=\frac{\mathrm{d}}{\mathrm{d}x}\frac1{1-x}\\ &=\frac{\mathrm{d}}{\mathrm{d}x}\left(1+x+x^2+x^3+\dots\,\right)\\[6pt] &=1+2x+3x^2+\dots \end{align} $$ Thus, $$ \begin{align} U(x) ...


1

$${1+x\over1-x^2}{1\over1-x^4}{1+x^3\over1-x^6}{1\over1-x^8}\dots={1\over1-x}{1\over1-x^3}{1\over1-x^4}{1\over1-x^5}{1\over1-x^7}\dots$$


1

First you prove its an equivalence relation. Reflexive: for all $ n \in \mathbb{Z}: n \sim n$ because $n-n = 0 = 0\times 10$ Symmetric: for all $m, n \in \mathbb{Z}: m \sim n \to m - n = 10k \to n - m =10(-k) \to n \sim m$. Transitivity: for all $m, n, p \in \mathbb{Z}: m \sim n, n \sim p \to m - n = 10k, n - p = 10l \to m - p = 10(k+l) \to m \sim p$. Thus ...



Only top voted, non community-wiki answers of a minimum length are eligible