Tag Info

New answers tagged

1

I am posting a recursive algorithm to print all such combinations. Hope this will be helpful. //prints all ordered combination of 1 and 2 which sum up to n function printAll(n){ //[] is empty list print(n,[]) } function print(n,list){ //base case if(n==0){ output all the elements in list }else{ //passing a new list by appending "1" ...


0

A simpler way to state the same is the following: Suppose $A = \{a_0, …, a_{k-1} \}$ is a partition of $n$ into $k$ positive distinct integers. Then take the following partition: $$ A' = \{a_0-1, …, a_{k-1}-1\} $$ so $$ \sum A' = n-k $$ and $A'$ has either $k$ or $k-1$ distinct positive integers (at most one of them is $0$). This process defines a function ...


0

This problem merits special attention because it is an instance of a partition problem that can be solved by the Polya Enumeration Theorem as well as by Ferrer's diagrams. Using the material from this MSE link we have for the sum on the LHS the equality $$\sum_{q=1}^k P_q(n) = \sum_{q=1}^k [z^n] Z(S_q)\left(\frac{z}{1-z}\right) = [z^n] \sum_{q=1}^k ...


2

HINT: Take any partition of $n+k$ into $k$ parts and subtract $1$ from each part. What do you get? Is the process reversible?


1

I am not sure, what you refer to as the last example, but there is indeed 1-to-1 correspondence between algebras and partitions at over finite sets. The elements of partitions are atoms of the algebra, that is sets that don't contain any proper non-empty subset which is also an element of algebra. Note that partition $$ E := ...


0

Suppose that our partition contains an entry $m\gt 4$. We show that it is profitable to split $m$. It is convenient to divide into two cases, $m$ odd and $m$ even. Suppose that $m$ is odd, say $m=2k+1$. We show that it is profitable to split $m$ as $k+(k+1)$. It is enough to show that $k(k+1)\gt 2k+1$, or equivalently that $k^2-k-1\gt 0$. Since $k\ge 2$, ...


6

By way of enrichment I would like to point out that using the Polya Enumeration Theorem the closed form is also given by $$n! [z^k] Z(P_n)\left(\frac{1}{1-z}\right)$$ where $Z(P_n) = Z(A_n)-Z(S_n)$ is the difference between the cycle index of the alternating group and the cycle index of the symmetric group. This cycle index is known in species ...


6

This is really just a commentary on yashg's (now deleted) answer; I just want to provide a bit of context and a reference. To save repetition: all variables in this post are restricted to integers. The title of the question is somewhat confusing: the vector $(0,1,3)$ is a solution, not a "set of solutions", of the multivariable equation $k_1+k_2+k_3=4$. ...


2

The ordered pairs are going to be all those pairs of the form $(x,y)$ where $x$ and $y$ belong to the same part. There should be $3^2+2^2$ such pairs in this case.


3

I believe I've found a solution, but it's up to you all to check its correctness. Here it goes: We have to find the number of non-negative integral solutions to :$$k_1+k_2+....+k_n=P$$ where $k_i\in \{ 0,1,2,3,.....\}$ , $P\in\{1,2,3,4,....\}$ and $k_i\ne k_j$ Since all the numbers in LHS are distinct, we can assume for simplicity that $k_i<k_{i+1}$ ...


0

If $k_i$ are not ditinct then the total ways are: $$\sum_{i}^nk_i=k,k_i\ge0\longrightarrow \binom{k+n-1}{n-1}$$ Now we need to use inclusion-exclusion to remove cases where any two or more $k_i$'s are equal, note that you need to be more careful while using inclusion-exclusion beacuse when taking for example $k_1$ and $k_2$ equal there may be the case that ...


0

It is not my area of expertise, but I believe that what you are after are called in the literature compositions of $k$ into $n$ distinct parts. You can probably find the answer in the following 1995 paper by B.Richmond and A.Knopfmacher "Compositions with distinct parts" (link), to which I unfortunately have no access. The generating function for the ...


0

the main point is that if you sepcify three students with $A$,$B$,$C$, which means that we distinguish these three student, then we can conclude the answer is $\{\begin{pmatrix} 3\\ 1 \end{pmatrix}+\begin{pmatrix} 2\\ 1 \end{pmatrix}+\begin{pmatrix} 1\\ 1 \end{pmatrix} \} \begin{pmatrix} 8\\ 2 \end{pmatrix}\begin{pmatrix} 6\\ 2 \end{pmatrix}\begin{pmatrix} ...


1

We assume that Student 1 picks $2$ problems, then Student 2 picks $2$ problems from the remaining $6$, then Student $3$ picks $2$ problems from the remaining $4$. Then S1 has $\binom{8}{2}$ choices, and for every such choice S2 has $\binom{6}{2}$ choices, and then S3 has $\binom{4}{2}$ choices, for a total of $\binom{8}{2}\binom{6}{2}\binom{4}{2}$, This ...


0

No. How does the $8!/(2!)^4$ arise? First, we order the questions in a random way (that's $8!$). Then give first two questions to the first student (disregarding the order between them, so we divide by $2!$). Then we give the next two to the second, third pair to the third, and then there are two left. In each pair the order doesn't matter, so we divide by ...


0

Well the way I interpret the question is that every student gets the same list. You are correct, if every student got a different list order, the answer would be different. But then it is not necessarily your 3! factor to resolve this because there are also cases where both students get the same list. So in short, you thought too hard about the question :)


2

The proof of the asymptotic formula for the partition function given by Hardy and Ramanujan was "the birth of the circle method", and used properties of modular forms. Erdös was trying to give a proof with elementary methods (he also gave a so-called elementary proof of the PNT with Selberg). He succeeded in 1942 to give such a proof, but only with "unknown" ...


1

Hints: For $x\in M$, let $[x]$ be the equivalence class of $x$ with respect to $\sim$. $x\sim y \Leftrightarrow [x]=[y]$ Also $M/\sim=\{[x]:x\in M\}$ Now think about what it means for two elements of $M$ to be related with respect to $∼_{M/∼}$



Top 50 recent answers are included