A152086 -id:A152086 - cp's OEIS frontend

A102699 Number of strings of length n, using as symbols numbers from the set {1, 2, ..., n}, in which consecutive symbols differ by exactly 1.

1, 1, 2, 6, 16, 42, 104, 252, 592, 1370, 3112, 6996, 15536, 34244, 74832, 162616, 351136, 754938, 1615208, 3443940, 7314928, 15493676, 32714992, 68918856, 144815456, 303703972, 635554064, 1327816392, 2769049312, 5766417480, 11989472672, 24897569648

Offset: 0

Don Rogers (donrogers42(AT)aol.com), Feb 07 2005

nonn

Equally, number of different n-digit numbers, using only the digits 1 through n, where consecutive digits differ by 1. It is assumed that there are n different digits available even when n > 9.
Number of endomorphisms of a path P_n. - N. J. A. Sloane, Sep 20 2009
a(n) is also the number of distinct paths of length n starting from the bottom row of an n X n chess board and ending at the top row, such that all the n squares traversed in the path are of the same color. - Kiran Ananthpur Bacche, Oct 25 2022

			For example, a(4)=16: the 16 strings are 1212, 1232, 1234, 2121, 2123, 2321, 2323, 2343, 3212, 3232, 3234, 3432, 3434, 4321, 4323, 4343.
G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 104*x^6 + 252*x^7 + 592*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..3311 (terms n = 1..300 from T. D. Noe)
Sr. Arworn, An algorithm for the number of endomorphisms on paths, Disc. Math., 309 (2009), 94-103 (see p. 95).
Zhicong Lin and Jiang Zeng, On the number of congruence classes of paths, arXiv preprint arXiv:1112.4026 [math.CO], 2011.
M. A. Michels and U. Knauer, The congruence classes of paths and cycles, Discr. Math., 309 (2009), 5352-5359. See p. 5356. [From _N. J. A. Sloane_, Sep 20 2009]
Joseph Myers, BMO 2008-2009 Round 1 Problem 1-Generalisation

Cf. A110971, A152086.

Main diagonal of A220062. - Alois P. Heinz, Dec 03 2012

p:= 0; paths := proc(m, n, s, t) global p; if(((t+1) <= m) and s <= (n)) then paths(m,n,s+1,t+1); end if; if(((t-1) > 0) and s <= (n)) then paths(m,n,s+1,t-1); end if; if(s = n) then p:=p+1; end if; end proc; sumpaths:=proc(j) global p; p:=0; sp:=0; for h from 1 to j do p:=0; paths(j,j,1,h); sp:=sp+ p ; end do; sp; end proc; for l from 1 to 50 do sumpaths(l); end do; # Ben Paul Thurston, Oct 04 2006
# second Maple program:
a:= proc(n) option remember;
      `if`(n<5, [1, 1, 2, 6, 16][n+1], ((2*n^2-6*n-4) *a(n-1)
      +(56-32*n+4*n^2) *a(n-2) -8*(n-3)^2 *a(n-3))/ ((n-1)*(n-4)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 23 2012

a[n_] := a[n] = If[n <= 4, n*((n-3)*n+4)/2, ((2*n^2 - 6*n - 4)*a[n-1] + (4*n^2 - 32*n + 56)*a[n-2] - 8*(n-3)^2*a[n-3])/((n-1)*(n-4))]; Table[ a[n], {n, 1, 30}] (* Jean-François Alcover, Nov 10 2015, after Alois P. Heinz *)

x='x+O('x^55); Vec(x*(2*(1-x)-sqrt(1-4*x^2))/(1-2*x)^2) \\ Altug Alkan, Nov 10 2015

from math import comb
def A102699(n): return ((n+1<>1) if n&1 else (n-1)*comb(n-2,n-2>>1)<<2)) if n else 1 # Chai Wah Wu, Oct 28 2024

It appears that the limit of a(n)/a(n-1) is decreasing towards 2. - Ben Paul Thurston, Oct 04 2006
a(n) = (n+1)2^(n-1) - 4(n-1)binomial(n-2,(n-2)/2) for n even, a(n) = (n+1)2^(n-1) - (2n-1)binomial(n-1,(n-1)/2) for n odd. - Joseph Myers, Dec 23 2008
a(n) = 2 * Sum_{k=1..n-1} k*A110971(n,k). - N. J. A. Sloane, Sep 20 2009
G.f.: x * (2*(1 - x) - sqrt(1 - 4*x^2)) / (1 - 2*x)^2. - Michael Somos, Mar 17 2014
0 = a(n) * 8*n^2 - a(n+1) * 4*(n^2 - 2*n - 1) - a(n+2) * 2*(n^2 + 3*n - 2) + a(n+3) * (n-1)*(n+2) for n>0. - Michael Somos, Mar 17 2014
0 = a(n) * (16*a(n+1) - 16*a(n+2) + 4*a(n+3)) + a(n+1) * (-16*a(n+1) + 20*a(n+2) - 4*a(n+3)) + a(n+2) * (-4*a(n+2) + a(n+3)) for n>0. - Michael Somos, Mar 17 2014

