2
$\begingroup$

Let $q(n)$ denote the number of ordered sets of positive integers whose sum is $n$. Calculate $q(n)$ using a direct counting argument. I really don't quite understand the rules. What does "ordered" really stand for here? After that, I am asked to look at unordered sets. Am I allowed to use the same number more than once? I am really confused here, and the calculation seem to lead me nowhere solid. I would appreciate any outlook.

$\endgroup$
3
$\begingroup$

Here is the likely meaning for "ordered" and "unordered," in the form of an example, with $n=4$:

Ordered sets summing to $4$:

$$\begin{align} &1+1+1+1\\ &2+1+1,\quad 1+2+1,\quad 1+1+2\\ &2+2\\ &3+1,\quad1+3\\ &4 \end{align}$$

(so $q(4)=8$).

Unordered sets summing to $4$:

$$\begin{align} &1+1+1+1\\ &2+1+1\\ &2+2\\ &3+1\\ &4 \end{align}$$

(so $p(4)=5$, if we let $p(n)$ denote the number of unordered sets of positive integers whose sum in $n$).

Note that nothing here is actually a "set" in the usual mathematical sense of the word. Nor do the adjectives "ordered" and "unordered" look like they've been affixed correctly: the "unordered" sets have things nicely ordered (from largest to smallest in each sum), whereas the "ordered" sets seem to allow things to be out of order! Nonetheless I'm willing to bet that this is what's meant by the terminology here. If it is, and if you need further help, I (or someone else) will gladly provide it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So, "ordered" means "specific"? Excuse my lacking sense of rationality. I have arrived at a point where I no longer distinguished between "ordered" and "non-decreasing" or monotone. $\endgroup$ – Meitar Mar 29 '16 at 18:01
  • $\begingroup$ It was translated, and I believe my teacher, writing the notes, used the wrong term (really wasting my time). $\endgroup$ – Meitar Mar 29 '16 at 18:02
  • 1
    $\begingroup$ @Meitar, "ordered" here means that the (linear) order in which summands appear matters, which is why $3+1$ and $1+3$ each count once. You can think of "ordered" as placing things in a row, and "unordered" as putting them in a bag. $\endgroup$ – Barry Cipra Mar 29 '16 at 18:05
  • $\begingroup$ Okay, I have arrived at $2^{n-1}$ using recurrence. The examples are consistent so far. Do you know if this is correct? $\endgroup$ – Meitar Mar 29 '16 at 18:33
  • 1
    $\begingroup$ @Meitar, yes, very good! You can find confirmation -- and some different terminology -- at en.wikipedia.org/wiki/Composition_(combinatorics) . Be sure also to click on the link to "partitions" for the unordered case (where there is no such nice, simple formula). $\endgroup$ – Barry Cipra Mar 29 '16 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.