Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I had posted a question about a pretty old permutation cipher here on Stack Overflow.

One @Mark Adler has commented that all possibilities of seven numbers with range $0$-$255$ in ascending order is $9,503,812,464$.

I tried to speculate by saying "Ok you mean each byte can be having value $0$-$255$ if first byte is $255$ then all others are also $255$. This is one way. If first byte is $254$ then there can be seven ways for remaining bytes ie $255,255,255,255,255,255$ or $254,255,255,255,255,255$ or $254,254,255,255,255,255$ or .... $254,254,254,254,254,254$ yes i seem to get it"

But I am not sure how to count all possibilities. Can anyone please help?

share|improve this question
    
Certainly the number $9,503,812,464$ is way wrong, and I think Mark Adler knew that, because in the Stack Overflow question it would allow the sorted array to be encoded in $34$ bits; add $13$ bits for a permutation of $7$ to reconstruct the order and you've only $47$ bits encoding a general $56$ bit number, which is impossible. For an approximation of the true number, divide $2^{7\times 8}$ by $7!=5040$ to get about $14\times10^{12}$ rather than $9.5\times10^9$. –  Marc van Leeuwen Aug 4 '12 at 11:07
    
I found @Marc van Leeuwen's answer to be useful as it provides some future directions to a novice like me. I would have liked a few more answers. Thanks everyone for helping me. –  Mukesh Kamath Aug 26 '12 at 5:31
    
The hasty answer in the comment over on SO was wrong. It is corrected now. –  Mark Adler Sep 15 '12 at 17:05

5 Answers 5

up vote 7 down vote accepted

If $$0\le a_1\le a_2\le\cdots\le a_7\le255$$ then let $$b_0=a_1, b_1=a_2-a_1,b_2=a_3-a_2,\dots,b_6=a_7-a_6,b_7=255-a_7$$ and you have $$b_0+b_1+\cdots+b_7=255,\quad b_j\ge0.\tag1$$ Conversely, any solution of (1) gives you numbers $a_j$. So, do you know how to count the number of solutions of (1)?

share|improve this answer
    
I had the essence of this transformation in my mind but did'nt know it will lead me to answer. If first number(b0) is 255 all others are 0. If it is 254 then there must be a 1 somewhere in the other seven numbers. Position of this 1 yields 7 ways. I am now able to think of 253 then there must be 2 so seven more ways or 1 and 1 so 6+5+4+3+2+1 ie 21. I am thinking of a short cut sir. This must be a standard result just like factorization but i am not aware of it. –  Mukesh Kamath Aug 4 '12 at 10:45
    
I got it sir. I searched about partitions and realized it is a composition of a number n. I applied the binomial coefficient formula for (n-1,k-1) where n is 255 and k is 8. The answer is 12450563287800. I think this is 99.999% correct. Fully satisfied. –  Mukesh Kamath Aug 4 '12 at 11:17
1  
@MukeshKamath Sorry it's not. But think about it this way, there are 255 beads/dots/whatever all lined up in a row, and you have to split them into 7 partitions. Think about how many lines are needed to partition them, and where they can be drawn. –  ladaghini Aug 4 '12 at 11:25
    
@MukeshKamath: your answer is only 80% correct if you take percentage of the true answer as measure (which is of course nonsense, as it allows wrong answers being more than 100% correct; any wrong answer is in fact 0% correct). –  Marc van Leeuwen Aug 4 '12 at 12:25
    
Mukesh, don't use formulas you don't understand. If it were $b_0+b_1+b_2=1$, you wouldn't use the binomial coefficient for $(0,2)$, would you? Use the hint from ladaghini. –  Gerry Myerson Aug 4 '12 at 12:37

My favorite strategy is to translate all problems of this kind into one counting lattice paths across a rectangle, since this always works, and only requires remembering the formula for the number of lattice paths across a $a\times b$ rectangle (which follows from the transformation of combinations into lattice paths), namely $$\binom{a+b}a=\binom{a+b}b.$$

