Мультиперестановки

[lexus c.]

Сколько всего есть матриц, состоящих только из нулей и единиц, размера n*n, таких, что в каждой строке ровно k единиц и в каждом столбце ровно k единиц? (k<=n). Указать конструктивный способ перебора этих матриц.

[maxal]

См. A008300

Сгенерировать такие матрицы можно, заведя массив сумм в столбцах, изначально равных $k$, и в рекурсивном цикле по строкам генерировать все сочетания столбцов с ненулевыми значениями сумм по $k$, уменьшая значения сумм в столбцах из сочетания на 1.

На PARI/GP примерная программка выглядит так (осуществляется только подсчет):

 { T(n,k) = local(m);
m=vector(n,i,k);
count=0;
genall(m,k);
count 
}

{ genall(m,k) = local(m2,S);
S=select(j->m[j],vector(#m,j,j));
if(#S==0,count++;return);
forvec(v=vector(k,i,[1,#S]),
 m2=m;
 for(j=1,k,
  t=S[v[j]];
  m2[t]--;
 );
 genall(m2,k)
,2)
}

[lexus c.]

maxal писал(а):

См. http://www.research.att.com/~njas/sequences/A008300

Сгенерировать такие матрицы можно, заведя массив сумм в столбцах, изначально равных $k$, и в рекурсивном цикле по строкам генерировать все сочетания столбцов с ненулевыми значениями сумм по $k$, уменьшая значения сумм в столбцах из сочетания на 1.

На PARI/GP примерная программка выглядит так (осуществляется только подсчет):

 { T(n,k) = local(m);
m=vector(n,i,k);
count=0;
genall(m,k);
count 
}

{ genall(m,k) = local(m2,S);
S=select(j->m[j],vector(#m,j,j));
if(#S==0,count++;return);
forvec(v=vector(k,i,[1,#S]),
 m2=m;
 for(j=1,k,
  t=S[v[j]];
  m2[t]--;
 );
 genall(m2,k)
,2)
}

Спасибо.
Что же, получается, нельзя изящно посчитать без использования машины количество таких матриц?

[maxal]

lexus c. в сообщении #173708 писал(а):

Что же, получается, нельзя изящно посчитать без использования машины количество таких матриц?

Смотря, что значит "изящно". Вот, например, цитата из "Advanced Combinatorics" (стр. 235-236) с кое-какими формулами для $k=2$ и $k=3$:

[lexus c.]

maxal писал(а):

lexus c. в сообщении #173708 писал(а):

Что же, получается, нельзя изящно посчитать без использования машины количество таких матриц?

Смотря, что значит "изящно". Вот, например, цитата из "Advanced Combinatorics" (стр. 235-236) с кое-какими формулами для $k=2$ и $k=3$:

Спасибо!