CONTENTS v
7.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.2 Co-lexicographic order for compositions into exactly k parts . . . . . . . . . . . . . . . . 195
7.3 Compositions and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
7.4 Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
8 Subsets 201
8.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.2 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
8.3 Ordering with De Bruijn sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.4 Shifts-order for subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.5 k-subsets where k lies in a given range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9 Mixed radix numbers 219
9.1 Counting (lexicographic) order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
9.2 Minimal-change (Gray code) order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
9.3 gslex order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
9.4 endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
9.5 Gray code for endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
10 Permutations 233
10.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
10.2 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
10.3 Factorial representations of permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
10.4 An order from reversing prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
10.5 Minimal-change order (Heap’s algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
10.6 Lipski’s Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
10.7 Strong minimal-change order (Trotter’s algorithm) . . . . . . . . . . . . . . . . . . . . . . 254
10.8 Minimal-change orders from factorial numbers . . . . . . . . . . . . . . . . . . . . . . . . 259
10.9 Orders where the smallest element always moves right . . . . . . . . . . . . . . . . . . . . 267
10.10 Single track orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
10.11 Star-transposition order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
10.12 Derangement order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
10.13 Recursive algorithm for cyclic permutations . . . . . . . . . . . . . . . . . . . . . . . . . . 279
10.14 Minimal-change order for cyclic permutations . . . . . . . . . . . . . . . . . . . . . . . . . 281
10.15 Permutations with special properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
11 Subsets and permutations of a multiset 291
11.1 Subsets of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
11.2 Permutations of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
12 Gray codes for strings with restrictions 301
12.1 List recursions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
12.2 Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
12.3 Generalized Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
12.4 Digit x followed by at least x zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
12.5 Generalized Pell words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
12.6 Sparse signed binary words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
12.7 Strings with no two successive nonzero digits . . . . . . . . . . . . . . . . . . . . . . . . . 312
12.8 Strings with no two successive zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
12.9 Binary strings without substrings 1x1 or 1xy1 . . . . . . . . . . . . . . . . . . . . . . . . 315
13 Parenthesis strings 319
13.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
13.2 Gray code via restricted growth strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
[fxtbook draft of 2008-October-26]
