A330942 -id:A330942 - cp's OEIS frontend

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 13, 13, 1, 1, 1, 75, 409, 63, 1, 1, 1, 541, 23917, 16081, 321, 1, 1, 1, 4683, 2244361, 10681263, 699121, 1683, 1, 1, 1, 47293, 308682013, 14638956721, 5552351121, 32193253, 8989, 1, 1, 1, 545835, 58514835289, 35941784497263, 117029959485121, 3147728203035, 1538743249, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 02 2015

Also, A(n,k) is the number of alignments for k sequences of length n each (Slowinski 1998).
Row r > 0 is asymptotic to sqrt(r*Pi) * (r^(r-1)/(r-1)!)^n * n^(r*n+1/2) / (2^(r/2) * exp(r*n) * (log(2))^(r*n+1)), or equivalently to sqrt(r) * (r^(r-1)/(r-1)!)^n * (n!)^r / (2^r * (Pi*n)^((r-1)/2) * (log(2))^(r*n+1)). - Vaclav Kotesovec, Mar 23 2016
From Vaclav Kotesovec, Mar 23 2016: (Start)
Column k > 0 is asymptotic to sqrt(c(k)) * d(k)^n / (Pi*n)^((k-1)/2), where c(k) and d(k) are roots of polynomial equations of degree k, independent on n.
---------------------------------------------------
k               d(k)
---------------------------------------------------
2              5.8284271247461900976033774484193...
3             56.9476283720414911685286267804411...
4            780.2794068067951456595241495989622...
5          13755.2719024115081712083954421541320...
6         296476.9162644200814909862281498491264...
7        7553550.6198338218721069097516499501996...
8      222082591.6017202421029000117685530884167...
9     7400694480.0494436216324852038000444393262...
10  275651917450.6709238286995776605620357737005...
---------------------------------------------------
d(k) is a root of polynomial:
---------------------------------------------------
k=2, 1 - 6*d + d^2
k=3, -1 + 3*d - 57*d^2 + d^3
k=4, 1 - 12*d - 218*d^2 - 780*d^3 + d^4
k=5, -1 + 5*d - 1260*d^2 - 3740*d^3 - 13755*d^4 + d^5
k=6, 1 - 18*d - 5397*d^2 - 123696*d^3 + 321303*d^4 - 296478*d^5 + d^6
k=7, -1 + 7*d - 24031*d^2 - 374521*d^3 - 24850385*d^4 + 17978709*d^5 - 7553553*d^6 + d^7
k=8, 1 - 24*d - 102692*d^2 - 9298344*d^3 + 536208070*d^4 - 7106080680*d^5 - 1688209700*d^6 - 222082584*d^7 + d^8
(End)
d(k) = (2^(1/k) - 1)^(-k). - David Bevan, Apr 07 2022
d(k) is asymptotic to (k/log(2))^k/sqrt(2). - David Bevan, Apr 07 2022
A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with n ones in every column. - Andrew Howroyd, Jan 23 2020

			A(2,2) = 13: [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,0)], [(2,2),(1,2),(1,1),(1,0),(0,0)], [(2,2),(2,1),(1,1),(0,1),(0,0)], [(2,2),(2,1),(1,1),(0,0)], [(2,2),(2,1),(1,1),(1,0),(0,0)], [(2,2),(2,1),(2,0),(0,1),(0,0)], [(2,2),(2,1),(1,0),(0,0)], [(2,2),(1,1),(0,1),(0,0)], [(2,2),(1,1),(0,0)], [(2,2),(1,1),(1,0),(0,0)].
Square array A(n,k) begins:
  1, 1,    1,        1,             1,                   1, ...
  1, 1,    3,       13,            75,                 541, ...
  1, 1,   13,      409,         23917,             2244361, ...
  1, 1,   63,    16081,      10681263,         14638956721, ...
  1, 1,  321,   699121,    5552351121,     117029959485121, ...
  1, 1, 1683, 32193253, 3147728203035, 1050740615666453461, ...

