New answers tagged

0

As the OP said in his comment the answer is the following list of partitions of $S = \{1,2,3\}$: $\left\{ \{1,2,3\} \right\}$ (one set, just $S$ itself ) $\left\{ \{1,2\}, \{3\} \right\}$ (two sets, one of two elements , one singleton) $\left\{ \{1,3\}, \{2\} \right\}$ $\left\{ \{2,3\}, \{1\} \right\}$ $\left\{ \{1\}, \{2\}, \{3\} \right\}$ (all ...


1

Let $P(n,k)$ be the number of partitions of $n$ into exactly $k$ parts. This function satisfies the recurrence $$P(n,k)=P(n-1,k-1)+P(n-k,k)\;:$$ the first term on the right is the number of $k$-partitions of $n$ that have at least one part of size $1$, and the second is the number that have no parts of size $1$. (This is most easily seen by considering ...


0

Yes. The same idea can be applied: Choose $i$ of $n$ elements and partition the remaining $n-i$ elements into $k-1$ subsets, yielding $$ \binom niS(n-i,k-1)\;. $$


2

You can do it inductively in the "naive" way: Set $A_1=\{1,12\}$, $A_2=\{2,13^2-2\}$,$\ldots$, $A_{11}=\{11,13^{11}-11\}$, $A_{12}=\{13,13^{13}-13\}$, $A_{13}=\{14,13^{14}-13\}$,... You have, however, to show that this sequence satisfies the properties you want. I think one elementary way to do it is the following: We want to define $A_i$ inductively with ...


4

Note that any $k_j = 1$ is wasted: better to combine it with some other $k_i$, since $1 \cdot k_i < k_i + 1$. Any value $4$ or higher, we might as well split off a $2$: $x < 2 (x-2)$ if $x \ge 4$. So we're left with $2$'s and $3$'s. (Actually a $4$ is interchangeable with two $2$'s, but let's think in terms of $2$'s and $3$'s) $2^3 < 3^2$, so ...


0

There are several sequences/functions/implicit ideas in your question, and I'll try to clear them up as best as I can. There is an enumeration of the dyadic fractions $d_c$ where $d_1=0,d_2=1,d_3=\frac12$ that continues $\frac14,\frac34,\frac18,\frac38,\frac58,\frac78,\ldots$. Now, for fixed $n\ge0$, we can look at $d_1$ through $d_{2^n+1}$ and assign them ...


1

A partition, in this context, is taken to mean a finite subset $P$ of a real interval $[a,b]$ that contains the endpoints $a,b$ of the interval. Given a real interval $[a,b]$ and a positive integer $n\in\mathbb{N}$, we can define a function $t\colon\{0,1,2,\ldots,n\}\to[a,b]$, and we can insist that the function is increasing so that ...


2

One can show that the number $p_k(n)$ of partitions of $n$ into exactly $k$ parts is equal to the number of partitions of $n$ in which the largest part has size $k$. So you are looking for a formula for $p_9(k)$. Rubinstein has given an explicit formula for $p_k(n)$ in terms of Bernoulli polynomials, see here. A. Sills has given Rademacher-type formulas for ...


1

In your example, $[11,22]$ is listed twice; I'm guessing one of those was supposed to be $[1122].$ The question is not stated very clearly. Here's how I interpret it: Let $S=\{(m,n)\in\mathbb Z\times\mathbb Z:m,n\ge0\}.$ Given $(m,n)\in S,$ determine $f(m,n),$ the number of ways in which the vector $(m,n)$ can be expressed as an unordered sum of elements ...


0

If you want to find out whether a relation $R$ on a set $A$ is an equivalence relation then it is a handsome strategy to look for a function $f:A\to Y$ such that $aRb\iff f(a)=f(b)$. If you can find one then you are indeed dealing with an equivalence relation. Note that e.g. reflexivity of $R$ follows directly from the evident fact that $f(a)=f(a)$ for ...


1

Here's another example: Let $a \sim b$ if $a$ and $b$ have the same number of prime factors (up to multiplicity). We can put $1$ in with the prime numbers to meet your criterion of all classes being infinite. Then the classes are: $$\{1,2,3,5,7,11,\ldots\}\\ \{4,6,9,10,14,\ldots\}\\ \{8,12,18,20,\ldots\}\\ etc.$$


4

Little less constructive... Take your favorite bijection $\mathbb{N} \stackrel{f}{\to} \mathbb{N} \times \mathbb{N}$, let $\pi_2$ be the projection in the second coordinate, and consider $h=\pi_2 \circ f$. Now, define $x \sim y \iff h(x)=h(y).$


3

Yes. First note that $\lvert\mathbb N\rvert=\lvert\mathbb N\rvert^2$ so it would be strange if there weren't. For instance let $\sim$ be the equivalence relation defined by $p^n\sim p^k$ for all $p$ prime and $n,k\ge 1$, and let all numbers which aren't of the form $p^n$ be equivalent. So $$1\sim 6\sim 10\sim 12\sim 14\sim 15\sim\cdots$$ $$2\sim 4\sim ...


4

An example: Let $a\equiv b$ if the highest power of $2$ that divides $a$ is the same as the highest power of $2$ that divides $b$. So $\{1,3,5,7,9,\dots\}$ is one equivalence class. $\{2,6,10,14,18,\dots\}$ is another. $\{4,12,20,28,36,\dots\}$ is another. And so on. There are many other examples.


2

For every $j\ge 1$, let $\Delta_j$ consist of all natural numbers of the form $2^{j-1} m$, where $m$ is odd. Remarks: $1.$ This can be used to produce a simple bijection between $\mathbb{N}$ and $\mathbb{N}\times \mathbb{N}$. $2.$ You can get an interesting example of a different character by using the Cantor Pairing Function. Note that the linked article ...


1

The formula is $\binom{S-1}{N-1}$. This number is a part of what is known as the composition of a number (what is the sum of these numbers over N). If you want more information you can see the topic more in-depth here.


0

The problems seems to be similar to representing a number N as sum of k positive integers which can be solved with star and bar theorems of combinatorics For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements. ...


1

For the basic generating functions in term of $(1 - x^k) ^ {-1}$, we can write them out as a infinite sum. $(1 - x) ^ {-1}$ = $1 + x + x^2 + x^3 + ....$ $(1 - x^2) ^ {-1}$ = $1 + x^2 + x^4 + x^6....$ $(1 - x^3) ^ {-1}$ = $1 + x^3 + x^6 + x^9....$ and so on. So $\prod(1 - x^k) ^ {-1}$ is just an infinite product of ($1 + x + x^2 + x^3 + ....$)( $1 + x^2 ...


0

Here is a slightly different way to calculate the number of compositions of $40$ generated from $2,5$ and $10$. Since a selection of $2,5$ or $10$ can be represented as \begin{align*} x^2+x^5+x^{10} \end{align*} we start with the ordinary generating function \begin{align*} ...


0

The desired number is $$\frac{(2N)!}{N!\cdot2^N}$$ To get this, consider that there are $N!$ arrangements for every unordered partition.


0

Why not repeatedly choose the 2 components for each partition in order, to get $$ \binom{2N}{2} \times \binom{2N-2}{2} \times \ldots \times \binom{4}{2} \binom{2}{2} = \prod_{k=1}^N \binom{2k}{2}, $$ which you can simplify since $\binom{n}{2} = n(n-1)/2$ to get $$ \prod_{k=1}^N \binom{2k}{2} = \prod_{k=1}^N \frac{2k(2k-1)}{2} = \frac{(2N)!}{2^N} $$ UPDATE ...


0

Your $k = \frac{n}{2}, k = \frac{n+1}{2}$ possibilities are in fact a general solution because those are the only possibilities as we will see. In fact they are even more restricted. We know that 1 + 2 +.... n = \frac{n(n+1)}{2}$ As this sum is also $mk$, and $GCD (n, n+1) = 1$, $m$ has to divide $n$ or $m$ has to divide $n+1$ But it's given that $m ...


3

There is a famous generating function for this: I will provide the generating function, then talk a little bit about why it is correct. The generating function is $$ P(q) = \prod_{k=1}^\infty (1 - q^k)^{-1} = 1 + q +2q^2 + 3q^3 + 5q^4 + 7q^5 + 11q^6 + \cdots. $$ Why is it correct? Well, write each individual term in the product out: The first few are $$ ...


1

The symbol $\lambda / \mu$ is the standard notation for a skew shape. The shape of a partition can be thought of as a geometrical arrangement of boxes (I use o's here). For example, $\lambda = (5,3,2,1)$ is o o o o o o o o o o o Now if $\lambda$ and $\mu$ are 2 partitions such that $\mu_i \le \lambda_i$ for all $i$, then $\lambda/\mu$ is a skew shape, ...


1

Hint: You can produce the list for $8$ by appending $2$ to each entry in the list for $6$ and adding $1$ to the final number in each entry in the list for $7$.


4

(These are actually compositions, not partitions.) You get one composition of $n$ by adding $1$ to the last element of each composition of $n-1$; you also get one by appending a last part $2$ to each composition of $n-2$. The resulting sets of compositions of $n$ don’t overlap: each one in the first set has a last element that is at least $3$, while those ...


0

Notations: $F_0=0, \space F_1=1, \space F_{n+1}=F_{n}+F_{n-1}$. $p(n|"condition")=|\begin{Bmatrix} partitions \space of \space n \space verifying \space "condition" \end{Bmatrix}|$. At first I think that you second inequality is false because $p(2)=2$ and $F_2=1$, so I will consider that the second inequality is $p(n) \le F_{n+1}$ for $n\geq1$. We can ...


7

(2. Update: Now the condition $e\leq100$ is also taken care of.) Write $$\eqalign{a&=1+x_1\cr b&=2+x_1+x_2\cr c&=3+x_1+x_2+x_3\cr d&=4+x_1+x_2+x_3+x_4\cr e&=5+x_1+x_2+x_3+x_4+x_5\cr}$$ with $x_i\geq0$ $\>(1\leq i\leq5)$. Then we have to find the number of integer solutions ${\bf x}=(x_1,\ldots,x_5)$ satisfying $x_i\geq0$ $(1\leq ...


6

The number of partitions of $n$ into five distinct parts with largest part $k$ is the coefficient of $t^kq^n$ in $$ \frac{t^5q^{15}}{(1-tq)(1-tq^2)(1-tq^3)(1-tq^4)(1-tq^5)}. $$ (For an explanation of this, see below.) With sufficient brute force, one could extract the coefficients of all terms with $k\le100$ and $100<n<145$—this is what ...


2

Here is a very painstaking approach that may help you to see exactly what’s going on. The possible values of $b_1$ are $0,1,2$, and $3$, so far starters we try $$1+x+\frac{x^2}2+\frac{x^3}6$$ to account for $b_1$. Similarly, the possible values of $b_2$ are $1,2,3$, and $4$, so we try $$y+\frac{y^2}2+\frac{y^3}6+\frac{y^4}{24}$$ to account for $b_2$. ...


2

Three boxes have no restrictions with respect to the objects which results in $e^{3x}$. The restriction $b_1<b_2\leq 4$ of the other objects together with the objects of the three boxes is encoded as \begin{align*} ...


2

Partitions of unity arise naturally in many applications related to affine spaces and affine transformations. In fact, barycentric coordinates are partitions of unity. So, there are lots of applications in geometry. In other fields, also, there is often the idea of a "weighted average" where the weights necessarily sum to 1. This is common in ...



Top 50 recent answers are included