Dan Dima - cp's OEIS frontend

User: Dan Dima

Dan Dima has authored 6 sequences.

A306556 Integers that appear as (unreduced) numerators of segment endpoints when a ternary Cantor set is created.

0, 1, 2, 3, 6, 7, 8, 9, 18, 19, 20, 21, 24, 25, 26, 27, 54, 55, 56, 57, 60, 61, 62, 63, 72, 73, 74, 75, 78, 79, 80, 81, 162, 163, 164, 165, 168, 169, 170, 171, 180, 181, 182, 183, 186, 187, 188, 189, 216, 217, 218, 219, 222, 223, 224, 225, 234, 235, 236, 237, 240, 241, 242, 243

Offset: 1

Dan Dima, Feb 23 2019

Nonnegative integers whose ternary representation contains only digits 0 and 2 except for at most a single digit 1 that is followed only by 0's.
Nonnegative integers that can be written in base 3 using only 0's and 2's, allowing the use of the "decimal" point (.) and replacing ....10..0(.) by ....02..2(.)2222...
Note that fractions are not reduced.
List of integers in the closure of the ternary Cantor set under multiplication by 3. The closure is the union of the translated ternary Cantor sets spanning [a(1), a(2)], [a(3), a(4)], [a(5), a(6)], ... . - Peter Munn, Jul 09 2019

			On 1st step we have [0,1/3] U [2/3,3/3] so we get a(1)=0, a(2)=1, a(3)=2, a(4)=3.
On 2nd step we have [0,1/9] U [2/9,3/9] U [6/9,7/9] U [8/9,9/9] so we get in addition a(5)=6, a(6)=7, a(7)=8, a(8)=9.

Georg Cantor, Über unendliche, lineare Punktmannigfaltigkeiten V" [On infinite, linear point-manifolds (sets), Part 5]. Mathematische Annalen (in German). (1883) 21: 545-591.
Paul du Bois-Reymond, Der Beweis des Fundamentalsatzes der Integralrechnung, Mathematische Annalen (in German), (1880), 16, footnote on p. 128.
Eric Weisstein's World of Mathematics, Cantor Set
Wikipedia, Cantor set
Index entries for 3-automatic sequences.

Cf. A005823, A054591, A055247, A191106, A191108.

A306556(n) = {sm=0;while(n>1,ex=floor(log(n)/log(2));if(n-2^ex==0,sm=sm+3^(ex-1),sm=sm+2*3^(ex-1));n=n-2^ex);return(sm)}

a(n) = n--; fromdigits(binary(n>>1),3)*2 + (n%2); \\ Kevin Ryde, Apr 23 2021

a(1)=0, a(2)=1;
a(2^n) = 3^(n-1) for n >= 1;
a(2^n+k) = 2*3^(n-1) + a(k) for 1 <= k <= 2^n.
From Peter Munn, Jul 09 2019: (Start)
a(2n-1) = A005823(n) = A191106(n)-1.
a(2n)   = A191106(n) = A005823(n)+1.
a(2n-1) = (A055247(2n-1)-1)/3.
a(2n)   = (A055247(2n)  +1)/3.
a(2n-1) = (A191108(n)-1)/2.
a(2n)   = (A191108(n)+1)/2.
(End)

A189722 Number of self-avoiding walks of length n on square lattice such that at each point the angle turns 90 degrees (the first turn is assumed to be to the left - otherwise the number must be doubled).

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, 226, 362, 580, 921, 1468, 2344, 3740, 5922, 9413, 14978, 23829, 37686, 59770, 94882, 150606, 237947, 376784, 597063, 946086, 1493497, 2361970, 3737699, 5914635, 9330438, 14741315, 23301716, 36833270, 58071568

Offset: 2

Dan Dima and Stephen C. Locke, Apr 25-26 2011

The number of snakes composed of n identical segments such that the snake starts with a left turn and the other (n-2) joints are bent at 90-degree angles, either to the left or to the right, in such a way that the snake does not overlap.

Vi Hart came up with this idea of snakes (see the link below).

			For n=2 the a(2)=1 there is only one snake:
(0,0), (0,1), (-1,1).
For n=3 the a(3)=2 there are two snakes:
(0,0), (0,1), (-1,1), (-1,0);
(0,0), (0,1), (-1,1), (-1,2).
Representing the walk (or snake) as a sequence of turns I and -I in the complex plane, with the initial condition that the first turn is I, for length 2 we have [I], for length 3 we have [I,I], [I,-I], and for length 4 we have [I,I,-I], [I,-I,I], [I,-I,-I].

