[seqfan] Re: First difference of lexigraphical ordering of subsets of integers

[M. F. Hasler]

On Mon, Dec 2, 2019 at 11:44 PM Tommaso Martino <tommartin at hotmail.it>
wrote:

> Hello seqfans,
> this is my first attempt, so I hope to not get in wrong.
>
> Given S={1,2,3,4,5,6,7,8,9}, we can generate a finite sequence containing
> the lexicographical ordering of the subsets of k elements of S.
> We now define the new sequence a(n) as the first difference of such list,
> which is a(n+1)-a(n).
>

where the 2nd and 3rd a()  not the same as the first a().

The 2nd and 3rd a() correspond to
A009993 <https://oeis.org/A009993> List of numbers whose decimal digits are
in strictly increasing order.
(PARI) for(L=0,4,forsubset([9,L], s, print1(fromdigits(Vec(s))",")))
0,1,2,3,4,5,6,7,8,9,12,13,14,15,16,17,18,19,23,24,25,26,27,28,29,34,35,36,37,38,39,45,46,47,48,49,56,57,58,59,67,68,69,78,79,89,123,124...

The first differences of this sequence indeed don't appear to be in OEIS,
they go:
1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 5,
1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 7, 1, 1, 1, 8, 1, 1, 9, 1, 10, 34, 1, 1, 1,
1, 1, 1, 5, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 7, 1, 1, 1, 8, 1, 1, 9, 1, 10,
45, 1, 1, 1, 1, 1, 6, ...

I think this could be added to OEIS.

> --
Maximilian





> -- Example 1.
> Given S, the lexicographical ordering on the subsets of 2 elements of S is:
>
>   12 13 14 15 16 17 18 19 23 24 25
>   26 27 28 29 34 35 36 37 38 39 45
>   46 47 48 49 56 57 58 59 67 68 69
>   78 79 89
>
> The first difference of the generated sequence is:
>
>   1  1  1  1  1  1  1  4
>   1  1  1  1  1  1  5
>   1  1  1  1  1  6
>   1  1  1  1  7
>   1  1  1  8
>   1  1  9
>   1  10
>
> -- Example 2.
> Given S, the lexicographical ordering on the subsets of 3 elements of S is:
>
>   123 124 125 126 127 128 129 134 135 136 137 138 139 145 146 147 148 149
>   156 157 158 159 167 168 169 178 179 189 234 235 236 237 238 239 245 246
>   247 248 249 256 257 258 259 267 268 269 278 279 289 345 346 347 348 349
>   356 357 358 359 367 368 369 378 379 389 456 457 458 459 467 468 469 478
>   479 489 567 568 569 578 579 589 678 679 689 789
>
> The first difference of the generated sequence is:
>
>   1   1   1   1   1   1
>   5   1   1   1   1   1
>   6   1   1   1   1   7
>   1   1   1   8   1   1
>   9   1  10  45   1   1
>   1   1   1   6   1   1
>   1   1   7   1   1   1
>   8   1   1   9   1  10
>   56  1   1   1   1   7
>   1   1   1   8   1   1
>   9   1  10  67   1   1
>   1   8   1   1   9   1
>   10  78  1   1   9   1
>   10  89  1  10 100
>
> Some repeating pattern seems to appear in the sequence.
> Different sequences can be generated with the same S, and increasing
> values of k < S.
> The length of the sequence can be easily computed, and it is a function of
> both k and S.
> Modifying the length of S, for example S={2..8}, different sequences can
> be obtained.
>
> Is it worth submitting to OEIS?
>
> Thank you,
> Tommaso MARTINO