OFFSET
1,3
LINKS
Seiichi Manyama, Rows n = 1..30, flattened
EXAMPLE
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;
PROG
(Ruby)
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)}
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Seiichi Manyama, Nov 17 2018
STATUS
approved