Vaclav Kotesovec, Table of n, a(n) for n = 2..50
Vi Hart, How To Snakes [Broken link?]
Vi Hart, How to snakes, YouTube, March 2011.
IBM Corp., Ponder This, April 2011.

ValidSnake:=proc(P) local S, visited, lastdir, lastpoint, j;
S:={0, 1}; lastdir:=1; lastpoint:=1;
for j from 1 to nops(P) do  lastdir:=lastdir*P[j];
  lastpoint:=lastpoint+lastdir;
  S:=S union {lastpoint};
od;
if (nops(S) = (2+nops(P))) then return(true); else return(false); fi;
end;
NextList:=proc(L) local S, snake, newsnake;
S:={ };
for snake in L do
  newsnake:=[op(snake), I];
  if ValidSnake(newsnake) then S:=S union {newsnake}; fi;
  newsnake:=[op(snake), -I];
  if ValidSnake(newsnake) then S:=S union {newsnake}; fi;
od;
return(S union { });
end;
L:={[I]}:
for k from 3 to 25 do
  L:=NextList(L):
  print(k, nops(L));
od:
# second Maple program:
a:= proc(n) local v, b;
      v:= proc() true end: v(0, 0), v(0, 1):= false$2:
      b:= proc(n, x, y, d) local c;
            if v(x, y) then v(x, y):= false;
               c:= `if`(n=0, 1,
                   `if`(d=1, b(n-1, x, y+1, 2) +b(n-1, x, y-1, 2),
                             b(n-1, x+1, y, 1) +b(n-1, x-1, y, 1) ));
               v(x, y):= true; c
            else 0 fi
          end;
      b(n-2, -1, 1, 1)
    end:
seq(a(n), n=2..25);  # Alois P. Heinz, Jun 10 2011

a[n_] := Module[{v, b}, v[, ] = True; v[0, 0] = v[0, 1] = False; b[m_, x_, y_, d_] := Module[{c}, If[v[x, y], v[x, y] = False; c = If[m == 0, 1, If[d == 1, b[m-1, x, y+1, 2] + b[m-1, x, y-1, 2], b[m-1, x+1, y, 1] + b[m-1, x-1, y, 1]]]; v[x, y] = True; c, 0]]; b[n-2, -1, 1, 1]]; Table[ a[n], {n, 2, 25}] (* Jean-François Alcover, Nov 07 2015, after Alois P. Heinz *)

a(33)-a(40) from Alois P. Heinz, Jun 10 2011

A126074 Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 9, 8, 6, 1, 25, 40, 30, 24, 1, 75, 200, 180, 144, 120, 1, 231, 980, 1260, 1008, 840, 720, 1, 763, 5152, 8820, 8064, 6720, 5760, 5040, 1, 2619, 28448, 61236, 72576, 60480, 51840, 45360, 40320, 1, 9495, 162080, 461160, 653184, 604800, 518400, 453600, 403200, 362880

Offset: 1

Dan Dima, Mar 01 2007

Sum of the n-th row is the number of all permutations of n elements: Sum_{k=1..n, T(n,k)} = n! = A000142(n) We can extend T(n,k)=0, if k<=0 or k>n.
From Peter Luschny, Mar 07 2009: (Start)
Partition product of prod_{j=0..n-2}(k-n+j+2) and n! at k = -1, summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A102189.
Same partition product with length statistic is A008275.
Diagonal a(A000217(n)) = rising_factorial(1,n-1), A000142(n-1) (n > 0).
Row sum is A000142. (End)
Let k in {1,2,3,...} index the family of sequences A000012, A000085, A057693, A070945, A070946, A070947, ... respectively. Column k is the k-th sequence minus its immediate predecessor. For example, T(5,3)=A057693(5)-A000085(5). - Geoffrey Critzer, May 23 2009

			Triangle T(n,k) begins:
  1;
  1,   1;
  1,   3,    2;
  1,   9,    8,    6;
  1,  25,   40,   30,   24;
  1,  75,  200,  180,  144,  120;
  1, 231,  980, 1260, 1008,  840,  720;
  1, 763, 5152, 8820, 8064, 6720, 5760, 5040;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
S. W. Golomb and P. Gaal, On the number of permutations of n objects with greatest cycle length k, Adv. in Appl. Math., 20(1), 1998, 98-107.
IBM Research, Ponder This, December 2006.
Peter Luschny, Counting with Partitions. [From _Peter Luschny_, Mar 07 2009]
Peter Luschny, Generalized Stirling_1 Triangles. [From _Peter Luschny_, Mar 07 2009]
D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.

