A089006 -id:A089006 - cp's OEIS frontend

A016121 Number of sequences (a_1, a_2, ..., a_n) of length n with a_1 = 1 satisfying a_i <= a_{i+1} <= 2*a_i.

1, 2, 5, 17, 86, 698, 9551, 226592, 9471845, 705154187, 94285792211, 22807963405043, 10047909839840456, 8110620438438750647, 12062839548612627177590, 33226539134943667506533207, 170288915434579567358828997806, 1630770670148598007261992936663653

Offset: 0

Jeffrey Shallit

nonn

Number of n X n binary symmetric matrices with rows, considered as binary numbers, in nondecreasing order. - R. H. Hardin, May 30 2008

Also, number of (n+1) X (n+1) binary symmetric matrices with zero main diagonal and rows, considered as binary numbers, in nondecreasing order. - Max Alekseyev, Feb 06 2022

Alois P. Heinz, Table of n, a(n) for n = 0..50

Cf. A008934, A060690, A089006, A351157, A351158, A351287, A351288.

Row sums of triangle A097712.

T[n_, k_] := T[n, k] = If[n < 0 || k > n, 0, If[n == k, 1, If[k == 0, 1, T[n - 1, k] + Sum[T[n - 1, j] T[j, k - 1], {j, 0, n - 1}]]]];
a[n_] := Sum[T[n, k], {k, 0, n}];
a /@ Range[0, 20] (* Jean-François Alcover, Oct 02 2019 *)

@CachedFunction
def T(n, k): # T = A097712
    if k<0 or k>n: return 0
    elif k==0 or k==n: return 1
    else: return T(n-1, k) + sum(T(n-1, j)*T(j, k-1) for j in range(n))
def A016121(n): return sum(T(n,k) for k in range(n+1))
[A016121(n) for n in range(31)] # G. C. Greubel, Feb 21 2024

a(n) = Sum_{k=0..n} A097712(n, k). - Paul D. Hanna, Aug 24 2004

Equals the binomial transform of A008934 (number of tournament sequences): a(n) = Sum_{k=0..n} C(n, k)*A008934(k). - Paul D. Hanna, Sep 18 2005

A180985 Array T(n,k) = number of n X k binary matrices with rows and columns in lexicographically nondecreasing order.

Original entry on oeis.org

2, 3, 3, 4, 7, 4, 5, 14, 14, 5, 6, 25, 45, 25, 6, 7, 41, 130, 130, 41, 7, 8, 63, 336, 650, 336, 63, 8, 9, 92, 785, 2942, 2942, 785, 92, 9, 10, 129, 1682, 11819, 24520, 11819, 1682, 129, 10, 11, 175, 3351, 42305, 183010, 183010, 42305, 3351, 175, 11, 12, 231, 6280, 136564

Offset: 1

R. H. Hardin, Sep 30 2010

Differs from "number of inequivalent {0,1}-matrices of size n X k, modulo permutations of rows and columns", A241956, starting at T(2, 3) = 14 while A241956(2, 3) = 13. - M. F. Hasler, Apr 27 2022

			Table starts:
