A240909 -id:A240909 - cp's OEIS frontend

A131271 Triangular array T(n,k), n>=0, k=1..2^n, read by rows in bracketed pairs such that highest ranked element is bracketed with lowest ranked.

1, 1, 2, 1, 4, 2, 3, 1, 8, 4, 5, 2, 7, 3, 6, 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11, 1, 32, 16, 17, 8, 25, 9, 24, 4, 29, 13, 20, 5, 28, 12, 21, 2, 31, 15, 18, 7, 26, 10, 23, 3, 30, 14, 19, 6, 27, 11, 22, 1, 64, 32, 33, 16, 49, 17, 48, 8, 57

Offset: 0

J. Demongeot (Jacques.Demongeot(AT)imag.fr), Jun 24 2007

In a knockout competition with 2^n players, arranging the competition brackets (see Wikipedia) in T(n,k) order, where T(n,k) is the rank of the k-th player, ensures that highest ranked players cannot meet until the later stages of the competition. None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition. At the same time the top ranked players in each match meet the lowest ranked player possible consistent with this rule. The sequence for the top ranked players meeting the highest ranked player possible is A049773. - Colin Hall, Feb 28 2012
Ranks in natural order of 2^n increasing real numbers appearing in limit cycles of interval iterations, or Median Spiral Order. [See the works by Demongeot & Waku]
From Andrey Zabolotskiy, Dec 06 2024 (Start):
For n>0, row n-1 is the permutation relating row n of Kepler's tree of fractions with row n of the left half of Stern-Brocot tree. Specifically, if K_n(k) [resp. SB_n(k)] is the k-th fraction in the n-th row of A294442 [resp. A057432], where 1/2 is in row 1 and k=1..2^(n-1), then K_n(k) = SB_n(T(n-1, k)).
The inverse permutation is row n of A088208.
When 1 is subtracted from each term, rows 3-5 become A240908, A240909, A240910. (End)

			Triangle begins:
1;
1,  2;
1,  4, 2, 3;
1,  8, 4, 5, 2,  7, 3,  6;
1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11;
...

Alois P. Heinz, Table of n, a(n) for n = 0..8190
John M. Campbell, A generalization of Deterministic Finite Automata related to discharging, arXiv:2506.14072 [cs.FL], 2025. See p. 7.
Jacques Demongeot and Jules Waku, Counter-Examples about Lower- and Upper-Bounded Population Growth, Math. Pop. Studies 12 (2005), 199-210.
Jacques Demongeot and Jules Waku, Application of interval iterations to the entrainment problem in respiratory physiology, Phil. Trans. R. Soc. A, 367 (2009), 4717-4739.
Wikipedia, Bracket (tournament)

Cf. A049773, A088208, A294442, A057432.
Cf. A005578 (last elements in rows), A155944 (T(n,2^(n-1)) for n>0).
Cf. A006519, A240908, A240909, A240910.

T:= proc(n,k) option remember;
      `if`({n, k} = {1}, 1,
      `if`(irem(k, 2)=1, T(n-1, (k+1)/2), 2^(n-1)+1 -T(n-1, k/2)))
    end:
seq(seq(T(n, k), k=1..2^(n-1)), n=1..7); # Alois P. Heinz, Feb 28 2012, with offset 1

T[0, 1] = 1;
T[n_, k_] := T[n, k] = If[Mod[k, 2] == 1, T[n, (k + 1)/2], 2^n + 1 - T[n, k/2]];
Table[T[n, k], {n, 0, 6}, {k, 2^n}] // Flatten (* Jean-François Alcover, May 31 2018, after Alois P. Heinz *)

T(0,1) = 1, T(n,2k-1) = T(n-1,k), T(n,2k) = 2^n+1 - T(n-1,k).

T(n,1) = 1; for 1 < k <= 2^n, T(n,k) = 1 + (2^n)/m - T(n,k-m), where m = A006519(k-1). - Mathew Englander, Jun 20 2021

Edited (with new name from Colin Hall) by Andrey Zabolotskiy, Dec 06 2024

A240908 The sequency numbers of the 8 rows of a version of the Hadamard-Walsh matrix of order 8.

Original entry on oeis.org

0, 7, 3, 4, 1, 6, 2, 5

Offset: 1

Ross Drewe, Apr 14 2014

The Hadamard (Hadamard-Walsh) matrix is widely used in telecommunications and signal analysis. It has 3 well-known forms which vary according to the sequency ordering of its rows: "natural" ordering, "dyadic" or Payley ordering, and sequency ordering. In a mathematical context the sequency is the number of zero crossings or transitions in a matrix row (although in a physical signal context, it is half the number of zero crossings per time period). The matrix row sequencies are a permutation of the set [0,1,2,...n-1], where n is the order of the matrix. For spectral analysis of signals the sequency-ordered form is needed. Unlike the dyadic ordering (given by A153141), the natural ordering requires a separate list for each matrix order. This sequence is the natural sequency ordering for an order 8 matrix.

			This is a fixed length sequence of only 8 values, as given.

N. J. A. Sloane, A Library of Hadamard Matrices
Eric Weisstein's World of Mathematics, Hadamard Matrix
Wikipedia, Walsh matrix

Cf. A240909 "natural order" sequencies for Hadamard-Walsh matrix, order 16.
Cf. A240910 "natural order" sequencies for Hadamard-Walsh matrix, order 32.
Cf. A153141 "dyadic order" sequencies for Hadamard-Walsh matrix, all orders.
Cf. A000975(n) is sequency of last row of H(n). - William P. Orrick, Jun 28 2015