Cf. A000142.
Cf. A071007, A080510, A028418.
Cf. A157386, A157385, A157384, A157383, A157400, A157391, A157392, A157393, A157394, A157395. - Peter Luschny, Mar 07 2009
T(2n,n) gives A052145 (for n>0). - Alois P. Heinz, Apr 21 2017

A:= proc(n,k) option remember; `if`(n<0, 0, `if`(n=0, 1,
       add(mul(n-i, i=1..j-1)*A(n-j,k), j=1..k)))
    end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n,k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 11 2013

Table[CoefficientList[ Series[(Exp[x^m/m] - 1) Exp[Sum[x^k/k, {k, 1, m - 1}]], {x, 0, 8}], x]*Table[n!, {n, 0, 8}], {m, 1, 8}] // Transpose // Grid (* Geoffrey Critzer, May 23 2009 *)

def A126074(n, k):
    f = factorial(n)
    P = Partitions(n, max_part=k, inner=[k])
    return sum(f // p.aut() for p in P)
for n in (1..9): print([A126074(n,k) for k in (1..n)]) # Peter Luschny, Apr 17 2016

T(n,1) = 1.
T(n,2) = n! * Sum_{k=1..[n/2]} 1/(k! * (2!)^k * (n-2*k)!).
T(n,k) = n!/k * (1-1/(n-k)-...-1/(k+1)-1/2k), if n/3 < k <= n/2.
T(n,k) = n!/k, if n/2 < k <= n.
T(n,n) = (n-1)! = A000142(n-1).
E.g.f. for k-th column: exp(-x^k*LerchPhi(x,1,k))*(exp(x^k/k)-1)/(1-x). - Vladeta Jovovic, Mar 03 2007
From Peter Luschny, Mar 07 2009: (Start)
T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n
T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,..,a_n such that
1*a_1+2*a_2+...+n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*..*a_n!),
f^a = (f_1/1!)^a_1*..*(f_n/n!)^a_n and f_n = product_{j=0..n-2}(j-n+1). (End)
Sum_{k=1..n} k * T(n,k) = A028418(n). - Alois P. Heinz, May 17 2016

A121294 a(m^2) = m^3; a(m^2+k) = m^3 + km, 0 <= k <= m; a(m(m+1)) = (m+1)m^2; a(m(m+1)+k) = (m+1)m^2 + k(2m+1), 0 <= k <= m+1; a((m+1)^2) = (m+1)^3.

Original entry on oeis.org

1, 2, 5, 8, 10, 12, 17, 22, 27, 30, 33, 36, 43, 50, 57, 64, 68, 72, 76, 80, 89, 98, 107, 116, 125

Offset: 1

Dan Dima, Aug 24 2006

nonn

A lower bound on A121231(n), the maximal number of 1's in any (0,1)-matrix M such that M^2 is also a (0,1)-matrix.

For example, for m^2 x m^2 matrices one can obtain a(m^2) = m^3 using m^2 m x m matrices with one row of m of 1's and (m-1) rows of m of 0's.

Edited by R. J. Mathar, Oct 01 2008

A121231 Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix.

Original entry on oeis.org

1, 2, 11, 172, 6327, 474286, 67147431, 17080038508

Offset: 0

Dan Dima, Aug 21 2006

Comments from Brendan McKay, Aug 21 2006: Equivalently, directed graphs (simple but loops allowed) without a few small forbidden subgraphs (those allowing 2 distinct paths of length 2 from vertex x to vertex y for some x,y; I think there are 6 possibilities). One can also consider isomorphism classes of those digraphs.
Comment from  Rob Pratt, Aug 03 2008: A121294 provides a lower bound on the maximum number of 1's in such a matrix M. There are cases where a higher number is reached; the following 5 X 5 matrix has 11 ones and its square is binary:
0 0 1 0 0
0 0 0 0 1
1 1 0 0 1
1 1 0 1 0
1 1 0 1 0.
The optimal values seem to match A070214, verified for n <= 7.
Term (5,1) of the n-th power of the 5 X 5 matrix shown is A001045(n), the Jacobsthal sequence. - Gary W. Adamson, Oct 03 2008
a(n) >= A226321(n).

Eric Weisstein's World of Mathematics, Background information about adjacency matrices
E. W. Weisstein, (0,1)-Matrix, MathWorld. [P. Petsie, Aug 03 2008]
Wikipedia, Background information about adjacency matrices
Index entries for matrices, binary, which are squares

