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.

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,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

Row sums: A321688.

Cf. A000041, A000142, A008277.

Sequence in context: A306534 A344392 A331787 * A055925 A276436 A161121

Adjacent sequences: A321683 A321684 A321685 * A321687 A321688 A321689

Keyword

nonn,tabl

Author

Seiichi Manyama, Nov 17 2018

Status

approved