Here just translate each byte with value $v$ into a vertical step at line $v$ of a grid; a horizontal step between grid lines $i$ and $i+1$ will then necessarily occur at level $l$, where $l$ is the number of bytes in the array with value $v\leq i$. The vertical grid lines need to numbered $0$ to $255$, the horizonal ones $0$ to $7$, so one gets a lattice path across a $7\times 255$ rectangle.

Added Since I gather from a comment to another answer that lattice paths are "beyond" the OP, I'll add a short explanation. A lattice path across a $a\times b$ rectangle (with $a,b\in\mathbf N$) is a way to traverse such a rectangle from one (fixed) corner (the origin) to the diagonally opposite corner, by taking successive unit steps parallel to one of the sides, and in the right direction (no backing up). Clearly one needs exacly $a+b$ steps, of which $a$ vertical and $b$ horizontal steps (assuming the rectangle is aligned in that way), and arranging such steps in any order will do. So it just amounts to choosing $a$ elements (positions of vertical steps) among a set of $a+b$ (available positions), and it is just one possible way to formulate the combinatorial question defining binomial coefficients.

The reason that the lattice path point of view is often more convenient than the "choose $k$ out of $n$" point of view is merely that many enumerative combinatorial problems having (arbitrary) binomial coefficients as answer can be easily translated into a problem of choosing a lattice path across an appropriate rectangle. Examples are (0)(already mentioned) choosing a subset of $k$ among $n\geq k$ (with $(a,b)=(k,n-k)$); (1) choosing a $k$-multiset among $n>0$ (so repetitions are allowed; take $(a,b)=(k,n-1)$, number the base set $0,\ldots,n-1$ and take as many vertical steps on grid line $j$ as the multiplicity of $j$ in the multiset); (2) choosing a $k$-multiset among $n\leq k$, with each of those $n$ chosen at least once (take $(a,b)=(k-n,n-1)$, visit as many grid points on grid line $j$ as the multiplicity of $j$ in the multiset); (3) choosing an additive decomposition $m=a_1+\cdots+a_l$ of $m\in\mathbf N$ with specified $l>0$ and with each $a_i\in\mathbf N$ (take $(a,b)=(m,l-1)$, and do $a_{j+1}$ vertical steps on grid line $j$ for $0\leq j<l$; this is really just (1) with $(k,n)=(m,l)$); (4) choosing a weakly increasing function (or sequence) $f:[1,k]\to[0,n]$ (take $(a,b)=(n,k)$, reach vertical grid line $j\in[1,k]$ by a horizontal step at level $f(j)$); (5) choosing a strictly increasing function $f:[1,k]\to[1,n]$ (take $(a,b)=(n-k,k)$, first reach vertical grid line $j\in[1,k]$ by at step number $f(j)$; this is (0) transposed). The "stars and bars" argument is unnecessary. See also section 7.2.1.3 (Volume 4A) of Knuth's Art of Computer Programming for more points of view.

share|improve this answer
    
If you've done the computation, you can check your result with the answer by @Ian Mallett, in the comments. –  Marc van Leeuwen Aug 4 '12 at 12:30
    
I don't think @Ian's answer is correct. –  ladaghini Aug 4 '12 at 18:06
    
@ladaghini: Depends on which answer you mean. The second one is correct: $15508763342592$. –  Marc van Leeuwen Aug 4 '12 at 19:30
    
No, I believe he has one too many nested loops. –  ladaghini Aug 4 '12 at 21:03
    
@ladaghini: Seven nested loops for an array of seven bytes seems appropriate. In any case the answer is correct, and I found it without using any loops. –  Marc van Leeuwen Aug 5 '12 at 8:12

Brute force, unoptimized, ugly, dirty, recursive algorithm:

unsigned long counter = 0;
void f(int last, int n) {
    if (n==0) ++counter;
    else for (int i=last;i<256;++i) f(i,n-1); break;
}
int main(int argc, char *argv[]) {
    f(0,7);
    printf("Final total %lu\n",counter); getchar();
    return 0;
}

