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

Author

Alois P. Heinz, Jan 25 2024

Keywords

• nonn
• tabl

Examples

			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;
  ...
		

Links

• Wikipedia, Permanent (mathematics)

Crossrefs

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

Cf. A007318, A184173 (same for determinants).

Programs

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 *)