A386576
Number of anti-runs of length n covering an initial interval of positive integers with strictly decreasing multiplicities.
Original entry on oeis.org
1, 1, 0, 1, 0, 1, 10, 4, 14, 84, 1136, 967, 3342, 12823, 101762, 1769580
Offset: 0
The a(7) = 4 anti-runs are:
(1,2,1,2,1,2,1)
(1,2,1,2,1,3,1)
(1,2,1,3,1,2,1)
(1,3,1,2,1,2,1)
For any multiplicities we have
A005649.
For weakly instead of strictly decreasing multiplicities we have
A321688.
A005651 counts ordered set partitions with weakly decreasing sizes, strict
A007837.
A032020 counts strict anti-run compositions.
-
seps[ptn_,fir_]:=If[Total[ptn]==1,{{fir}},Join@@Table[Prepend[#,fir]&/@seps[MapAt[#-1&,ptn,fir],nex],{nex,Select[DeleteCases[Range[Length[ptn]],fir],ptn[[#]]>0&]}]];
seps[ptn_]:=If[Total[ptn]==0,{{}},Join@@(seps[ptn,#]&/@Range[Length[ptn]])];
Table[Sum[Length[seps[y]],{y,Select[IntegerPartitions[n],UnsameQ@@#&]}],{n,0,10}]
A321686
Triangle read by rows: T(n,k) is the sum of the number of the arrangements of p_1 1's, p_2 2's, ..., p_k k's (p_1 + p_2 + ... + p_k = n and p_1 >= p_2 >= ... >= p_k) avoiding equal consecutive terms, where 1 <= k <= n.
Original entry on oeis.org
1, 0, 2, 0, 1, 6, 0, 2, 6, 24, 0, 1, 14, 36, 120, 0, 2, 40, 108, 240, 720, 0, 1, 59, 348, 900, 1800, 5040, 0, 2, 112, 1486, 3300, 8160, 15120, 40320, 0, 1, 287, 3056, 15744, 33960, 80640, 141120, 362880, 0, 2, 448, 10012, 76776, 180000, 378000, 866880, 1451520, 3628800
Offset: 1
In case of n=4.
| p_1 1's, p_2 2's, | Arrangements satisfying
Partition | ..., p_k k's | the condition
----------+-------------------+---------------------------
4 | 1111 |
3+1 | 1112 |
2+2 | 1122 | 1212, 2121.
2+1+1 | 1123 | 1213, 1231, 2131,
| | 1312, 1321, 3121.
1+1+1+1 | 1234 | 1234, 1243, ... (24 terms)
So T(4,1) = 0, T(4,2) = 0+2 = 2, T(4,3) = 6, T(4,4) = 24.
In case of n=5.
| p_1 1's, p_2 2's, | Arrangements satisfying
Partition | ..., p_k k's | the condition
----------+-------------------+---------------------------
5 | 11111 |
4+1 | 11112 |
3+2 | 11122 | 12121.
3+1+1 | 11123 | 12131, 13121.
2+2+1 | 11223 | 12123, 12132, 12312,
| | 12321, 13212, 31212,
| | 21213, 21231, 21321,
| | 21312, 23121, 32121.
2+1+1+1 | 11234 | 12134, 12143, ... ( 36 terms)
1+1+1+1+1 | 12345 | 12345, 12354, ... (120 terms)
So T(5,1) = 0, T(5,2) = 0+1 = 1, T(5,3) = 2+12 = 14, T(5,4) = 36, T(5,5) = 120.
Triangle begins:
1;
0, 2;
0, 1, 6;
0, 2, 6, 24;
0, 1, 14, 36, 120;
0, 2, 40, 108, 240, 720;
0, 1, 59, 348, 900, 1800, 5040;
0, 2, 112, 1486, 3300, 8160, 15120, 40320;
0, 1, 287, 3056, 15744, 33960, 80640, 141120, 362880;
-
def partition(n, min, max)
return [[]] if n == 0
[max, n].min.downto(min).flat_map{|i| partition(n - i, min, i).map{|rest| [i, *rest]}}
end
def mul(f_ary, b_ary)
s1, s2 = f_ary.size, b_ary.size
ary = Array.new(s1 + s2 - 1, 0)
(0..s1 - 1).each{|i|
(0..s2 - 1).each{|j|
ary[i + j] += f_ary[i] * b_ary[j]
}
}
ary
end
def ncr(n, r)
return 1 if r == 0
(n - r + 1..n).inject(:*) / (1..r).inject(:*)
end
def f(n)
return 1 if n < 2
(1..n).inject(:*)
end
def A(a)
ary = [1]
a.each{|i|
ary = mul(ary, [0] + (1..i).map{|j| (-1) ** (i - j) * ncr(i - 1, i - j) / f(j).to_r})
}
(0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
end
def A321686(n)
a = Array.new(n + 1, 0)
partition(n, 1, n).each{|ary|
a[ary.size] += A(ary)
}
a[1..-1]
end
(1..15).each{|i| p A321686(i)}
Showing 1-2 of 2 results.
Comments