..2...3.....4.......5.........6...........7.............8................9
..3...7....14......25........41..........63............92..............129
..4..14....45.....130.......336.........785..........1682.............3351
..5..25...130.....650......2942.......11819.........42305...........136564
..6..41...336....2942.....24520......183010.......1202234..........6979061
..7..63...785...11819....183010.....2625117......33345183........371484319
..8..92..1682...42305...1202234....33345183.....836488618......18470742266
..9.129..3351..136564...6979061...371484319...18470742266.....818230288201
.10.175..6280..402910..36211867..3651371519..358194085968...31887670171373
.11.231.11176.1099694.170079565.32017940222.6148026957098.1096628939510047
.
All solutions for 3 X 3:
..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..1....0..0..1....0..0..1....0..1..1....0..0..0
..0..0..1....0..1..1....0..1..0....0..0..1....0..1..1....0..1..1....1..1..1
.
..0..0..0....0..0..0....0..0..0....0..0..0....0..0..0....0..0..1....0..0..1
..0..0..1....0..1..1....0..0..1....0..1..1....0..1..1....0..1..0....0..1..0
..1..1..0....1..0..0....1..1..1....1..0..1....1..1..1....0..1..0....0..1..1
.
..0..0..1....0..0..1....0..0..1....0..0..1....0..0..1....0..0..1....0..0..1
..0..0..1....0..0..1....0..0..1....0..1..1....0..1..0....0..1..0....0..1..0
..0..1..0....0..0..1....0..1..1....0..1..1....1..0..0....1..1..0....1..0..1
.
..0..0..1....0..0..1....0..0..1....0..0..1....0..0..1....0..0..1....0..0..1
..0..1..0....0..0..1....0..1..1....0..1..1....0..0..1....0..1..1....0..1..1
..1..1..1....1..1..0....1..0..0....1..1..0....1..1..1....1..0..1....1..1..1
.
..0..0..0....0..0..1....0..0..1....0..0..1....0..1..1....0..1..1....0..1..1
..1..1..1....1..1..0....1..1..0....1..1..1....0..1..1....0..1..1....0..1..1
..1..1..1....1..1..0....1..1..1....1..1..1....0..1..1....1..0..0....1..0..1
...
..0..1..1....0..1..1....0..1..1....0..1..1....0..1..1....0..1..1....0..1..1
..0..1..1....1..0..0....1..0..0....1..0..0....1..0..1....1..0..1....1..0..1
..1..1..1....1..0..0....1..0..1....1..1..1....1..1..0....1..0..1....1..1..1
.
..0..1..1....1..1..1
..1..1..1....1..1..1
..1..1..1....1..1..1

Cf. A089006 (diagonal).
Cf. A004006 (row & column 2), A184138 (row & column 3).
Cf. A241956 (similar but different).

A180985(h,w,cnt=0)={ local(A=matrix(h,w), z(r,c)=!while(r1 && z(r,c), c--); while(c>1, A[r,c--]=0); while(r>1, A[r--,]=A[r+1,]); next(3))); break); cnt} \\ M. F. Hasler, Apr 27 2022

T(n,k) = T(k,n). T(1,k) = k+1. T(2,k) = A004006(k+1). T(3,k) = A184138(k). - M. F. Hasler, Apr 27 2022

A229794 T(n,k)=Number of n X n 0..k arrays with rows and columns in lexicographically nondecreasing order.

Original entry on oeis.org

2, 3, 7, 4, 29, 45, 5, 86, 1169, 650, 6, 205, 14178, 250841, 24520, 7, 421, 102251, 21907055, 318174607, 2625117, 8, 777, 520017, 733861607, 348053502590, 2533164987353, 836488618, 9, 1324, 2066505, 13111482259, 83399309397669

Offset: 1

R. H. Hardin, Sep 29 2013

Table starts
.....2.........3............4..............5................6
.....7........29...........86............205..............421
....45......1169........14178.........102251...........520017
...650....250841.....21907055......733861607......13111482259
.24520.318174607.348053502590.83399309397669.7470491620551006

			Some solutions for n=2 k=4
..1..4....1..3....1..4....0..3....1..4....2..4....1..4....0..3....0..1....0..3
..2..3....3..2....4..0....1..1....2..0....4..2....3..2....2..1....0..1....4..4

R. H. Hardin, Table of n, a(n) for n = 1..63

Column 1 is A089006
Column 2 is A162085
Column 3 is A162086
Column 4 is A162087
Column 5 is A162088
Column 6 is A162089
Column 7 is A162090

Empirical for row n:
n=1: a(n) = 1*n + 1
n=2: a(n) = (1/3)*n^4 + (7/6)*n^3 + (13/6)*n^2 + (7/3)*n + 1
n=3: [polynomial of degree 9]
n=4: [polynomial of degree 16]

