A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 2, 3, 0, 0, 2, 4, 6, 4, 0, 0, 4, 6, 9, 8, 5, 0, 0, 2, 6, 15, 20, 15, 6, 0, 0, 4, 8, 24, 32, 35, 18, 7, 0, 0, 3, 10, 27, 56, 70, 54, 28, 8, 0, 0, 4, 12, 42, 84, 125, 120, 84, 32, 9, 0, 0, 2, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0

Offset

0,5

Comments

A composition of n is a finite sequence of positive integers summing to n.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Formula

T(n,k) = Sum_{m|n} Sum_{d|gcd(k,m)} mu(d)*binomial(m/d-1, k/d-1) for n > 0. - Andrew Howroyd, Jan 19 2023

Example

Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   3   2   3   0
   0   2   4   6   4   0
   0   4   6   9   8   5   0
   0   2   6  15  20  15   6   0
   0   4   8  24  32  35  18   7   0
   0   3  10  27  56  70  54  28   8   0
   0   4  12  42  84 125 120  84  32   9   0
   0   2  10  45 120 210 252 210 120  45  10   0
   0   6  18  66 168 335 450 462 320 162  50  11   0
Row n = 6 counts the following compositions (empty columns indicated by dots):
  .  (6)       (15)    (114)  (1113)  (11112)  .
     (33)      (24)    (123)  (1122)  (11121)
     (222)     (42)    (132)  (1131)  (11211)
     (111111)  (51)    (141)  (1221)  (12111)
               (1212)  (213)  (1311)  (21111)
               (2121)  (231)  (2112)
                       (312)  (2211)
                       (321)  (3111)
                       (411)

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Function[c, Length[Union[Array[RotateRight[c, #]&, Length[c]]]]==k]]], {n, 0, 10}, {k, 0, n}]

Prog

(PARI) T(n, k)=if(n==0, k==0, sumdiv(n, m, sumdiv(gcd(k, m), d, moebius(d)*binomial(m/d-1, k/d-1)))) \\ Andrew Howroyd, Jan 19 2023

Crossrefs

Column k = 1 is A000005.

Row sums are A011782.

Diagonal T(2n,n) is A045630(n).

The strict version is A072574.

A version counting runs is A238279.

Column k = n - 1 is A254667.

Aperiodic compositions are counted by A000740.

Aperiodic binary words are counted by A027375.

The orderless period of prime indices is A052409.

Numbers whose binary expansion is periodic are A121016.

Periodic compositions are counted by A178472.

Period of binary expansion is A302291.

Numbers whose prime signature is aperiodic are A329139.

All of the following pertain to compositions in standard order (A066099):

- Length is A000120.

- Necklaces are A065609.

- Sum is A070939.

- Rotational symmetries are counted by A138904.

- Constant compositions are A272919.

- Lyndon compositions are A275692.

- Co-Lyndon compositions are A326774.

- Aperiodic compositions are A328594.

- Rotational period is A333632.

- Co-necklaces are A333764.

- Reversed necklaces are A333943.

Cf. A000031, A001037, A008965, A019536, A211100, A291166, A328595, A328596, A329312, A329313, A329326.

Sequence in context: A099766 A194947 A132339 * A137676 A333755 A238130

Adjacent sequences: A333938 A333939 A333940 * A333942 A333943 A333944

Keyword

nonn,tabl

Author

Gus Wiseman, Apr 16 2020

Status

approved