A351204 - OEIS

A351204

Number of integer partitions of n such that every permutation has all distinct runs.

%I #11 Feb 16 2022 01:50:08

%S 1,1,2,3,4,5,8,9,11,14,18,20,25,28,34,41,47,53,64,72,84,98,113,128,

%T 148,169,194,223,255,289,333,377,428,488,554,629,715,807,913,1033,

%U 1166,1313,1483,1667,1875,2111,2369,2655,2977,3332,3729,4170,4657,5195,5797,6459

%N Number of integer partitions of n such that every permutation has all distinct runs.

%C Partitions enumerated by this sequence include those in which all parts are either the same or distinct as well as partitions with an even number of parts all of which except one are the same. - _Andrew Howroyd_, Feb 15 2022

%H Andrew Howroyd, <a href="/A351204/b351204.txt">Table of n, a(n) for n = 0..1000</a>

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/q/87559">What is a sequence run? (answered 2011-12-01)</a>

%e The a(1) = 1 through a(8) = 11 partitions:

%e (1) (2) (3) (4) (5) (6) (7) (8)

%e (11) (21) (22) (32) (33) (43) (44)

%e (111) (31) (41) (42) (52) (53)

%e (1111) (2111) (51) (61) (62)

%e (11111) (222) (421) (71)

%e (321) (2221) (431)

%e (3111) (4111) (521)

%e (111111) (211111) (2222)

%e (1111111) (5111)

%e (311111)

%e (11111111)

%t Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!UnsameQ@@Split[#]&]=={}&]],{n,0,15}]

%o (PARI) \\ here Q(n) is A000009.

%o Q(n)={polcoef(prod(k=1, n, 1 + x^k + O(x*x^n)), n)}

%o a(n)={Q(n) + if(n, numdiv(n) - 1) + sum(k=1, (n-1)\3, sum(j=3, (n-1)\k, j%2==1 && n-k*j<>k))} \\ _Andrew Howroyd_, Feb 15 2022

%Y The version for run-lengths instead of runs is A000005.

%Y The version for normal multisets is 2^(n-1) - A283353(n-3).

%Y The complement is counted by A351203, ranked by A351201.

%Y A005811 counts runs in binary expansion.

%Y A044813 lists numbers whose binary expansion has distinct run-lengths.

%Y A059966 counts Lyndon compositions, necklaces A008965, aperiodic A000740.

%Y A098859 counts partitions with distinct multiplicities, ordered A242882.

%Y A238130 and A238279 count compositions by number of runs.

%Y A297770 counts distinct runs in binary expansion.

%Y A003242 counts anti-run compositions.

%Y Counting words with all distinct runs:

%Y - A351013 = compositions, for run-lengths A329739, ranked by A351290.

%Y - A351016 = binary words, for run-lengths A351017.

%Y - A351018 = binary expansions, for run-lengths A032020, ranked by A175413.

%Y - A351200 = patterns, for run-lengths A351292.

%Y - A351202 = permutations of prime factors.

%Y Cf. A000041, A035363, A047993, A116608, A144300, A329746, A351291.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 15 2022

%E Terms a(26) and beyond from _Andrew Howroyd_, Feb 15 2022