New answers tagged

0

Consider any arrangement of the numbers $1,2,\ldots,2n$ in a row. There are $(2n)!$ such arrangements. Each such arrangement gives raise to $n$ disjoint sets of 2 elements (simply pick the first two for the first subset, next two for the next etc). The set of $n$ disjoint subsets is counted $n!2^n$ times since we get the same disjoint sets when we permute ...


0

Let us denote the number of ways of writing $n$ as a sum of $k$ distinct positive integers as $Q(n,k)$ and number of $k$ partitions of $n$ as $P(n,k)$. It can be proved that $$Q(n,k) = P\left(n-\frac{1}{2}k(k-1), k\right)$$ - see Barnard and Child, Higher Algebra. For $P(n,k)$ we have the recurrence relation $$P(n,k) = P(n-k,k)+P(n-1,k-1)$$ Using these, we ...


2

As Doug M said what you are doing is obtaining the modulo $9$ of the number, it is also called the Digital root of the number. An excerpt from Wikipedia: The digital root (also repeated digital sum) of a non-negative integer is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the ...


1

Very useful paper, though this only gives a good approximation to the number of partitions of n into exactly k parts each no larger than N due to Ratsaby (App. Analysis and Discrete M. 2008): http://www.doiserbia.nb.rs/img/doi/1452-8630/2008/1452-86300802222R.pdf


0

Hint We know $p_k(n)$( partitions of $n$ into exactly $k$ parts) equals $$x_1+x_2+\cdots +x_k=n\quad ,\quad x_i\in \mathbb{N}$$ let $m=n+\left( \begin{matrix} k \\ 2 \\ \end{matrix} \right)$ and prove the number of distinct partition of $m$ into exactly $k$ distinct parts equals $p_k(n)$ show $$\frac{1}{k!}\left( \begin{matrix} n-1 \\ k-1 \...


0

Yes, you have overcounted. You can conut $S_i$'s in $$\binom{2n}2\binom{2n-2}2\dots\binom22=\frac{(2n)!}{\underbrace{2!2!2!\dots2!}_{\text{n times}}}=\frac{(2n)!}{(2!)^n}$$ But, here the order of $S_i$'s are not relevant, so divide the number of permutations of $S_i$'s, that is $n!$. So, your result should be $$\frac{\binom{2n}2\binom{2n-2}2\dots\binom22}{...


1

Let $a_n$ be the number of ways to partition $\{1,\dots, 2n\}$. Then $a_{n+1}=a_{n}+(2n)(2n-1)a_{n-1}$, because either $2n+2$ and $2n+1$ are in the same set, and we have $a_n$ ways to finish, or they are in different sets and then there are $(2n+2)(2n+1)a_{n-1}$ ways to finish. Now by induction it is easy to see that the answer is $(2n-1)!!=(2n-1)(2n-3)\dots ...


0

I believe your confusion regarding the definition of a partition, P, of a set X may stem from conflating the elements of X with the elements of P. The elements of a partition are non-empty subsets of X. For P to be a partition of X it's elements (subsets of X) must be disjoint and cover all of X. If you keep in mind that the elements of P are non-empty ...


2

Good question. But the list of refinements of a composition is implemented. Thus you can do the following: def finer(p): # Return the list of all partitions refining the given partition ``p``. # # EXAMPLES:: # # sage: finer(Partition([3,2,1])) # [[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [2, 2, 1, 1], [3, 1, 1, 1], [3, 2, 1]] ...


3

I don't currently have Sage installed but browsing the documentation seems to indicate that taking a closed interval (with one end of the interval being your partition in question and the other end being the finest, all-ones partition) of the IntegerPartitions poset should do the trick. EDIT: I just tested it on SageMathCell, an online Sage interface, and ...


0

No sooner did I submit this than I realized that there is indeed a simple answer: Note that $f(2a; 2S) = 2 f(a;S)$. But by writing $2S = S + S$ and partitioning one $S$ into a sum of $(a-1)$ terms and the other into a sum of $(a+1)$ terms, because $f(2a,2S)$ is defined as an optimum, we see that $f(2a, 2S) \ge f(a-1, S) + f(a+1, S)$.


1

Induction on $n$. For $n=1,2$ there is nothing to prove. Assume the result is proved for $<n$ and consider the case $n$. We establish the case $n$ by induction on $m$. If $n$ is odd the smallest possible value of $m$ is $m=n$. We have $n=(n-1)+1=(n-2)+2=\dots=\frac{1}{2}(n+1)+\frac{1}{2}(n-1)$, so the result is true for $m=n,k=\frac{1}{2}(n+1)$. If $n$...



Top 50 recent answers are included