More terms from Ben Paul Thurston, Oct 04 2006
a(20) onwards from David Wasserman, Apr 26 2008
Edited by N. J. A. Sloane, Jan 03 2009 and Sep 23 2010
a(0)=1 prepended by Alois P. Heinz, Apr 17 2017

A377000 Array read by ascending antidiagonals: T(n,k) = number of n-esthetic numbers with k digits.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 5, 4, 1, 5, 7, 8, 6, 1, 6, 9, 12, 13, 8, 1, 7, 11, 16, 21, 21, 12, 1, 8, 13, 20, 29, 36, 34, 16, 1, 9, 15, 24, 37, 52, 63, 55, 24, 1, 10, 17, 28, 45, 68, 94, 108, 89, 32, 1, 11, 19, 32, 53, 84, 126, 169, 189, 144, 48, 1, 12, 21, 36, 61, 100, 158, 232, 305, 324, 233, 64, 1

Offset: 2

Paolo Xausa, Oct 12 2024

A number is n-esthetic if, when written in base n, adjacent digits differ by 1: see De Koninck and Doyon (2009), where T(n,k) is denoted by N_q(r).

			Array begins (cf. De Koninck and Doyon (2009), table on p. 155):
  n\k| 1   2   3   4    5    6    7    8     9    10  ...
  -------------------------------------------------------
   2 | 1,  1,  1,  1,   1,   1,   1,   1,    1,    1, ... = A000012
   3 | 2,  3,  4,  6,   8,  12,  16,  24,   32,   48, ... = A029744 (from n = 2)
   4 | 3,  5,  8, 13,  21,  34,  55,  89,  144,  233, ... = A000045 (from n = 4)
   5 | 4,  7, 12, 21,  36,  63, 108, 189,  324,  567, ... = A228879
   6 | 5,  9, 16, 29,  52,  94, 169, 305,  549,  990, ...
   7 | 6, 11, 20, 37,  68, 126, 232, 430,  792, 1468, ...
   8 | 7, 13, 24, 45,  84, 158, 296, 557, 1045, 1966, ...
   9 | 8, 15, 28, 53, 100, 190, 360, 685, 1300, 2475, ...
  10 | 9, 17, 32, 61, 116, 222, 424, 813, 1556, 2986, ... = A090994
  ...                                               \______ A152086 (main diagonal)

Paolo Xausa, Table of n, a(n) for n = 2..11326 (first 150 antidiagonals, flattened).
Jean-Marie De Koninck and Nicolas Doyon, Esthetic Numbers, Ann. Sci. Math. Québec 33 (2009), No. 2, pp. 155-164.
Giovanni Resta, Esthetic Numbers, Numbers Aplenty, 2013.
Branko J. Malesevic, Some combinatorial aspects of differential operation composition on the space R^n, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 29-33 (arXiv version, arXiv:0704.0750 [math.DG], 2007).

Cf. A000012 (row n = 2), A029744 (row n = 3), A000045 (row n = 4), A228879 (row n = 5), A090994 (row n = 10).
Cf. A102699, A152086 (main diagonal).
Diagonal above the main diagonal appears to be A206603.