Alois P. Heinz, Antidiagonals n = 0..48, flattened
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Columns: A000012 (k=0 and k=1), A001850 (k=2), A126086 (k=3), A263064 (k=4), A263065 (k=5), A263066 (k=6), A263067 (k=7), A263068 (k=8), A263069 (k=9), A263070 (k=10).
Rows: A000012 (n=0), A000670 (n=1), A055203 (n=2), A062208 (n=3), A062205 (n=4), A263061 (n=5), A263062 (n=6), A062204 (n=7), A263063 (n=8), A263071 (n=9), A263072 (n=10).
Main diagonal: A262810.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A263159, A316674.
Cf. A188392, A330942, A331461, A331637.

A:= (n, k)-> add(add((-1)^i*binomial(j, i)*
     binomial(j-i, n)^k, i=0..j), j=0..k*n):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[, 0] =  1; A[n, k_] := Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, n]^k, {i, 0, j}], {j, 0, k*n}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jul 22 2016, after Alois P. Heinz *)

T(n,k) = {my(m=n*k); sum(j=0, m, binomial(j,n)^k*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))} \\ Andrew Howroyd, Jan 23 2020

A(n,k) = Sum_{j=0..k*n} Sum_{i=0..j} (-1)^i*C(j,i)*C(j-i,n)^k.
A(n,k) = Sum_{i >= 0} binomial(i,n)^k/2^(i+1). - Peter Bala, Jan 30 2018
A(n,k) = Sum_{j=0..n*k} binomial(j,n)^k * Sum_{i=j..n*k} (-1)^(i-j) * binomial(i,j). - Andrew Howroyd, Jan 23 2020

A188392 T(n,k) = number of (n*k) X k binary arrays with rows in nonincreasing order and n ones in every column.

Original entry on oeis.org

1, 2, 1, 5, 3, 1, 15, 16, 4, 1, 52, 139, 39, 5, 1, 203, 1750, 862, 81, 6, 1, 877, 29388, 35775, 4079, 150, 7, 1, 4140, 624889, 2406208, 507549, 15791, 256, 8, 1, 21147, 16255738, 238773109, 127126912, 5442547, 52450, 410, 9, 1, 115975, 504717929, 32867762616

Offset: 1

R. H. Hardin, Mar 30 2011

			Array begins:
========================================================================
n\k| 1  2   3      4         5            6            7               8
---+--------------------------------------------------------------------
1  | 1  2   5     15        52          203           877           4140
2  | 1  3  16    139      1750        29388        624889       16255738
3  | 1  4  39    862     35775      2406208     238773109    32867762616
4  | 1  5  81   4079    507549    127126912   55643064708 38715666455777
5  | 1  6 150  15791   5442547   4762077620 8738543204786
6  | 1  7 256  52450  46757209 135029200594
7  | 1  8 410 154279 335279744
8  | 1  9 625 411180
9  | 1 10 915
     ...
All solutions for 6 X 2
..1..1....1..1....1..0....1..1
..1..1....1..1....1..0....1..0
..1..0....1..1....1..0....1..0
..0..1....0..0....0..1....0..1
..0..0....0..0....0..1....0..1
..0..0....0..0....0..1....0..0

Andrew Howroyd, Table of n, a(n) for n = 1..181 (terms 1..69 from R. H. Hardin)

