|
%I #38 Nov 19 2018 07:18:15
%S 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,
%T 1800,5040,0,2,112,1486,3300,8160,15120,40320,0,1,287,3056,15744,
%U 33960,80640,141120,362880,0,2,448,10012,76776,180000,378000,866880,1451520,3628800
%N 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.
%H Seiichi Manyama, <a href="/A321686/b321686.txt">Rows n = 1..30, flattened</a>
%e In case of n=4.
%e | p_1 1's, p_2 2's, | Arrangements satisfying
%e Partition | ..., p_k k's | the condition
%e ----------+-------------------+---------------------------
%e 4 | 1111 |
%e 3+1 | 1112 |
%e 2+2 | 1122 | 1212, 2121.
%e 2+1+1 | 1123 | 1213, 1231, 2131,
%e | | 1312, 1321, 3121.
%e 1+1+1+1 | 1234 | 1234, 1243, ... (24 terms)
%e So T(4,1) = 0, T(4,2) = 0+2 = 2, T(4,3) = 6, T(4,4) = 24.
%e In case of n=5.
%e | p_1 1's, p_2 2's, | Arrangements satisfying
%e Partition | ..., p_k k's | the condition
%e ----------+-------------------+---------------------------
%e 5 | 11111 |
%e 4+1 | 11112 |
%e 3+2 | 11122 | 12121.
%e 3+1+1 | 11123 | 12131, 13121.
%e 2+2+1 | 11223 | 12123, 12132, 12312,
%e { | 12321, 13212, 31212,
%e | | 21213, 21231, 21321,
%e | | 21312, 23121, 32121.
%e 2+1+1+1 | 11234 | 12134, 12143, ... ( 36 terms)
%e 1+1+1+1+1 | 12345 | 12345, 12354, ... (120 terms)
%e So T(5,1) = 0, T(5,2) = 0+1 = 1, T(5,3) = 2+12 = 14,
%e T(5,4) = 36, T(5,5) = 120.
%e Triangle begins:
%e 1;
%e 0, 2;
%e 0, 1, 6;
%e 0, 2, 6, 24;
%e 0, 1, 14, 36, 120;
%e 0, 2, 40, 108, 240, 720;
%e 0, 1, 59, 348, 900, 1800, 5040;
%e 0, 2, 112, 1486, 3300, 8160, 15120, 40320;
%e 0, 1, 287, 3056, 15744, 33960, 80640, 141120, 362880;
%o (Ruby)
%o def partition(n, min, max)
%o return [[]] if n == 0
%o [max, n].min.downto(min).flat_map{|i| partition(n - i, min, i).map{|rest| [i, *rest]}}
%o end
%o def mul(f_ary, b_ary)
%o s1, s2 = f_ary.size, b_ary.size
%o ary = Array.new(s1 + s2 - 1, 0)
%o (0..s1 - 1).each{|i|
%o (0..s2 - 1).each{|j|
%o ary[i + j] += f_ary[i] * b_ary[j]
%o }
%o }
%o ary
%o end
%o def ncr(n, r)
%o return 1 if r == 0
%o (n - r + 1..n).inject(:*) / (1..r).inject(:*)
%o end
%o def f(n)
%o return 1 if n < 2
%o (1..n).inject(:*)
%o end
%o def A(a)
%o ary = [1]
%o a.each{|i|
%o ary = mul(ary, [0] + (1..i).map{|j| (-1) ** (i - j) * ncr(i - 1, i - j) / f(j).to_r})
%o }
%o (0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
%o end
%o def A321686(n)
%o a = Array.new(n + 1, 0)
%o partition(n, 1, n).each{|ary|
%o a[ary.size] += A(ary)
%o }
%o a[1..-1]
%o end
%o (1..15).each{|i| p A321686(i)}
%Y Row sums: A321688.
%Y Cf. A000041, A000142, A008277.
%K nonn,tabl
%O 1,3
%A _Seiichi Manyama_, Nov 17 2018
|