A374525 T(n,k) is the number of distinct n X n {0,1}-matrices that reach a fixed point after k alternately applied sorts by rows and columns, where T(n,k), k>=0 is an irregular triangle read by rows.

Original entry on oeis.org

2, 7, 7, 2, 45, 219, 243, 5, 650, 13599, 46385, 4512, 344, 46, 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714, 2625117, 1649029775, 39954292931, 22532640821, 3839779352, 685879134, 49418375, 5578311, 215664, 17256, 836488618

Offset: 1

Hugo Pfoertner at the suggestion of Markus Sigg, Jul 19 2024

It is conjectured that for n>=3 the last term > 0 in row n is T(n,2*n-3). This is consistent with the result of random draws, where T(7,11) is the last term in row 7.

Approximate values of the terms in the next row 7 from random drawings are as follows: 8.4E8, 3.79E12, 2.38E14, 2.54E14, 5.61E13, 1.02E13, 8.22E11, 9.0E10, 4.2E9, 3E8, 9E6, 1E6.

			The triangle begins
   \ k    0        1         2        3       4       5     6    7
  n  -------------------------------------------------------------
  1 |     2,
  2 |     7,       7,        2,
  3 |    45,     219,      243,       5,
  4 |   650,   13599,    46385,    4512,    344,     46,
  5 | 24520, 2542012, 23807149, 6258387, 781647, 132869, 7134, 714
.
  T(2,0) = 7;
  matrices that are already stably sorted, i.e., neither affected
  by sorting by rows nor by sorting by columns:
  [0, 0; 0, 0], [0, 0; 0, 1], [0, 0; 1, 1], [0, 1; 0, 1],
  [0, 1; 1, 0], [0, 1; 1, 1], [1, 1; 1, 1]
.
  T(2,1) = 7; matrices that become stable after one sort:
               sorting by     stable
  [0, 0; 1, 0] columns ->  [0, 0; 0, 1]
  [0, 1; 0, 0] rows    ->  [0, 0; 0, 1]
  [1, 0; 0, 1] rows or ->  [0, 1; 1, 0]
               columns
  [1, 0; 1, 0] columns ->  [0, 1; 0, 1]
  [1, 0; 1, 1] columns ->  [0, 1; 1, 1]
  [1, 1; 0, 0] rows    ->  [0, 0; 1, 1]
  [1, 1; 0, 1] rows    ->  [0, 1; 1, 1]
.
  T(2,2) = 2; matrices needing two sorts to become stable:
         sorting            by     stable
  [1, 0]            [0, 1]         [0, 0]
  [0, 0]            [0, 0]         [0, 1]
         columns ->        rows ->
  [1, 1]            [1, 1]         [0, 1]
  [1, 0]            [0, 1]         [1, 1]

Hugo Pfoertner, PARI program, computes row n.
Markus Sigg, C program, computes row n for A374525 or A374526.

Cf. A002416 (row sums), A089006 (column 0), A374526.

PARI
```
\\ See link.
```

For each n: Sum_{k>=0} T(n,k) = 2^(n^2).

T(n,0) = A089006(n).

a(24)-a(33) (row 6 of triangle) from Markus Sigg, Jul 25 2024

A374526 Similar to A374525, but for each starting matrix with a choice of whether to sort by columns or rows first, such that the total number of sorting steps for this matrix is minimized.

Original entry on oeis.org

2, 7, 7, 2, 45, 254, 212, 1, 650, 19500, 44463, 899, 20, 4, 24520, 4347402, 27123390, 1978573, 72427, 7940, 144, 36, 2625117, 3107244605, 53818094633, 11242079280, 512469215, 35810192, 1002242, 148572, 2304, 576, 836488618

Offset: 1

Markus Sigg and Hugo Pfoertner, Jul 24 2024

This irregular triangle, read by rows, has the same structure as that of A374525, but differs starting from row 3.

			The triangle begins
   \ k    0        1         2        3      4     5    6   7
  n  --------------------------------------------------------
  1 |     2,
  2 |     7,       7,        2,
  3 |    45,     254,      212,       1,
  4 |   650,   19500,    44463,     899,    20,    4,
  5 | 24520, 4347402, 27123390, 1978573, 72427, 7940, 144, 36