Recursion: H(2)=[1 1; 1 -1]; H(n) = H(n-1)*H(2), where * is Kronecker matrix product.

Definition of H(n) corrected by William P. Orrick, Jun 28 2015

A240910 The sequency numbers of the 32 rows of a Hadamard-Walsh matrix, order 32.

Original entry on oeis.org

0, 31, 15, 16, 7, 24, 8, 23, 3, 28, 12, 19, 4, 27, 11, 20, 1, 30, 14, 17, 6, 25, 9, 22, 2, 29, 13, 18, 5, 26, 10, 21

Offset: 1

Ross Drewe, Apr 14 2014

See A240908 for context. This sequence is the natural sequency ordering for an order 32 matrix.

			This is a fixed length sequence of only 32 values, as given in full above.

N. J. A. Sloane, A Library of Hadamard Matrices
Eric Weisstein's World of Mathematics, Hadamard Matrix
Wikipedia, Walsh matrix

Cf. A240908 "natural order" sequencies for Hadamard-Walsh matrix, order 8.
Cf. A240909 "natural order" sequencies for Hadamard-Walsh matrix, order 16.
Cf. A153141 "dyadic order" sequencies for Hadamard-Walsh matrix, all orders.
Cf. A000975(n) is sequency of last row of H(n). - William P. Orrick, Jun 28 2015

Recursion: H(2) = [1 1; 1 -1]; H(n) = H(n-1) * H(2), where * is the Kronecker matrix product.

Definition of H(n) corrected by William P. Orrick, Jun 28 2015

A259363 Number of distinct elements in the Gram matrix of the first M rows of the Kronecker product (Sylvester) Hadamard matrix.

Original entry on oeis.org

0, 1, 2, 3, 2, 4, 4, 3, 2, 4, 5, 6, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 5, 8, 9, 10, 9, 12, 11, 10, 7, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 6, 9, 10, 11, 8, 9, 8, 7, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9

Offset: 0

William P. Orrick, Jun 24 2015

Let H(2) = [1, 1; 1, -1]; let H(2^(n+1)) be the Kronecker product of H(2^n) and H(2). For M less than or equal to 2^n, let A(2^n,M) be the submatrix of H(2^n) consisting of its first M rows, and let G(2^n,M)=(A(2^n,M))'A(2^n,M). Then a(M) is the number of distinct elements of G(2^n,M), which depends only on M.

			H(4)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1;1,-1,-1,1], A(4,3)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1], G(4,3)=[3,1,1,-1;1,3,-1,1;1,-1,3,1;-1,1,1,3]. Since G(4,3) has 3 distinct elements, a(3)=3.

Math Stackexchange, Relation between number of unique values in Gramian Matrix (G) and the matrices that created it

Cf. A000975, A240908, A240909, A240910.

mToWord[m_] := Module[{binary, sbin, lst, j},
  binary = IntegerDigits[m, 2];
  sbin = Split[binary];
  lst = {};
  For[j = 1, j <= Length[sbin], j++,
   If[sbin[[j, 1]] == 1 && Length[sbin[[j]]] > 1, AppendTo[lst, 11]];
   If[sbin[[j]] == {1}, AppendTo[lst, 1]];
   If[sbin[[j, 1]] == 0, AppendTo[lst, 0]]
   ];
  lst
  ]
s[{1}]=1
s[{1,0}]=2
s[w_] := Module[{b, newW, a, c},
  If[w[[1]] == 11,
   b = 1,
   b = 0
   ];
  If[w[[-1]] != 0,
   newW = Append[w, 0];
   a = -1,
   newW = w;
   a = 0
   ];
  If[newW[[-2]] == 1,
   c = -3,
   If[newW[[-2]] == 11,
    c = -1
    ]
   ];
  a + b + c + 2 Length[newW]
  ]
numberDistinctGramValues[m_]:=If[m==0,0,s[mToWord[m]]]

Recurrence for M>0: let b be the base-2 representation of M. Map b to a word w on the alphabet {1,I,O} by splitting b into runs of 0's and 1's and letting O represent a string of one or more 0's, I a string of two or more 1's, and 1 an isolated 1. Then a(0)=0, a(n)=s(w), where s(1)=1, s(1O1)=4, s(uO)=s(u)+1, s(vI)=s(v1)+2, s(vIO1)=s(v1)+4, s(v1O1)=s(v1)+4, where u is a nonempty word and v is an arbitrary word.
Closed form: s(1)=1, s(1O)=2, s(w)=4[(|w|+1)/2]+a(w)+b(w)+c(w), where |w| is the length of w, [x] is the greatest integer function, and a, b, c are defined by a(w)=0 if w ends in O, -1 if w ends in 1 or I; b(w)=1 if first letter of w is I, 0 if first letter of w is 1; c(w)=-1 if last non-O letter of w is I, -3 if last non-O letter of w is 1.
Equivalently, for n > 1, a(n) = 4*A069010(n) - A000035(n) + A079944(n-2) + 4 - A099545(n-1) + A036987(n-1).

cp's OEIS Frontend

A131271 Triangular array T(n,k), n>=0, k=1..2^n, read by rows in bracketed pairs such that highest ranked element is bracketed with lowest ranked.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A240908 The sequency numbers of the 8 rows of a version of the Hadamard-Walsh matrix of order 8.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A240910 The sequency numbers of the 32 rows of a Hadamard-Walsh matrix, order 32.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A259363 Number of distinct elements in the Gram matrix of the first M rows of the Kronecker product (Sylvester) Hadamard matrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula