This site is supported by donations to The OEIS Foundation.

User:Yosu Yurramendi

From OeisWiki
Jump to: navigation, search

Yosu Yurramendi Mendizabal.
Donostia ([1]), Basque Country ([2]), 1955.

BSc in Mathematics, Universidad Complutense de Madrid, 1977.
Ph.D. in Statistics, Université Pierre et Marie Curie, Paris VI, 1984 ([3]).

University of the Basque Country ([4]).
Department of Computing Sciences and Artificial Intelligence ([5]).
Main field of study: Data Analysis.
yosu.yurramendi at ehu.eus

Main contributions to OEIS:



Enumeration systems of positive rationals ( ℚ+ ) based on Stern's sequence ( A002487 )

See 'Index entries for fraction trees' ([6])

A002487 can be represented by blocks of 2m terms (m ≥ 0) in a natural way ([7]).

  • The classes of enumeration systems has been generated by means of a combinatorial procedure by taking into account the blocks, that is to say, block by block (([8])). More classes can be defined.
  • In these enumeration systems every numerator (denominator) is a permuted sequence of A002487, where the permutation is produced at each block of 2m terms.
  • Sequences num+den (= numerator+denominator) are considered. In sequences num+den each integer n > 1 appears phi(n) times (phi, Euler's totient function, A000010)). Sequence built by sums of blocks of num+den is A083329.
  • numerator/num+den and denominator/num+den are enumeration systems of rationals in (0,1).
  • A very desirable property of an enumeration system of ℚ+, further than the existence of a bijection or an one-to-one correspondence with ℕ, is to have some procedures (algorithms) which can specify (as fast as possible) the nature of the underlying bijection:
    • What location corresponds to a given irreducible fraction.
    • And, viceversa, what irreducible fraction corresponds to a given location.
    Same questions can be considered for numerator, denominator, and num+den sequences. For example, a fast algorithm for A002487 has been defined ([9]).


Classification

Class 1

 

                  numerator(n)                        numerator(n) + denominator(n)
∀n > 0    f(n) = --------------             f(n)+1 = -------------------------------
                 denominator(n)                                denominator(n)

Example:

                       f(n)              numerator(n)
Calkin-Wilf:  f(2n) = ------  =  -----------------------------           f(2n+1) = f(n) + 1
                      f(n)+1      numerator(n) + denominator(n)

 

The four systems organized in a table

                 
                 f(2n) =    f(n)/(f(n)+ 1)             1/(f(n)+1)
                          ------------------------------------------
            (f(n)+1)/1    |  Calkin-Wilf              Yurramendi-2 |
f(2n+1) =                 |                                        |
           (f(n)+1)/f(n)  |     Yu-Ting-1                  driB    |
                          ------------------------------------------
                                                       

 

The numerator and denominator of four systems organized in a table

∀n > 0    numerator(2n+1) = denominator(2n) = num+den(n) = numerator(n) + denominator(n)

                 
              denominator(2n+1) =    denominator(n)       numerator(n)
                              ------------------------------------------
                 numerator(n) |       Calkin-Wilf         Yu-Ting-1     |
numerator(2n) =               |                                         |
                denominator(n)|       Yurramendi-2           driB       |
                               ------------------------------------------
                                                                                 

Class 2

                                                                             numerator(2m+k)                      &n bsp;                 numerator(2m+k) + denominator(2m+k)
∀m ≥ 0, ∀k such that 0 ≤ k < 2m    f(2m+k) = ----------------------------             f(2m+k)+1 = -------------------------------------------------------
                                                                            denominator(2m+k)                                                   denominator(2m+k)

Example:

                                               f(2m+k)                          numerator(2m+k)
Stern-Brocot:  f(2m+1+k) = ---------------  =  --------------------------------------------------------                  f(2m+1+2m+k) = f(2m+k) + 1
                                             f(2m+k)+1        numerator(2m+k) + denominator(2m+k)

                 
                                                             f(2m+1+k) =    f(2m+k)/(f(2m+k)+ 1)                    1/(f(2m+k)+1)

                                                                                     ____________________________________________
                             (f(2m+k)+1)/1                               |  Stern-Brocot                                 Yurramendi-1 |
f(2m+1+2m+k) =                                                      |                                                                              |
                            (f(2m+k)+1)/f(2m+k)                    |        HCS                                               Bird         |
                                                                                    _____________________________________________

 

∀m ≥ 0, ∀k such that 0 ≤ k < 2m   numerator(2m+1+2m+k) = denominator(2m+1+k) = num+den(2m+k) = numerator(2m+k) + denominator(2m+k)

 

                                                     denominator(2m+1+2m+k) =    denominator(2m+k)      numerator(2m+k)

                                                                                               ________________________________________
                                   numerator(2m+k)                               |          Stern-Brocot                       HCS         |
numerator(2m+1+k) =                                                          |                                                                      |
                                   denominator(2m+k)                            |          Yurramendi-1                       Bird        |
                                                                                               ________________________________________

 

Permutations

Numerator and denominator of systems are permuted sequences of A002487

Class 1
Class 2

Relationships

    ∘   | A000027 A054429 A258746 A180200 A233279 A165199 A154435 A006068
---------------------------------------------------------------------------
A000027 | A000027 A054429 A258746 A180200 A233279 A165199 A154435 A006068 |
A054429 | A054429 A000027 A165199 A154435 A006068 A258746 A180200 A233279 |
A258746 | A258746 A165199 A000027 A233279 A180200 A054429 A006068 A154435 |
A180200 | A180200 A006068    a       b       c       m       n       o    |
A233279 | A233279 A154435    d       e       f       p       q       r    |
A165199 | A165199 A258746 A054429 A006068 A154435 A000027 A233279 A180200 |
A154435 | A154435 A233279    p       q       r       d       e       f    |
A006068 | A006068 A180200    m       n       o       a       b       c    |
        -------------------------------------------------------------------

a <- A180200[A258746], b <- A180200[A180200], c <- A180200[A233279]
d <- A233279[A258746], e <- A233279[A180200], f <- A233279[A233279]
m <- A180200[A165199], n <- A180200[A154435], o <- A180200[A006068]
p <- A233279[A165199], q <- A233279[A154435], r <- A233279[A006068]

Permutations between numerator and denominator of systems

σ1 = A000027, the positive integers (identity permutation).
τ0 = A054429, the inverse permutation by blocks of 2m terms.
τ1 = A063946, τ2 = A065190.

  • τ0τ0 = σ1.
    ({σ1, τ0}, ∘) is a cyclic group (C2, [17]).
  • τ1τ1 = τ2τ2 = σ1.
    τ0τ1 = τ1τ0 = A117120, τ0τ2 = τ2τ0 = A092569.
    ({σ1, τ0, τ1, τ0τ1}, ∘) is a Klein 4-group (C2xC2, [18]), and so is ({σ1, τ0, τ2, τ0τ2}, ∘).
  • τ1τ2 = τ2τ1.
    ({σ1, τ0, τ1, τ2, τ0τ1, τ0τ2, τ1τ2, τ0τ1τ2}, ∘) is an elementary abelian group of order 23 (C2xC2xC2, [19]).
Class 1
Class 2


Permutations between systems

Between classes
Between Class 1 and Class 2

σ1 = A000027, the positive integers (identity permutation).
σ0 = A059893, the bit-reversal permutation by blocks of 2m terms.

Within classes

Structure of permutation system is the same in both classes.

Class 1/Class 2
From                To
Stern-Brocot/Calkin-Wilf
Bird/driB
HCS/Yu-Ting
Yurramendi-1/2
Stern-Brocot/Calkin-Wilf
σ1
σ2
σ3
σ4
Bird/driB
σ2
σ1
σ4
σ3
HCS/Yu-Ting
σ3'
σ4'
σ1
σ2'
Yurramendi-1/2
σ4'
σ3'
σ2'
σ1

σ1 = A000027

  • σ2σ2 = σ'2σ'2 = σ1
    σ2σ'2 = σ'2σ2
    ({σ1, σ2, σ'2, σ2σ'2}, ∘) is a Klein 4-group (C2xC2).
  • σ3σ'3 = σ'3σ3 = σ1
    σ4σ'4 = σ'4σ4 = σ1
Within Class 1

σ2=A258996, σ'2=A092569, σ2σ'2 = A284447,
σ3=A231551, σ'3=A231550,
σ4=A284459, σ'4=A284460.

Within Class 2

σ2=A258746, σ'2=A117120, σ2σ'2 = A284120,
σ3=A233279, σ'3=A233280,
σ4=A180200, σ'4=A180201.

Some other relationships between permutations

σ1 = A000027,
τ0 = A054429, σ0 = A059893,
τ1 = A063946, τ2 = A065190,
σ2-1 = A258996, σ'2-1 = A092569, σ2-2 = A258746, σ'2-2 = A117120 .

  • σ0τ0 = τ0σ0 = A059894,
    ({σ1, σ0, τ0, σ0τ0}, ∘) is a Klein 4-group
  • σ2-1τ0 = τ0σ2-1,          σ2-1τ1 = τ1σ2-1,         σ2-1τ2 = τ2σ2-1
    σ'2-1τ0 = τ0σ'2-1 = τ2,       σ'2-1τ1 = τ1σ'2-1,         σ'2-1τ2 = τ2σ'2-1 = τ0
    ({σ1, τ0, τ1, τ2, σ0, σ2-1, σ'2-1, ...(*), τ0τ1τ2σ0σ2-1σ'2-1}, ∘) is also an elementary abelian group of order 26.
  • σ2-2τ0 = τ0σ2-2 = A165199,    σ2-2τ1 = τ1σ2-2,         σ2-2τ2 = τ2σ2-2
    σ'2-2τ0 = τ0σ'2-2 = τ1,       σ'2-2τ1 = τ1σ'2-2 = τ0,      σ'2-2τ2 = τ2σ'2-2
    ({σ1, τ0, τ1, τ2, σ0, σ2-2, σ'2-2, ...(*), τ0τ1τ2σ0σ2-2σ'2-2}, ∘) is an elementary abelian group of order 26, where (*) expresses all the k-combinations (1<k<6) from the set of 6 basic permutations ({τ0, τ1, τ2, σ0, σ2-2, σ'2-2}; all except σ1).
  • σ2-1σ2-2 = σ2-2σ2-1,        σ2-2σ'2-1 = σ'2-1σ2-2
    σ'2-1σ2-2 = σ2-2σ'2-1,       σ'2-2σ'2-1 = σ'2-1σ'2-2
    ({σ1, τ0, τ1, τ2, σ0, σ2-2, σ'2-2, σ2-1, σ'2-1, ...(*), σ1τ0τ1τ2σ0σ2-2σ'2-2σ2-1σ'2-1}, ∘) is an elementary abelian group of order 28.
  • σ4-2σ3-2 = A064707       σ'3-2σ'4-2 = A064706


Number of binary pattern classes in the (m,n)-rectangular grid with k '1's and (mn-k) '0's

Two binary patterns are in same class if one of them can be obtained by a reflection or 180-degree rotation .
A034851 : (1,n,k) triangle is the Losanitsch's triangle .
A226048 : (2,n,k) triangle .
A226290 : (3,n,k) triangle .
A225812 : (4,n,k) triangle (with María Merino).
A228022 : (5,n,k) triangle (with María Merino).
A228165 : (6,n,k) triangle (with María Merino).
A228166 : (7,n,k) triangle (with María Merino).
A228167 : (8,n,k) triangle (with María Merino).
A228168 : (9,n,k) triangle (with María Merino).
A228169 : (10,n,k) triangle (with María Merino).

A225826 to A225834 : (m,n) sequences, 1 < m < 11 (one by one).
A225910 : (m,n) table, 1 < m < 11 ((m,n) sequences all together).

YURRAMENDI MENDIZABAL Y. 2013. "Matematika esperimentalaren adibide bat: Lauki sareko patroi bitarren kopuruaren kalkulua", EKAIA, 26, 325-348] ([20]).
MERINO MAESTRE M., YURRAMENDI MENDIZABAL Y. 2014. "Lauki sareko patroi bitarren kalkulua, oinarrizko konbinatoriaren eskutik" EKAIA, 27, 237-262 ([21]).