All possibilities of seven numbers in ascending order?

Question

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?

Answer 1

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)?

Answer 2

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.

Answer 3

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.

Answer 4

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;
}

Answer 5

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} $$