A303974 Regular triangle where T(n,k) is the number of aperiodic multisets of size k that fit within some normal multiset of size n.

1, 2, 1, 3, 3, 3, 4, 6, 10, 6, 5, 10, 22, 23, 15, 6, 15, 40, 57, 62, 27, 7, 21, 65, 115, 165, 129, 63, 8, 28, 98, 205, 356, 385, 318, 120, 9, 36, 140, 336, 676, 914, 1005, 676, 252, 10, 45, 192, 518, 1176, 1885, 2524, 2334, 1524, 495, 11, 55, 255, 762, 1918, 3528, 5495, 6319, 5607, 3261, 1023

Offset

1,2

Comments

A multiset is normal if it spans an initial interval of positive integers. It is aperiodic if its multiplicities are relatively prime.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Formula

T(n,k) = Sum_{d|k} mu(k/d) * Sum_{i=1..d} binomial(d-1, i-1)*binomial(n-k+i, i). - Andrew Howroyd, Sep 18 2018

Example

Triangle begins:
1
2    1
3    3    3
4    6   10    6
5   10   22   23   15
6   15   40   57   62   27
7   21   65  115  165  129   63
8   28   98  205  356  385  318  120
9   36  140  336  676  914 1005  676  252
The a(4,3) = 10 multisets: (112), (113), (122), (123), (124), (133), (134), (223), (233), (234).
The a(5,4) = 23 multisets:
(1112), (1222),
(1113), (1123), (1223), (1233), (1333), (2223), (2333),
(1124), (1134), (1224), (1234), (1244), (1334), (1344), (2234), (2334), (2344),
(1235), (1245), (1345), (2345).

Mathematica

allnorm[n_Integer]:=Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1];
Table[Length/@GatherBy[Select[Union@@Rest/@Subsets/@allnorm[n], GCD@@Length/@Split[#]===1&], Length], {n, 10}]

Prog

(PARI) T(n, k)={sumdiv(k, d, moebius(k/d)*sum(i=1, d, binomial(d-1, i-1)*binomial(n-k+i, i)))} \\ Andrew Howroyd, Sep 18 2018

Crossrefs

Row sums are A303976.

Cf. A000740, A000837, A001597, A007716, A007916, A027941, A178472, A210554, A301700, A303431, A303546, A303551, A303945.

Sequence in context: A029161 A035384 A360033 * A153868 A341147 A325335

Adjacent sequences: A303971 A303972 A303973 * A303975 A303976 A303977

Keyword

nonn,tabl

Author

Gus Wiseman, May 03 2018

Extensions

Terms a(56) and beyond from Andrew Howroyd, Sep 18 2018

Status

approved