Rows 1..8 are A000110, A020554, A165434, A165435, A165436, A165437, A188393, A188394.
Columns 3..7 are A011863(n+1), A175707, A188389, A188390, A188391.
Main diagonal gives A188388.
Cf. A188445, A219727, A330942.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); WeighT(v)[n]^k/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k, q=Vec(exp(O(x*x^m) + intformal((x^n-1)/(1-x)))/(1-x))); if(n==0, 1, sum(j=0, m, my(s=0); forpart(p=j, s+=D(p,n,k), [1,n]); s*q[#q-j]))} \\ Andrew Howroyd, Dec 12 2018

A188445 T(n,k) is the number of (n*k) X k binary arrays with nonzero rows in decreasing order and n ones in every column.

Original entry on oeis.org

1, 2, 0, 5, 1, 0, 15, 8, 0, 0, 52, 80, 5, 0, 0, 203, 1088, 205, 1, 0, 0, 877, 19232, 11301, 278, 0, 0, 0, 4140, 424400, 904580, 67198, 205, 0, 0, 0, 21147, 11361786, 101173251, 24537905, 250735, 80, 0, 0, 0, 115975, 361058000, 15207243828, 13744869502

Offset: 1

R. H. Hardin, Mar 31 2011

			Array begins:
============================================================================
n\k| 1 2 3   4       5          6             7              8             9
---+------------------------------------------------------------------------
1  | 1 2 5  15      52        203           877           4140         21147
2  | 0 1 8  80    1088      19232        424400       11361786     361058000
3  | 0 0 5 205   11301     904580     101173251    15207243828 2975725761202
4  | 0 0 1 278   67198   24537905   13744869502 11385203921707 ...
5  | 0 0 0 205  250735  425677958 1184910460297 ...
6  | 0 0 0  80  621348 5064948309 ...
7  | 0 0 0  15 1058139 ...
8  | 0 0 0   1 ...
...
Some solutions for 16 X 4:
  1 1 1 0    1 1 1 1    1 1 1 1    1 1 1 0    1 1 1 1
  1 0 1 1    1 1 0 1    1 1 0 0    1 0 1 1    1 1 0 0
  1 0 1 0    1 0 1 1    1 0 1 1    1 0 0 1    1 0 1 1
  1 0 0 1    1 0 0 0    1 0 0 0    1 0 0 0    1 0 0 0
  0 1 1 1    0 1 1 0    0 1 1 1    0 1 1 0    0 1 1 1
  0 1 0 1    0 1 0 0    0 1 0 0    0 1 0 1    0 1 0 0
  0 1 0 0    0 0 1 1    0 0 1 1    0 1 0 0    0 0 1 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 1 1    0 0 0 1
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
  0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0

Andrew Howroyd, Table of n, a(n) for n = 1..181 (terms 1..69 from R. H. Hardin)

Rows 1..5 are A000110, A002718, A060486, A188446, A188447.
Columns 5..6 are A331127, A331129.
Column sums are A319190.
Cf. A059443, A060487, A188392, A219585, A318361, A330942, A330964, A331039.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); WeighT(v)[n]^k/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, 1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)} \\ Andrew Howroyd, Dec 16 2018

A(n,k) = 0 for n > 2^(k-1). - Andrew Howroyd, Jan 24 2020

A331039 Array read by antidiagonals: A(n,k) is the number of T_0 n-regular set-systems on a k-set.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 5, 0, 0, 1, 0, 1, 43, 5, 0, 0, 1, 0, 1, 518, 175, 1, 0, 0, 1, 0, 1, 8186, 9426, 272, 0, 0, 0, 1, 0, 1, 163356, 751365, 64453, 205, 0, 0, 0, 1, 0, 1, 3988342, 84012191, 23553340, 248685, 80, 0, 0, 0, 1

Offset: 0

Andrew Howroyd, Jan 08 2020

An n-regular set-system is a finite set of nonempty sets in which each element appears in n blocks.
A set-system is T_0 if for every two distinct elements there exists a block containing one but not the other element.
A(n,k) is the number of binary matrices with k distinct columns and any number of distinct nonzero rows with n ones in every column and rows in decreasing lexicographic order.

			Array begins:
==========================================================
n\k | 0 1 2 3   4       5           6                7
----+-----------------------------------------------------
  0 | 1 1 0 0   0       0           0                0 ...
  1 | 1 1 1 1   1       1           1                1 ...
  2 | 1 0 1 5  43     518        8186           163356 ...
  3 | 1 0 0 5 175    9426      751365         84012191 ...
  4 | 1 0 0 1 272   64453    23553340      13241130441 ...
  5 | 1 0 0 0 205  248685   421934358    1176014951129 ...
  6 | 1 0 0 0  80  620548  5055634889   69754280936418 ...
  7 | 1 0 0 0  15 1057989 43402628681 2972156676325398 ...
  ...
The A(2,3) = 5 matrices are:
  [1 1 1]    [1 1 0]    [1 1 0]    [1 0 1]    [1 1 0]
  [1 0 0]    [1 0 1]    [1 0 0]    [1 0 0]    [1 0 1]
  [0 1 0]    [0 1 0]    [0 1 1]    [0 1 1]    [0 1 1]
  [0 0 1]    [0 0 1]    [0 0 1]    [0 1 0]
The corresponding set-systems are:
  {{1,2,3}, {1}, {2}, {3}},
  {{1,2}, {1,3}, {2,3}},
  {{1,2}, {1,3}, {2}, {3}},
  {{1,2}, {1}, {2,3}, {3}},
  {{1,3}, {1}, {2,3}, {2}}.

Andrew Howroyd, Table of n, a(n) for n = 0..209

Rows n=1..4 are A000012, A060053, A060070, A331655.

Cf. A188445, A330942, A330964, A331126, A331160, A331161, A331569, A331654.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); binomial(WeighT(v)[n], k)*k!/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, k<=1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)}

A(n, k) = Sum_{j=1..k} Stirling1(k, j)*A188445(n, j) for n, k >= 1.
A(n, k) = 0 for k >= 1, n > 2^(k-1).
A331654(n) = Sum_{d|n} A(n/d, d).

A331315 Array read by antidiagonals: A(n,k) is the number of nonnegative integer matrices with k columns and any number of nonzero rows with column sums n and columns in nonincreasing lexicographic order.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 14, 4, 1, 1, 8, 150, 128, 8, 1, 1, 16, 2210, 10848, 1288, 16, 1, 1, 32, 41642, 1796408, 933448, 13472, 32, 1, 1, 64, 956878, 491544512, 1852183128, 85862144, 143840, 64, 1, 1, 128, 25955630, 200901557728, 7805700498776, 2098614254048, 8206774496, 1556480, 128, 1

Offset: 0

Andrew Howroyd, Jan 13 2020

The condition that the columns be in nonincreasing order is equivalent to considering nonequivalent matrices up to permutation of columns.

A(n,k) is the number of n-uniform k-block multisets of multisets.

			Array begins:
====================================================================
n\k | 0  1      2          3                4                  5
----+---------------------------------------------------------------
  0 | 1  1      1          1                1                  1 ...
  1 | 1  1      2          4                8                 16 ...
  2 | 1  2     14        150             2210              41642 ...
  3 | 1  4    128      10848          1796408          491544512 ...
  4 | 1  8   1288     933448       1852183128      7805700498776 ...
  5 | 1 16  13472   85862144    2098614254048 140102945876710912 ...
  6 | 1 32 143840 8206774496 2516804131997152 ...
     ...
The A(2,2) = 14 matrices are:
  [1 0]  [1 0]  [1 0]  [2 0]  [1 1]  [1 0]  [1 0]
  [1 0]  [0 1]  [0 1]  [0 1]  [1 0]  [1 1]  [1 0]
  [0 1]  [1 0]  [0 1]  [0 1]  [0 1]  [0 1]  [0 2]
  [0 1]  [0 1]  [1 0]
