Tag Info

Hot answers tagged

5

Alternatively, you can use Cantor's pairing function to get a bijection $\pi:\Bbb N\times\Bbb N\rightarrow N$. Then we can define $A_i=\{\pi(i,k):k\in\Bbb N\}$.


4

A really explicit formula would be $$A_i=\{2^i (2j+1) - 1: j\ge 0\}.$$ So $$A_0=\{2j+0\}=\text{even numbers}$$ $$A_1=\{4j+1\}=\{1,5,9,13,\dots\}$$ $$A_2=\{8j+3\}=\{3,11,19,\dots\}$$ $$A_3=\{16j+7\}=\{7,23,39,\dots\}$$ $$\dots$$


4

Partition the graph into two arbitrary partitions $A$ and $B$ at first. Now, consider the set $S$ of edges between them, i.e. $S = \{(a,b) \in E \ | \ a \in A, \ b \in B\}$. If some vertex $v \in A$ has more than half neighbours in $A$, then clearly shifting $v$ to $B$ increases the size of $S$. Similarly for any such vertex in $B$, shifting to $A$ ...


3

Let $\{p_n\}_{n\in\mathbb N}$ be the prime numbers. Set $$ A_j=\{p_j^k : k=1,2,\ldots,\}, $$ and $A_0=\mathbb N\setminus\bigcup_{j\in\mathbb N}A_j$.


3

The generating function for $p(n)$ is $$p(n)=\prod_{k\ge 1}\frac1{1-x^k}=\prod_{k\ge 1}\sum_{j\ge 0}x^{jk}\;:$$ the coefficient of $x^n$ is the number of ways to write $n$ in the form $$n=j_1\cdot1+j_2\cdot2+j_3\cdot3+\ldots\;.$$ To omit $\ell$ as a summand in the partitions, drop out the factor of $\dfrac1{1-x^\ell}$. Thus, if $p_\ell(n)$ is the desired ...


2

For the sake of diversity, let $A_1=\{1\}\cup2\mathbb N$, $$A_2=3\mathbb N\setminus 6\mathbb N,\qquad A_3=5\mathbb N\setminus (10\mathbb N\cup15\mathbb N),\qquad A_4=7\mathbb N\setminus (14\mathbb N\cup21\mathbb N\cup35\mathbb N),$$ and, more generally, let $A_i$ denote the set of positive integers whose smallest divisor not equal to $1$ is the $i$th prime. ...


2

For every $k\geqslant0$, let $$A_k=\{k+n^2\mid n\geqslant1,2n\geqslant k\}.$$ The partition up to $25$ is as follows: $A_0=\{1,4,9,16,25,\ldots\}$ $A_1=\{2,5,10,17,\ldots\}$ $A_2=\{3,6,11,18,\ldots\}$ $A_3=\{7,12,19,\ldots\}$ $A_4=\{8,13,20,\ldots\}$ $A_5=\{14,21,\ldots\}$ $A_6=\{15,22,\ldots\}$ $A_7=\{23,\ldots\}$ $A_8=\{24,\ldots\}$ Each $i\geqslant1$ ...


2

You don’t need your expressions for $P_e(x)$ and $P_o(x)$; just expand $$\prod_{k\ge 1}\frac1{1+x^k}=\prod_{k\ge 1}(1-x^k+x^{2k}-+\ldots\;,$$ and notice that the individual $x^n=x^{k_1}x^{k_2}\ldots x^{k_m}$ terms of the outer product are positive or negative according as $m$ is even or odd, so the coefficient of $x^k$ in $$\prod_{k\ge 1}\frac1{1+x^k}$$ ...


1

Note: This is really a nice question since it provides a good opportunity to consider similar but different concepts in a non-trivial but manageable way! But first some clarification: The example with $n=9$ in the question above giving a result of $10$ means the number of different compositions of $9$ is $10$. Later on a generating function for ...


1

Assuming you are meaning partitions, the generating function you are looking for is $$ P_{odd,redblue}(z) = \prod_{n=1}^{\infty} \frac{1}{1-2z^{2n+1}}. $$ I don't know yet if the function has a nicer form or what the properties of the function are. How to get there: You should first be familiar with the multiset construction, from Flajolet's book Analytic ...


1

Given $n$, let $f_n$ denote the required number of block arrangements. If we consider the possibilities for the first block for such arrangements, we see that, since the first block can be red or blue and have length one of $3$, $5$, $7$, etc, \begin{eqnarray*} f_n &=& 2(f_{n-3} + f_{n-5} + f_{n-7} + \cdots + f_k) \\ && \\ && ...


1

Before we get to your question, we need to fix your setup: as others have pointed out in the comments, your limits on the $x_k$ incorrectly exclude solutions with $0$s, like $800$ and $710$. In fact you want $0\le x_k\le 8$ for $k=1,2,3,4,5$: $0$ should be allowed in any position, and there’s no need to allow $9$ in any position, since a $9$ would make the ...


1

The generating function for partitions where no odd number appears more than once is $$\prod_{k\ge 1} \frac{1}{1-z^{2k}} \prod_{k\ge 0} (1+z^{2k+1}).$$ The number of partitions containing no element of $A$ is $$\prod_{k\ge 1} \frac{1}{1-z^k} \prod_{k\ge 0} (1-z^{4k+2}).$$ Re-write this as $$\prod_{k\ge 1} \frac{1}{1-z^{2k}} \prod_{k\ge 0} ...


1

There are several valid answers. I like mine. :) $A_n$ is the set of integers whose decimal representation contains exactly $n$ '1' digits.


1

Recall that an equivalence relation is reflexive, symmetric, and transitive. In this case we will only need the first two properties. Reflexivity means that all pairs of the form $(x,x)$, with $x \in A$, belong to $R$. Symmetry means that if the pair $(x,y)$ is in $R$, then $(y,x)$ is also in $R$. Therefore we can decompose $R$ into two sets of pairs: ...


1

You can set up a one-to-one correspondence (aka a bijection) between the partitions of $N$ into odd parts and the partitions of $N$ into distinct parts. I will just illustrate with an example; I leave it to you to formalize it and verify that it works. Here is one way to partition the number $N=863$ into odd parts: partition it into $22$ ones, $49$ threes, ...


1

If the question you wrote is correct, I think the given answer is wrong. Let $X_i=x_i-1$ for $i\not=2$ and $X_2=x_2-3$. Then, $X_i$ are non-negative integers and we have $$\sum_{i=1}^{7}X_i=23-9=14.$$ Hence, the answer is $$\binom{7+14-1}{14}=\binom{20}{6}=38760.$$



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