.
T(3,3) = 1 because only one ([1,1,0; 1,0,1; 0,1,0]) of the A374525(3,3) = 5 matrices needs 3 sort steps irrespective of the initial sorting direction, whereas the other 4 ([0,1,1; 1,1,0; 0,0,1], [1,0,1; 0,1,1; 1,0,0], [1,0,1; 1,1,0; 0,0,1], [1,1,0; 0,1,1; 1,0,0]) can be sorted in a single step by choosing the "better" direction.
.
                  Sorting by
       Rows     Cols     Rows     Cols stable
  1 1 0    0 1 0    0 0 1    0 0 1    0 0 1
  1 0 1    1 0 1    1 1 0    0 1 1    0 1 1
  0 1 0    1 1 0    0 1 1    1 1 0    1 1 0     3 sort steps needed
                                                for both choices
       Cols     Rows     Cols     Rows stable   of initial sorting
  1 1 0    0 1 1    0 1 0    0 0 1    0 0 1     direction
  1 0 1    1 0 1    0 1 1    0 1 1    0 1 1
  0 1 0    0 1 0    1 0 1    1 1 0    1 1 0
.
       Rows     Cols stable        Cols     Rows     Cols     Rows stable
  0 1 1    0 0 1    0 0 1  |  0 1 1    0 1 1    0 1 0    0 0 1    0 0 1
  1 1 0    0 1 1    0 1 1  |  1 1 0    1 0 1    0 1 1    0 1 1    0 1 1
  0 0 1    1 1 0    1 1 0  |  0 0 1    0 1 0    1 0 1    1 1 0    1 1 0
.
  1 0 1    0 1 1    0 1 1  |  1 0 1    0 1 1    0 1 0    0 0 1    0 0 1
  0 1 1    1 0 0    1 0 0  |  0 1 1    1 0 1    0 1 1    0 1 1    0 1 1
  1 0 0    1 0 1    1 0 1  |  1 0 0    0 1 0    1 0 1    1 1 0    1 1 0
.
  1 0 1    0 0 1    0 0 1  |  1 0 1    0 1 1    0 1 0    0 0 1    0 0 1
  1 1 0    1 0 1    1 0 1  |  1 1 0    1 0 1    0 1 1    0 1 1    0 1 1
  0 0 1    1 1 1    1 1 1  |  0 0 1    0 1 0    1 0 1    1 1 0    1 1 0
.
  1 1 0    0 1 1    0 1 1  |  1 1 0    0 1 1    0 1 0    0 0 1    0 0 1
  0 1 1    1 0 0    1 0 0  |  0 1 1    1 0 1    0 1 1    0 1 1    0 1 1
  1 0 0    1 1 0    1 0 1  |  1 0 0    0 1 0    1 0 1    1 1 0    1 1 0
    1 sort step needed               3 sort steps needed
.
T(4,5)=4, because there are 4 matrices needing 5 sort steps irrespective of the choice of the initial sorting direction.
[1,1,0,1; 1,0,1,1; 0,1,1,0; 1,1,0,0], [1,1,1,0; 1,0,1,1; 0,1,0,1; 1,1,0,0],
[1,1,0,1; 1,0,1,1; 1,1,0,0; 0,1,1,0], [1,1,1,0; 1,0,1,1; 1,1,0,0; 0,1,0,1].
Routes of sorting for the first of these matrices, both with 5 steps:
         Cols       Rows       Cols       Rows       Cols       Rows stable
  1 1 0 1    0 1 1 1    0 1 0 1    0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
  1 0 1 1    1 0 1 1    0 1 1 1    0 1 1 1    0 1 1 1    0 1 1 1    0 1 1 1
  0 1 1 0    1 1 0 0    1 0 1 1    1 1 0 1    1 0 1 0    1 0 0 1    1 0 0 1
  1 1 0 0    0 1 0 1    1 1 0 0    1 0 1 0    1 1 0 1    1 1 1 0    1 1 1 0