.
  [1 0]  [1 0]  [2 1]  [2 0]  [1 1]  [1 0]  [2 2]
  [0 2]  [0 1]  [0 1]  [0 2]  [1 1]  [1 2]
  [1 0]  [1 1]

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Rows n=1..2 are A000012, A121227.
Columns k=0..2 are A000012, A011782, A331397.
The version with binary entries is A330942.
The version with distinct columns is A331278.
Other variations considering distinct rows and columns and equivalence under different combinations of permutations of rows and columns are:
All solutions: A316674 (all), A331568 (distinct rows).
Up to row permutation: A219727, A219585, A331161, A331160.
Up to column permutation: this sequence, A331572, A331278, A331570.
Nonisomorphic: A331485.
Cf. A317583.

T(n, k)={my(m=n*k); sum(j=0, m, binomial(binomial(j+n-1, n)+k-1, k)*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))}

A(n,k) = Sum_{j=0..n*k} binomial(binomial(j+n-1,n)+k-1, k) * (Sum_{i=j..n*k} (-1)^(i-j)*binomial(i,j)).
A(n, k) = Sum_{j=0..k} abs(Stirling1(k, j))*A316674(n, j)/k!.
A(n, k) = Sum_{j=0..k} binomial(k-1, k-j)*A331278(n, j).
A(n, k) = A011782(n) * A330942(n, k) for k > 0.
A317583(n) = Sum_{d|n} A(n/d, d).

A331461 Array read by antidiagonals: A(n,k) is the number of nonequivalent binary matrices with k columns and any number of nonzero rows with n ones in every column up to permutation of rows and columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 5, 8, 4, 1, 1, 1, 7, 23, 16, 5, 1, 1, 1, 11, 66, 93, 30, 6, 1, 1, 1, 15, 212, 652, 332, 50, 7, 1, 1, 1, 22, 686, 6369, 6414, 1062, 80, 8, 1, 1, 1, 30, 2389, 79568, 226041, 56712, 3117, 120, 9, 1, 1, 1, 42, 8682, 1256425, 12848128, 7295812, 441881, 8399, 175, 10, 1, 1

Offset: 0

Andrew Howroyd, Jan 18 2020

A(n,k) is the number of non-isomorphic set multipartitions (multiset of sets) with k parts each part has size n.

			Array begins:
===========================================================
n\k | 0 1 2   3    4       5          6              7
----+-----------------------------------------------------
  0 | 1 1 1   1    1       1          1              1 ...
  1 | 1 1 2   3    5       7         11             15 ...
  2 | 1 1 3   8   23      66        212            686 ...
  3 | 1 1 4  16   93     652       6369          79568 ...
  4 | 1 1 5  30  332    6414     226041       12848128 ...
  5 | 1 1 6  50 1062   56712    7295812     1817321457 ...
  6 | 1 1 7  80 3117  441881  195486906   200065951078 ...
  7 | 1 1 8 120 8399 3006771 4298181107 17131523059493 ...
  ...
The A(2,3) = 8 matrices are:
  [1 0 0]  [1 1 0]  [1 1 1]  [1 1 0]  [1 1 0]  [1 1 1]  [1 1 0]  [1 1 1]
  [1 0 0]  [1 0 0]  [1 0 0]  [1 1 0]  [1 0 1]  [1 1 0]  [1 0 1]  [1 1 1]
  [0 1 0]  [0 1 0]  [0 1 0]  [0 0 1]  [0 1 0]  [0 0 1]  [0 1 1]
  [0 1 0]  [0 0 1]  [0 0 1]  [0 0 1]  [0 0 1]
  [0 0 1]  [0 0 1]
  [0 0 1]

Andrew Howroyd, Table of n, a(n) for n = 0..152

Rows n=0..6 are A000012, A000041, A050535, A050913, A058783, A058784, A058785.
Columns k=0..4 are A000012, A000012, A000027(n+1), A002624, A331720.
Cf. A188392, A262809, A304942, A306018, A330942, A331485, A331508, A331509, A331510.

\\ See A304942 for Blocks
T(n,k)={Blocks(k, n*k, n)}
{ for(n=0, 7, for(k=0, 6, print1(T(n,k), ", ")); print) }

A306018(n) = Sum_{d|n} A(n/d, d).

