What Is The Formula for the 3 of 9 Bar Code Alphabet?

The right pattern to think how this encoding works is that 1) you find a set of "safe bit sequences", then 2) map your characters to these sequences.

End result feels like a random order, but each of these steps is quite logical per se.

"Safe" bit sequences are such that if you invert a single bit in any of it, result will be "outside" of your set. This is a form of error checking - basically a major "selling point" of Code 39.

• Say, if you want to "encode" that way two characters, you'll need two bits at least. 00 and 11 make a set of two safe bit sequences - break (invert) one bit in any of these and you will get invalid code. Note that set of 01 and 10 is safe, too.
   
  To encode three characters, one needs more than two bits.
  Example of safe set for three characters is 000, 110 and 011.

Now, you need to encode 39 characters.

First, find how much bits you need for that, then find a set of "safe bit sequences".

And only after that, map your characters, like first char -> first safe bit sequence, second char -> second sequence etc.

You see, it's easier to think in terms of "steps" here, not in terms of "formula".

Algorithm to find safe bit sequences for given number of bits N could be about as follows,

1. allocate boolean array of length 2 power N, initialize its elements with true
2. start with 0 - its boolean representation is N bits, each zero
3. do N times: invert one of the bits in 0 - that will be "unsafe bit sequence",
   mark array element at resulting index false
   _{array[1000], array[0100], array[0010], etc}
4. find next after 0index in array where element is true,
   for bit representation of that index, repeat same loop as above:
   invert one of the bits and mark respective ("unsafe") element of array false
5. find next true index and so on and so on until array ends

In the end, elements of array marked true will represent "safe bit sequences".

To transform these sequences to bar code, one would just map pairs of bits appropriately, like 00 - narrow black, 01 - narrow white, 10 - wide black, 11 - wide white.

The Wikipedia page you link to mentions that

Their original design included two wide bars and one wide space in each character, resulting in 40 possible characters.

As a reference it cites David Allais' memoirs:

I proceeded to illustrate a symbol character using the side of the chalk to draw the wide bars. The structure of five bars and four spaces including two wide bars and one wide space came to me in flash. The two of five coding in the bars afforded ten combinations and the wide space provided for four separate groups.

So with that in mind we can identify the marked bars and spaces and a pattern does emerge:

 BSBSBSBSB BB S 001122334 0 000110100 23 1 1 100100001 04 1 2 001100001 14 1 3 101100000 01 1 4 000110001 24 1 5 100110000 02 1 6 001110000 12 1 7 000100101 34 1 8 100100100 03 1 9 001100100 13 1 A 100001001 04 2 B 001001001 14 2 C 101001000 01 2 D 000011001 24 2 E 100011000 02 2 F 001011000 12 2 G 000001101 34 2 H 100001100 03 2 I 001001100 13 2 J 000011100 23 2 K 100000011 04 3 L 001000011 14 3 M 101000010 01 3 N 000010011 24 3 O 100010010 02 3 P 001010010 12 3 Q 000000111 34 3 R 100000110 03 3 S 001000110 13 3 T 000010110 23 3 U 110000001 04 0 V 011000001 14 0 W 111000000 01 0 X 010010001 24 0 Y 110010000 02 0 Z 011010000 12 0 - 010000101 34 0 . 110000100 03 0 011000100 13 0 * 010010100 23 0 

Note that the bars for 0 in the first section correspond instead to 10 in the other three sections. If we rotate the bars to be ordered 40123 then the pattern we see is

 40123 04 xx... 14 x.x.. 01 .xx.. 24 x..x. 02 .x.x. 12 ..xx. 34 x...x 03 .x..x 13 ..x.x 23 ...xx 

which is one of the obvious ways of enumerating pairs of 5 elements.

Equivalently, if you name the bits B1-S3-B2-S0-B3-S1-B4-S2-B0 from left to right in your representation and instead represent each code as SBB indices then the sequence 12..90AB..YZ-. * becomes 010 020 021 030 031 032 040 041 042 043 110 120 ... 342 343.