or
         Rows       Cols       Rows       Cols       Rows       Cols stable
  1 1 0 1    0 1 1 0    0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
  1 0 1 1    1 0 1 1    1 1 0 1    0 1 1 0    0 1 0 1    0 1 0 1    0 1 0 1
  0 1 1 0    1 1 0 0    0 1 1 0    1 1 0 1    1 1 1 0    1 1 0 1    1 1 0 1
  1 1 0 0    1 1 0 1    1 1 1 0    1 1 1 0    1 1 0 1    1 1 1 0    1 1 1 0

Cf. A002416 (row sums), A089006 (column 0), A374525.

numberOfSortSteps(M, f) = {my(c=0, M1 = if (f == 0, vecsort(M), vecsort(M~)~)); if (M != M1, M = M1; c++); while (1, f = !f; M1 = if (f == 0, vecsort(M), vecsort(M~)~); if (M != M1, M = M1; c++, return(c)))};
minNumberOfSortSteps(M) = min(numberOfSortSteps(M, 0), numberOfSortSteps(M, 1));
a374526(n) = {my(v = vector(n*n), M = matrix(n,n)); while (1, v[minNumberOfSortSteps(M) + 1]++; for (i = 1, n, for (j = 1, n, if (M[i,j]++ == 1, break(2), M[i,j]=0); if (i == n && j == n, break(3))))); select(x->x>0, v)};

T(n,0) = A089006(n).

Sum_{k>=0} T(n,k) = 2^(n^2).

A171699 Square array of number of distinct m X n (0,1) matrices after iterated double sorting, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 14, 14, 5, 1, 1, 6, 25, 45, 25, 6, 1, 1, 7, 41, 130, 130, 41, 7, 1, 1, 8, 63, 336, 650, 336, 63, 8, 1, 1, 9, 92, 785, 2942, 2942, 785, 92, 9, 1, 1, 10, 129, 1682, 11819, 24520, 11819, 1682, 129, 10, 1, 1, 11, 175

Offset: 0

Randy Compton (RANDYRulerOfZexernet(AT)gmail.com), Dec 15 2009

T(m,n) gives the number of distinct results obtained by repeatedly sorting the m X n (0,1) matrices by columns & then rows until reaching a fixed point. Its diagonal is A089006.

			Array begins:
  1,1,1,1,1,...
  1,2,3,4,5,...
  1,3,7,14,25,...
  1,4,14,45,130,...
  1,5,25,130,650,...

Cf. A089006.

-- with the function "t" producing the array.
import List
prod = foldr (\x xs -> [y:ys | y <- x, ys <- xs]) [[]]
f xs = let ys = sort (transpose (sort (transpose xs))) in if xs == ys then xs else f ys
t m n = length $ nub $ map f $ prod (replicate m (prod (replicate n [0,1])))

Corrected & extended by Randy Compton (RANDYRulerOfZexernet(AT)gmail.com), Dec 18 2009

cp's OEIS Frontend

A016121 Number of sequences (a_1, a_2, ..., a_n) of length n with a_1 = 1 satisfying a_i <= a_{i+1} <= 2*a_i.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

SageMath

Formula

A180985 Array T(n,k) = number of n X k binary matrices with rows and columns in lexicographically nondecreasing order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A229794 T(n,k)=Number of n X n 0..k arrays with rows and columns in lexicographically nondecreasing order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A374525 T(n,k) is the number of distinct n X n {0,1}-matrices that reach a fixed point after k alternately applied sorts by rows and columns, where T(n,k), k>=0 is an irregular triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A374526 Similar to A374525, but for each starting matrix with a choice of whether to sort by columns or rows first, such that the total number of sorting steps for this matrix is minimized.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A171699 Square array of number of distinct m X n (0,1) matrices after iterated double sorting, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Haskell

Extensions