A331508 Array read by antidiagonals: A(n,k) is the number of nonisomorphic T_0 n-regular set multipartitions (multisets of sets) on a k-set.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 5, 3, 1, 1, 0, 1, 11, 12, 4, 1, 1, 0, 1, 26, 66, 25, 5, 1, 1, 0, 1, 68, 445, 278, 44, 6, 1, 1, 0, 1, 177, 4279, 5532, 966, 73, 7, 1, 1, 0, 1, 497, 53340, 200589, 53535, 2957, 112, 8, 1, 1, 0, 1, 1476, 846254, 11662671, 7043925, 431805, 8149, 166, 9, 1, 1

Offset: 0

Andrew Howroyd, Jan 18 2020

An n-regular set multipartition is a finite multiset of nonempty sets in which each element appears in n blocks.
A set multipartition is T_0 if for every two distinct elements there exists a block containing one but not the other element.
A(n,k) is the number of nonequivalent binary matrices with k distinct columns and any number of nonzero rows with n ones in every column up to permutation of rows and columns.
A(n,k) is the number of non-isomorphic set-systems with k parts each of size n.

			Array begins:
===============================================
n\k | 0 1 2  3    4      5       6        7
----+------------------------------------------
  0 | 1 1 0  0    0      0       0        0 ...
  1 | 1 1 1  1    1      1       1        1 ...
  2 | 1 1 2  5   11     26      68      177 ...
  3 | 1 1 3 12   66    445    4279    53340 ...
  4 | 1 1 4 25  278   5532  200589 11662671 ...
  5 | 1 1 5 44  966  53535 7043925 ...
  6 | 1 1 6 73 2957 431805 ...
  ...
The A(2,3) = 5 matrices are:
  [1 0 0]  [1 1 0]  [1 1 1]  [1 1 0]  [1 1 0]
  [1 0 0]  [1 0 0]  [1 0 0]  [1 0 1]  [1 0 1]
  [0 1 0]  [0 1 0]  [0 1 0]  [0 1 0]  [0 1 1]
  [0 1 0]  [0 0 1]  [0 0 1]  [0 0 1]
  [0 0 1]  [0 0 1]
  [0 0 1]

Andrew Howroyd, Table of n, a(n) for n = 0..152 (first 17 antidiagonals)

Rows n=1..6 are A000012, A000664, A058790, A058791, A058792, A058793.

Cf. A283877, A306019, A330942, A331126, A331277, A331461, A331509, A331510.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))[k]}
T(n,k)={my(m=n*k, s=0); if(m==0, k<=1, forpart(q=m, my(g=sum(t=1, k, K(q, t, n)*x^t/t) + O(x*x^k)); s+=permcount(q)*polcoef(exp(g - subst(g,x,x^2)), k)); s/m!)}
{ for(n=0, 6, for(k=0, 5, print1(T(n, k), ", ")); print) } \\ Andrew Howroyd, Jan 16 2024

A306019(n) = Sum_{d|n} A(n/d, d).

A331571 Array read by antidiagonals: A(n,k) is the number of binary matrices with k columns and any number of distinct nonzero rows with n ones in every column and columns in nonincreasing lexicographic order.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 4, 3, 0, 1, 1, 8, 23, 0, 0, 1, 1, 16, 290, 184, 0, 0, 1, 1, 32, 4298, 17488, 840, 0, 0, 1, 1, 64, 79143, 2780752, 771305, 0, 0, 0, 1, 1, 128, 1702923, 689187720, 1496866413, 21770070, 0, 0, 0, 1, 1, 256, 42299820, 236477490418, 5261551562405, 585897733896, 328149360, 0, 0, 0, 1

Offset: 0

Andrew Howroyd, Jan 20 2020

The condition that the columns be in nonincreasing order is equivalent to considering nonequivalent matrices up to permutation of columns.

			Array begins:
===============================================================
n\k | 0 1 2   3         4               5                 6
----+----------------------------------------------------------
  0 | 1 1 1   1         1               1                 1 ...
  1 | 1 1 2   4         8              16                32 ...
  2 | 1 0 3  23       290            4298             79143 ...
  3 | 1 0 0 184     17488         2780752         689187720 ...
  4 | 1 0 0 840    771305      1496866413     5261551562405 ...
  5 | 1 0 0   0  21770070    585897733896 30607728081550686 ...
  6 | 1 0 0   0 328149360 161088785679360 ...
  ...
The A(2,2) = 3 matrices are:
   [1 1]  [1 0]  [1 0]
   [1 0]  [1 1]  [0 1]
   [0 1]  [0 1]  [1 1]

Andrew Howroyd, Table of n, a(n) for n = 0..209

Rows n=0..4 are A000012, A011782, A060090, A060491, A331652.

Cf. A330942, A331567, A331569, A331570, A331572, A331653.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); binomial(WeighT(v)[n] + k - 1, k)/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={ my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))), f=Vec(serlaplace(1/(1+x) + O(x*x^m))/(x-1))); if(n==0, 1, sum(j=1, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*sum(i=j, m, q[i-j+1]*f[i]))); }

A(n, k) = Sum_{j=0..k} abs(Stirling1(k, j))*A331567(n, j)/k!.
A(n, k) = Sum_{j=0..k} binomial(k-1, k-j)*A331569(n, j).
A(n, k) = 0 for k > 0, n > 2^(k-1).
A331653(n) = Sum_{d|n} A(n/d, d).

A331569 Array read by antidiagonals: A(n,k) is the number of binary matrices with k distinct columns and any number of distinct nonzero rows with n ones in every column and columns in decreasing lexicographic order.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 3, 0, 1, 0, 1, 17, 0, 0, 1, 0, 1, 230, 184, 0, 0, 1, 0, 1, 3264, 16936, 840, 0, 0, 1, 0, 1, 60338, 2711904, 768785, 0, 0, 0, 1, 0, 1, 1287062, 675457000, 1493786233, 21770070, 0, 0, 0, 1, 0, 1, 31900620, 232383728378, 5254074934990, 585810653616, 328149360, 0, 0, 0, 1

Offset: 0

Andrew Howroyd, Jan 20 2020

The condition that the columns be in decreasing order is equivalent to considering nonequivalent matrices with distinct columns up to permutation of columns.

A(n,k) is the number of k-block n-uniform T_0 set systems without isolated vertices.

			Array begins:
===============================================================
n\k | 0 1 2   3         4               5                 6
----+----------------------------------------------------------
  0 | 1 1 0   0         0               0                 0 ...
  1 | 1 1 1   1         1               1                 1 ...
  2 | 1 0 3  17       230            3264             60338 ...
  3 | 1 0 0 184     16936         2711904         675457000 ...
  4 | 1 0 0 840    768785      1493786233     5254074934990 ...
  5 | 1 0 0   0  21770070    585810653616 30604798810581906 ...
  6 | 1 0 0   0 328149360 161087473081920 ...
  ...
The A(2,2) = 3 matrices are:
   [1 1]  [1 0]  [1 0]
   [1 0]  [1 1]  [0 1]
   [0 1]  [0 1]  [1 1]

Andrew Howroyd, Table of n, a(n) for n = 0..209

Rows n=1..4 are A000012, A331649, A094631, A331650.

Cf. A330942, A331039, A331567, A331570, A331571, A331572, A331651.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); binomial(WeighT(v)[n], k)/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={ my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))), f=Vec(serlaplace(1/(1+x) + O(x*x^m))/(x-1))); if(n==0, k<=1, sum(j=1, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*sum(i=j, m, q[i-j+1]*f[i]))); }

A(n, k) = Sum_{j=0..k} Stirling1(k, j)*A331567(n, j)/k!.
A(n, k) = Sum_{j=0..k} (-1)^(k-j)*binomial(k-1, k-j)*A331571(n, j).
A331651(n) = Sum_{d|n} A(n/d, d).

