A353851 Number of integer compositions of n with all equal run-sums.

1, 1, 2, 2, 5, 2, 8, 2, 12, 5, 8, 2, 34, 2, 8, 8, 43, 2, 52, 2, 70, 8, 8, 2, 282, 5, 8, 18, 214, 2, 386, 2, 520, 8, 8, 8, 1957, 2, 8, 8, 2010, 2, 2978, 2, 3094, 94, 8, 2, 16764, 5, 340, 8, 12310, 2, 26514, 8, 27642, 8, 8, 2, 132938, 2, 8, 238, 107411, 8, 236258

Offset

0,3

Comments

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).

Links

David A. Corneth, Table of n, a(n) for n = 0..10000

Formula

From David A. Corneth, Jun 02 2022 (Start)

a(p) = 2 for prime p.

a(p*q) = 8 for distinct primes p and q (Cf. A006881).

a(n) = Sum_{d|n} tau(d)*(tau(d)-1) ^ (n/d - 1) where tau = A000005. (End)

Example

The a(0) = 1 through a(8) = 12 compositions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
           (11)  (111)  (22)    (11111)  (33)      (1111111)  (44)
                        (112)            (222)                (224)
                        (211)            (1113)               (422)
                        (1111)           (2112)               (2222)
                                         (3111)               (11114)
                                         (11211)              (41111)
                                         (111111)             (111122)
                                                              (112112)
                                                              (211211)
                                                              (221111)
                                                              (11111111)
For example:
  (1,1,2,1,1) has run-sums (2,2,2) so is counted under a(6).
  (4,1,1,1,1,2,2) has run-sums (4,4,4) so is counted under a(12).
  (3,3,2,2,2) has run-sums (6,6) so is counted under a(12).

Mathematica

Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n], SameQ@@Total/@Split[#]&]], {n, 0, 15}]

Prog

(PARI) a(n) = {if(n <=1, return(1)); my(d = divisors(n), res = 0); for(i = 1, #d, nd = numdiv(d[i]); res+=(nd*(nd-1)^(n/d[i]-1)) ); res } \\ David A. Corneth, Jun 02 2022

Crossrefs

The version for parts or runs instead of run-sums is A000005.

The version for multiplicities instead of run-sums is A098504.

All parts are divisors of n, see A100346.

The version for partitions is A304442, ranked by A353833.

The version for run-lengths instead of run-sums is A329738, ptns A047966.

These compositions are ranked by A353848.

The distinct instead of equal version is A353850.

A003242 counts anti-run compositions, ranked by A333489.

A005811 counts runs in binary expansion.

A011782 counts compositions.

A353847 represents the composition run-sum transformation.

For distinct instead of equal run-sums: A032020, A098859, A242882, A329739, A351013, A353837, ranked by A353838 (complement A353839), A353852, A354580, ranked by A354581.

Cf. A000005, A006881, A238279, A275870, A333755, A351014, A351016, A351017, A353832, A353834, A353849, A353853-A353859 (run-sum trajectory), A353860, A353863, A353864, A353932.

Sequence in context: A368580 A309208 A293225 * A305798 A305808 A353858

Adjacent sequences: A353848 A353849 A353850 * A353852 A353853 A353854

Keyword

nonn,easy

Author

Gus Wiseman, May 31 2022

Extensions

More terms from David A. Corneth, Jun 02 2022

Status

approved