A377000[n_, k_] := Round[2^k/(n+1)*Sum[If[m != (n+1)/2, Cos[#]^k*(Cot[#] + Csc[#])^2 & [Pi*m/(n+1)], 0], {m, 1, n, 2}]];
Table[A377000[n-k+1, k], {n, 2, 15}, {k, n-1}]

from itertools import count, islice
from functools import lru_cache
@lru_cache(maxsize=None)
def A377000_N(q,r,i):
    if r==1 and i==0: return 0
    if r==1: return 1
    if q==2: return r+i&1^1
    if i == 0: return A377000_N(q,r-1,1)
    if i == q-1: return A377000_N(q,r-1,q-2)
    return A377000_N(q,r-1,i-1)+A377000_N(q,r-1,i+1)
def A377000_T(n,k): return sum(A377000_N(n,k,i) for i in range(n))
def A377000_gen(): # generator of terms
    for n in count(2):
        for k in range(1,n):
            yield A377000_T(n-k+1,k)
A377000_list = list(islice(A377000_gen(),100)) # Chai Wah Wu, Oct 21 2024

All of the following formulas are taken from De Koninck and Doyon (2009).
T(n,k) = 2^k/(n+1) * Sum_{m=1..n, m odd, m != (n+1)/2} cos(p)^k*(cot(p) + csc(p))^2, where p = Pi*m/(n+1).
T(n,1) = n - 1.
T(2,k) = 1.
T(3,k) = 2^((k+1)/2) if k is odd, 3*2^((k-2)/2) if k is even = A029744(k+1).
T(4,k) = A000045(k+3).
T(5,k) = 4*3^((k-1)/2) if k is odd, 7*3^((k-2)/2) if k is even = A228879(k-1).
Conjectures from Chai Wah Wu, Oct 21 2024: (Start)
Conjecture 1: For even n, T(n,k) is the number of meaningful differential operations of the k-th order on the space R^(n-1).
Conjecture 2: For each n, the row T(n,k) satisfies a linear recurrence. For example:
T(6,k) = T(6,k-1) + 2*T(6,k-2) - T(6,k-3) for k > 3 (A090990).
T(7,k) = 4*T(7,k-2) - 2*T(7,k-4) for k > 4.
T(8,k) = T(8,k-1) + 3*T(8,k-2) - 2*T(8,k-3) - T(8,k-4) for k > 4 (A090992).
T(9,k) = 5*T(9,k-2) - 5*T(9,k-4) for k > 4.
T(10,k) = T(10,k-1) + 4*T(10,k-2) - 3*T(10,k-3) - 3*T(10,k-4) + T(10,k-5) for k > 5.
T(11,k) = 6*T(11,k-2) - 9*T(11,k-4) + 2*T(11,k-6) for k > 6.
T(12,k) = T(12,k-1) + 5*T(12,k-2) - 4*T(12,k-3) - 6*T(12,k-4) + 3*T(12,k-5) + T(12,k-6) for k > 6 (A129638).
...
Note that for even n, Conjecture 1 implies Conjecture 2 due to (Malesevic, 1998).
Conjecture 3: T(n,n-2) = A182555(n-2). (End)

A110971 Triangle T(n,k) (n >= 2, 1 <= k <= n-1) read by rows: row n gives epispectrum of a path P_n (see reference for precise definition).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 6, 6, 1, 1, 2, 7, 11, 10, 1, 1, 2, 8, 14, 24, 14, 1, 1, 2, 9, 16, 35, 42, 22, 1, 1, 2, 10, 18, 45, 68, 81, 30, 1, 1, 2, 11, 20, 55, 89, 149, 138, 46, 1, 1, 2, 12, 22, 66, 110, 216, 282, 250, 62, 1, 1, 2, 13, 24, 78, 132, 285, 422, 577, 419

Offset: 2

N. J. A. Sloane, Sep 20 2009

			Triangle begins:
  1;
  1, 1;
  1, 2,  1;
  1, 2,  4,  1;
  1, 2,  6,  6,  1;
  1, 2,  7, 11, 10,   1;
  1, 2,  8, 14, 24,  14,   1;
  1, 2,  9, 16, 35,  42,  22,   1;
  1, 2, 10, 18, 45,  68,  81,  30,   1;
  1, 2, 11, 20, 55,  89, 149, 138,  46,    1;
  1, 2, 12, 22, 66, 110, 216, 282, 250,   62,   1;
  1, 2, 13, 24, 78, 132, 285, 422, 577,  419,  94,   1;
  1, 2, 14, 26, 91, 156, 364, 568, 945, 1070, 732, 126, 1;

Toufik Mansour, Armend Sh. Shabani, Bargraphs in bargraphs, Turkish Journal of Mathematics (2018) Vol. 42, Issue 5, 2763-2773.
M. A. Michels and U. Knauer, The congruence classes of paths and cycles, Discr. Math., 309 (2009), 5352-5359.

Cf. A152086, A102699.

cp's OEIS Frontend

A102699 Number of strings of length n, using as symbols numbers from the set {1, 2, ..., n}, in which consecutive symbols differ by exactly 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A377000 Array read by ascending antidiagonals: T(n,k) = number of n-esthetic numbers with k digits.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A110971 Triangle T(n,k) (n >= 2, 1 <= k <= n-1) read by rows: row n gives epispectrum of a path P_n (see reference for precise definition).

Views

Author

Keywords

Examples

Links

Crossrefs