Cf. A226321, A225371, A055084, A052264, A051589, A069452, A053304, A001045, A121294, A070214.

Edited by R. J. Mathar, Oct 01 2008
a(7) from R. H. Hardin, Jun 19 2012. This makes it clear that the old A122527 was really a badly-described version of this sequence, and that a(7) was earlier found by Balakrishnan (bvarada2(AT)jhu.edu), Sep 17 2006. - N. J. A. Sloane, Jun 19 2012
Entry revised by N. J. A. Sloane, Jun 19 2012

A107348 Triangle read by rows: T(m,n) = number of different lines in a rectangular m X n array of points with integer coordinates (x,y): 0 <= x <= m, 0 <= y <= n.

Original entry on oeis.org

0, 1, 6, 1, 11, 20, 1, 18, 35, 62, 1, 27, 52, 93, 140, 1, 38, 75, 136, 207, 306, 1, 51, 100, 181, 274, 405, 536, 1, 66, 131, 238, 361, 534, 709, 938, 1, 83, 164, 299, 454, 673, 894, 1183, 1492, 1, 102, 203, 370, 563, 836, 1111, 1470, 1855, 2306

Offset: 0

Dan Dima, May 23 2005

We may assume n <= m since T(m,n)=T(n,m).

			Triangle begins
0,
1, 6,
1, 11, 20,
1, 18, 35, 62,
1, 27, 52, 93, 140,
1, 38, 75, 136, 207, 306,
1, 51, 100, 181, 274, 405, 536,
1, 66, 131, 238, 361, 534, 709, 938,
1, 83, 164, 299, 454, 673, 894, 1183, 1492,
1, 102, 203, 370, 563, 836, 1111, 1470, 1855, 2306,
...

M. A. Alekseyev, M. Basova, and N. Yu. Zolotykh, On the minimal teaching sets of two-dimensional threshold functions, SIAM J. Disc. Math. 29(1), 2015, pp. 157-165.
Les Reid, Problem #7: How Many Lines Does the Lattice of Points Generate?, Problems from the 04-05 academic year, Challenge Archive, Missouri State University's Problem Corner.

Cf. A295707 (symmetric array), A018808 (diagonal). A160842 - A160850 (columns).

VR := proc(m,n,q) local a,i,j; a:=0;
for i from -m+1 to m-1 do for j from -n+1 to n-1 do
if gcd(i,j)=q then a:=a+(m-abs(i))*(n-abs(j)); fi; od: od: a; end;
LL:=(m,n)->(VR(m,n,1)-VR(m,n,2))/2;
for m from 1 to 12 do lprint([seq(LL(m,n),n=1..m)]); od: # N. J. A. Sloane, Feb 10 2020

VR[m_, n_, q_] := Sum[If[GCD[i, j] == q, (m - Abs[i])(n - Abs[j]), 0], {i, -m + 1, m - 1}, {j, -n + 1, n - 1}];
LL[m_, n_] := (1/2)(VR[m, n, 1] - VR[m, n, 2]);
Table[LL[m, n], {m, 1, 10}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jun 04 2023, after N. J. A. Sloane *)

T(0, 0) = 0; T(m, 0) = 1, m >= 1.
When both m,n -> +oo, T(m,n) / 2Cmn -> 9/(2*pi^2). - Dan Dima, Mar 18 2006
T(n,m) = A295707(n,m). - R. J. Mathar, Dec 17 2017

T(3,3) corrected and sequence extended by R. J. Mathar, Dec 17 2017

cp's OEIS Frontend

User: Dan Dima

A306556 Integers that appear as (unreduced) numerators of segment endpoints when a ternary Cantor set is created.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A189722 Number of self-avoiding walks of length n on square lattice such that at each point the angle turns 90 degrees (the first turn is assumed to be to the left - otherwise the number must be doubled).

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

Extensions

A126074 Triangle read by rows: T(n,k) is the number of permutations of n elements that have the longest cycle length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A121294 a(m^2) = m^3; a(m^2+k) = m^3 + km, 0 <= k <= m; a(m(m+1)) = (m+1)m^2; a(m(m+1)+k) = (m+1)m^2 + k(2m+1), 0 <= k <= m+1; a((m+1)^2) = (m+1)^3.

Views

Author

Keywords

Comments

Extensions

A121231 Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A107348 Triangle read by rows: T(m,n) = number of different lines in a rectangular m X n array of points with integer coordinates (x,y): 0 <= x <= m, 0 <= y <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions