A369559 T(n,k) is the sum of the permanents of all k X k submatrices in the n X n Pascal matrix; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 1, 3, 1, 1, 7, 9, 1, 1, 15, 50, 35, 1, 1, 31, 234, 482, 185, 1, 1, 63, 1016, 5011, 6894, 1267, 1, 1, 127, 4256, 46252, 162724, 150624, 10633, 1, 1, 255, 17509, 403316, 3231672, 8369812, 4900141, 105219, 1, 1, 511, 71349, 3415771, 59157822, 362855438, 696003275, 223813933, 1196889, 1

Offset

0,5

Links

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

Wikipedia, Permanent (mathematics)

Example

T(3,2) = 9:
  The 3 X 3 Pascal matrix
    [1 0 0]
    [1 1 0]
    [1 2 1]
  has nine 2 X 2 submatrices
    [1 0] [1 0] [0 0] [1 0] [1 0] [0 0] [1 1] [1 0] [1 0]
    [1 1] [1 0] [1 0] [1 2] [1 1] [2 1] [1 2] [1 1] [2 1].
  Sum of their permanents is 1 + 0 + 0 + 2 + 1 + 0 + 3 + 1 + 1 = 9.
Triangle T(n,k) begins:
  1;
  1,   1;
  1,   3,     1;
  1,   7,     9,      1;
  1,  15,    50,     35,       1;
  1,  31,   234,    482,     185,       1;
  1,  63,  1016,   5011,    6894,    1267,       1;
  1, 127,  4256,  46252,  162724,  150624,   10633,      1;
  1, 255, 17509, 403316, 3231672, 8369812, 4900141, 105219, 1;
  ...

Maple

with(combinat): with(LinearAlgebra):
T:= proc(n, k) option remember; `if`(k=0 or k=n, 1, (l-> add(add(
      Permanent(SubMatrix(Matrix(n, (i, j)-> binomial(i-1, j-1)),
       i, j)), j in l), i in l))(choose([$1..n], k)))
    end:
seq(seq(T(n, k), k=0..n), n=0..9);

Mathematica

T[n_, k_] := T[n, k] = If[k == 0 || k == n, 1, Module[{l, M},
    l = Subsets[Range[n], {k}];
    M = Table[Binomial[i-1, j-1], {i, n}, {j, n}];
    Total[Permanent /@ Flatten[Table[M[[i, j]], {i, l}, {j, l}], 1]]]];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 29 2024 *)

Crossrefs

Columns k=0-2 give: A000012, A000225, A369906.

Cf. A007318, A184173 (same for determinants).

Sequence in context: A176791 A259471 A220555 * A075440 A137470 A112492

Adjacent sequences: A369556 A369557 A369558 * A369560 A369561 A369562

Keyword

nonn,tabl

Author

Alois P. Heinz, Jan 25 2024

Status

approved