1. Stenography keyboard - combinations

Minor debate raging in the court reporting community over the total number of possible strokes (distinct combinations of keys in a fixed order) on the standard machine shorthand (stenograph) machine.

The rules are:

1. There are 22 keys on the keyboard.
2. A stroke is formed by combining any number of keys between 1 and 22.
3. Order matters.
4. No repetition.

Extra credit: Newer stenograph machines have optional features. What if there are 23, 24, 25, 26, or 27 keys?

Note: You don't need to know anything about the stenograph machine to solve the math above, and an explanation of stenography will probably confuse rather than clarify. But here it is:

Yes, there's an S (and T and P and R) on both the left and right side of the keyboard. But they are different keys!
Each key has its own column from left to right. Each row constitutes one stroke.

So a single stroke can contain any of the following in this order: S, T, K, P, W, H, R, A, O, *, E, U, -F, -R, -P, -B, -L, -G, -T, -S, -D, -Z.

2. Re: Stenography keyboard - combinations

Let $k_1="S", k_2="T"$ etc.

If your word starts with $k_1$ there are $\begin{pmatrix}21 \\ k\end{pmatrix}$ length (k+1) words. $0<k\leq 21$

If your word starts with $k_m$ there are $\begin{pmatrix}22-m \\ k\end{pmatrix}$ length (k+1) words. $0<k\leq 22-m$

So you end up with the double summation

$N=\displaystyle{\sum_{m=1}^{22} \sum_{k=0}^{22-m}}\begin{pmatrix}22-m \\ k\end{pmatrix}=4194303$

someone should probably check this.

3. Re: Stenography keyboard - combinations

Thanks, romsek. The math of the summations is over my head.

But the result, 4194303, is a familiar one, one that has been put forth as a solution.

My brute-force analysis suggests that for n keys on the keyboard, there are 2^n - 1 possibilities:

one key: S = 1 = 2^1 - 1
two keys: S, ST, T = 3 = 2^2 - 1
three keys: S, ST, SK, STK, T, K, TK = 7 = 2^3 - 1
four keys: S, ST, SK, SP, STK, STP, SKP, STKP, T, TK, TP, TKP, K, KP, P = 15 = 2^4 - 1
.
.
.
22 keys = 2^22 - 1 = 4194303 -- which, happily, is the result you got by a different method.

Thanks!