It will take some minutes to run. Even less general, but perhaps more clear:

int main(int argc, char *argv[]) {
    for (int a=0;a<256;++a)
        for (int b=a;b<256;++b)
            for (int c=b;c<256;++c)
                for (int d=c;d<256;++d)
                    for (int e=d;e<256;++e)
                        for (int f=e;f<256;++f)
                            for (int g=f;g<256;++g)
                                ++counter;
    printf("Final total %lu\n",counter);
    getchar();
    return 0;
}

Maybe I don't understand the question. I get 3,931,404,032.

share|improve this answer
    
Apparently you are using $32$ bits integers. Your answer is correct modulo $2^{32}$. You also encountered (and ignored) integer overflow $3610$ times. And if you had used the more appropriate %ld format, you would have found a negative result $-363563264$ –  Marc van Leeuwen Aug 4 '12 at 12:01
    
Ack--figured it was something like that. "counter" should be declared unsigned long long, and the printf should be "%llu". –  Ian Mallett Aug 4 '12 at 12:03
    
I am fully turned on now. I knew i could have done this. If you have got same result in both cases then i have to believe that number. I hope your counter has not overflown in both instances. –  Mukesh Kamath Aug 4 '12 at 12:04
    
Made the changes. Rerunning the second version, which is faster, I get the answer as 15,508,763,342,592. That's slightly over 12,450,563,287,800. I'm much more confident this time (unsigned long long overflows after 18,446,744,073,709,551,615). –  Ian Mallett Aug 4 '12 at 12:25

Of course the binomial calculation is the quickest path to the answer. However seeing the brute force approach above, a better brute force approach is provided here. The thing to do is remember previous answers and don't recalculate them. This code runs too quickly for the csh time command to measure, so it completes in less than a millisecond. I don't know how much less. (Since $256^7$ is less than $2^{64}$, this is guaranteed to not overflow an unsigned long long in C.) The result is $15\,508\,763\,342\,592$.

/* count how many 7-byte sorted sequences there are */

#include <stdio.h>
#include <string.h>

#define SEQLEN 7
#define SEQMAX 255

/* Memoization of seqs() results. */
unsigned long long memo[SEQLEN][SEQMAX+1];

/* Return the number of possible length n sorted descending sequences of
   non-negative integers with the first value less than or equal to a. */
unsigned long long seqs(int n, int a)
{
    int k;
    unsigned long long count;

    if (--n == 0)
        return a + 1;
    if (memo[n][a])
        return memo[n][a];
    count = 0;
    for (k = 0; k <= a; k++)
        count += seqs(n, k);
    memo[n][a] = count;
    return count;
}

int main(void)
{
    memset(memo, 0, sizeof(memo));
    printf("%llu\n", seqs(SEQLEN, SEQMAX));
    return 0;
}
share|improve this answer

This is a perfect application of "stars and bars". The high level idea is that you represent the situation not as numbers, but as properties of a sequence of symbols.

In this case, lay out a line of 255 stars

* * * * * * * * * * * * * * * ...

and then you place bars into the picture to represent a particular sequence of bytes. In this case, if the $n$-th byte is $x$, then we place the $n$-th bar after the $x$-th star.

For simplicity, consider instead 3 numbers in the range 0-7, rather than 7 numbers in the range 0-255.

The triple of numbers (0, 3, 3) would look like

| * * * | | * * * *

conversely, if we were just given the picture, it's easy to work out what the three numbers are.

Let me say that again. To any triple of numbers, we can draw an associated diagram. From each diagram, we can recover a triple of numbers. In particular, the triple is unique, and every diagram corresponds to a triple.

So, the number of triples of non-decreasing numbers in 0-7 is the same as the number of ways to draw a picture using 7 stars and 3 bars.

The original problem is the same, with 255 stars and 7 bars. So the number of possibilities is

$$ \binom{262}{7} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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