A355748 Number of ways to choose a sequence of divisors, one of each part of the n-th composition in standard order.

1, 1, 2, 1, 2, 2, 2, 1, 3, 2, 4, 2, 2, 2, 2, 1, 2, 3, 4, 2, 4, 4, 4, 2, 3, 2, 4, 2, 2, 2, 2, 1, 4, 2, 6, 3, 4, 4, 4, 2, 6, 4, 8, 4, 4, 4, 4, 2, 2, 3, 4, 2, 4, 4, 4, 2, 3, 2, 4, 2, 2, 2, 2, 1, 2, 4, 4, 2, 6, 6, 6, 3, 6, 4, 8, 4, 4, 4, 4, 2, 4, 6, 8, 4, 8, 8, 8

Offset

0,3

Comments

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

Links

Table of n, a(n) for n=0..86.

Example

Composition number 152 in standard order is (3,1,4), and the a(152) = 6 choices are: (1,1,1), (1,1,2), (1,1,4), (3,1,1), (3,1,2), (3,1,4).

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Times@@Length/@Divisors/@stc[n], {n, 0, 100}]

Crossrefs

Positions of 1's are A000079 (after the first).

The anti-run case is A354578, zeros A354904, firsts A354905.

An unordered version (using prime indices) is A355731:

- firsts A355732,

- resorted A355733,

- weakly increasing A355735,

- relatively prime A355737,

- strict A355739.

A000005 counts divisors.

A003963 multiplies together the prime indices of n.

A005811 counts runs in binary expansion.

A029837 adds up standard compositions, lengths A000120.

A066099 lists the compositions in standard order.

A353851 counts compositions with all equal run-sums, ranked by A353848.

A353852 ranks compositions with all distinct run-sums, counted by A353850.

Cf. A124767, A175413, A238279, A274174, A326841, A333381, A333755, A353847, A353849, A355747.

Sequence in context: A369466 A060764 A105149 * A295894 A068307 A363721

Adjacent sequences: A355745 A355746 A355747 * A355749 A355750 A355751

Keyword

nonn

Author

Gus Wiseman, Jul 23 2022

Status

approved