A331126 Array read by antidiagonals: A(n,k) is the number of T_0 n-regular set multipartitions (multisets of sets) on a k-set.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 9, 3, 1, 1, 0, 1, 70, 29, 4, 1, 1, 0, 1, 794, 666, 68, 5, 1, 1, 0, 1, 12055, 28344, 3642, 134, 6, 1, 1, 0, 1, 233238, 1935054, 469368, 14951, 237, 7, 1, 1, 0, 1, 5556725, 193926796, 119843417, 5289611, 50985, 388, 8, 1, 1

Offset: 0

Andrew Howroyd, Jan 10 2020

An n-regular set multipartition is a finite multiset of nonempty sets in which each element appears in n blocks.
A set multipartition is T_0 if for every two distinct elements there exists a block containing one but not the other element.
A(n,k) is the number of binary matrices with k distinct columns and any number of nonzero rows with n ones in every column and rows in nonincreasing lexicographic order.

			Array begins:
====================================================================
n\k | 0 1 2   3      4         5             6                 7
----+---------------------------------------------------------------
  0 | 1 1 0   0      0         0             0                 0 ...
  1 | 1 1 1   1      1         1             1                 1 ...
  2 | 1 1 2   9     70       794         12055            233238 ...
  3 | 1 1 3  29    666     28344       1935054         193926796 ...
  4 | 1 1 4  68   3642    469368     119843417       53059346010 ...
  5 | 1 1 5 134  14951   5289611    4681749424     8639480647842 ...
  6 | 1 1 6 237  50985  46241343  134332244907   989821806791367 ...
  7 | 1 1 7 388 151901 333750928 3032595328876 85801167516707734 ...
     ...
The A(2,2) = 2 matrices are:
   [1 1]   [1 0]
   [1 0]   [1 0]
   [0 1]   [0 1]
           [0 1]
The corresponding set multipartitions are:
    {{1,2}, {1}, {2}},
    {{1}, {1}, {2}, {2}}.

Andrew Howroyd, Table of n, a(n) for n = 0..209

Rows n=1..3 are A000012, A014500, A331389.
Columns k=0..3 are A000012, A000012, A001477, A331390.
Cf. A188392, A188445, A330942, A331039, A331160, A331161, A331391.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); binomial(WeighT(v)[n], k)*k!/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k, q=Vec(exp(O(x*x^m) + intformal((x^n-1)/(1-x)))/(1-x))); if(n==0, k<=1, sum(j=0, m, my(s=0); forpart(p=j, s+=D(p, n, k), [1, n]); s*q[#q-j]))}

A(n, k) = Sum_{j=1..k} Stirling1(k, j)*A188392(n, j) for n, k >= 1.

A331391(n) = Sum_{d|n} A(n/d, d).

cp's OEIS Frontend

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A188392 T(n,k) = number of (n*k) X k binary arrays with rows in nonincreasing order and n ones in every column.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A188445 T(n,k) is the number of (n*k) X k binary arrays with nonzero rows in decreasing order and n ones in every column.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A331039 Array read by antidiagonals: A(n,k) is the number of T_0 n-regular set-systems on a k-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A331315 Array read by antidiagonals: A(n,k) is the number of nonnegative integer matrices with k columns and any number of nonzero rows with column sums n and columns in nonincreasing lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A331461 Array read by antidiagonals: A(n,k) is the number of nonequivalent binary matrices with k columns and any number of nonzero rows with n ones in every column up to permutation of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A331508 Array read by antidiagonals: A(n,k) is the number of nonisomorphic T_0 n-regular set multipartitions (multisets of sets) on a k-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A331571 Array read by antidiagonals: A(n,k) is the number of binary matrices with k columns and any number of distinct nonzero rows with n ones in every column and columns in nonincreasing lexicographic order.

Views

Author