The On-Line Encyclopedia of Integer Sequences (OEIS)

A345165 revision #14

A345165

Number of integer partitions of n without an alternating permutation.

0, 0, 1, 1, 2, 2, 5, 5, 8, 11, 17, 20, 29, 37, 51, 65, 85, 106, 141, 175, 223, 277, 351, 432, 540, 663, 820, 999, 1226, 1489, 1817, 2192, 2654, 3191, 3847, 4603, 5517, 6578, 7853, 9327, 11084, 13120, 15533, 18328, 21621, 25430, 29905, 35071, 41111, 48080, 56206, 65554, 76420, 88918, 103394, 120015, 139214, 161222, 186593, 215632, 249006, 287165, 330938, 380888, 438075, 503255, 577713, 662459

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it has the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

This sequence can be generated by the following pseudo code:

outputMap[2 to n] = n

for usedNumbers = 2 to n

for medianSize = ceil(usedNumbers / 2) + 1 to usedNumbers - 1

for medianValue = 1 to floor((n - usedNumbers + medianSize) / medianSize)

for numbersAboveMedian = 0 to usedNumbers - medianSize

calculateState(usedNumbers, medianSize, medianValue, numbersAboveMedian)

next numbersAboveMedian

next medianValue

next medianSize

if (usedNumbers mod 2 == 1)

for medianValue = 2 to Math.floor((n - usedNumbers + ceil(usedNumbers / 2))/ceil(usedNumbers / 2))

for numbersAboveMedian = 1 to usedNumbers - ceil(usedNumbers / 2) - 1

calculateState(usedNumbers, ceil(usedNumbers / 2), medianValue, numbersAboveMedian)

next numbersAboveMedian

next medianValue

endif

next usedNumbers

function calculateState(usedNumbers, medianSize, medianValue, numbersAboveMedian)

numbersBelowMedian = usedNumbers - medianSize - numbersAboveMedian)

bottomQTerms = gaussianBinomial(numbersBelowMedian + (medianValue - 1) - 1, numbersBelowMedian)

topQTerms = gaussianBinomial(n - 1 - 2 * numbersAboveMedian, numbersAboveMedian)

for bottomOffset = 0 to length(bottomQTerms) - 1

for topOffset = 0 to length(topQTerms) - 1

partitionSum = bottomOffset + topOffset + numbersBelowMedian + (medianSize * medianValue) + (numbersAboveMedian * (medianValue + 1));

if (partitionSum <= n)

outputMap[partitionSum] += bottomQTerms[bottomOffset] * topQTerms[topOffset]

next topOffset

next bottomOffset

end

where gaussianBinomial(m, n) takes the Gaussian Binomial (m choose n)_q and returns a zero-indexed array where each value in the array is the coefficient of q^index in the Gaussian binomial expansion.

LINKS

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

Joseph Likar, Table of n, a(n) for n = 0..1000

EXAMPLE

The a(2) = 1 through a(9) = 11 partitions:

(11) (111) (22) (2111) (33) (2221) (44) (333)

(1111) (11111) (222) (4111) (2222) (3222)

(3111) (31111) (5111) (6111)

(21111) (211111) (41111) (22221)

(111111) (1111111) (221111) (51111)

(311111) (321111)

(2111111) (411111)

(11111111) (2211111)

(3111111)

(21111111)

(111111111)

MATHEMATICA

wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];

Table[Length[Select[IntegerPartitions[n], Select[Permutations[#], wigQ]=={}&]], {n, 0, 15}]

CROSSREFS

Excluding twins (x,x) gives A344654, complement A344740.

The normal case is A345162, complement A345163.

The complement is counted by A345170, ranked by A345172.

The Heinz numbers of these partitions are A345171.

The version for factorizations is A348380, complement A348379.

A version for ordered factorizations is A348613, complement A348610.

A000041 counts integer partitions.

A001250 counts alternating permutations, complement A348615.

A003242 counts anti-run compositions.

A005649 counts anti-run patterns.

A025047 counts alternating or wiggly compositions.

A325534 counts separable partitions, ranked by A335433.

A325535 counts inseparable partitions, ranked by A335448.

A344604 counts alternating compositions with twins.

A345164 counts alternating permutations of prime indices, w/ twins A344606.

A345192 counts non-alternating compositions, without twins A348377.

Cf. A000070, A025048, A025049, A103919, A335126, A344605, A344607, A344615, A344653, A345166, A345167, A345168, A345169, A347706, A348609.

Sequence in context: A304393 A325535 * A062405 A368180 A071181 A213675

Adjacent sequences: A345162 A345163 A345164 * A345166 A345167 A345168

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jun 12 2021

EXTENSIONS

Terms a(26)-a(1000) by Joseph Likar, Aug 21 2023

STATUS

editing