A040000 -id:A040000 - cp's OEIS frontend

A034182 Number of not-necessarily-symmetric n X 2 crossword puzzle grids.

1, 5, 15, 39, 97, 237, 575, 1391, 3361, 8117, 19599, 47319, 114241, 275805, 665855, 1607519, 3880897, 9369317, 22619535, 54608391, 131836321, 318281037, 768398399, 1855077839, 4478554081, 10812186005, 26102926095, 63018038199, 152139002497, 367296043197

Offset: 1

Erich Friedman

n X 2 binary arrays with a path of adjacent 1's and no path of adjacent 0's from top row to bottom row. - R. H. Hardin, Mar 21 2002

Define a triangle with T(n,1) = T(n,n) = n*(n-1) + 1, n>=1, and its interior terms via T(r,c) = T(r-1,c) + T(r-1,c-1)+ T(r-2,c-1), 2<=cJ. M. Bergot, Mar 16 2013

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 145.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1)

Row 2 of A292357.
Column sums of A059678.
Cf. A001333, A034184, A034187, A052542 (first differences).

a034182 n = a034182_list !! (n-1)
a034182_list = 1 : 5 : (map (+ 4) $
   zipWith (+) a034182_list (map (* 2) $ tail a034182_list))
-- Reinhard Zumkeller, May 23 2013

{1}~Join~NestList[{#2, 2 #2 + #1 + 4} & @@ # &, {1, 5}, 28][[All, -1]] (* Michael De Vlieger, Oct 02 2017 *)

a(n) = 2a(n-1) + a(n-2) + 4.
(1 + 5x + 15x^2 + ...) = (1 + 2x + 2x^2 + ...) * (1 + 3x + 7x^2 + ...), convolution of A040000 and left-shifted A001333.
a(n) = (-4 + (1-sqrt(2))^(1+n) + (1+sqrt(2))^(1+n))/2. G.f.: x*(1+x)^2/((1-x)*(1 - 2*x - x^2)). - Colin Barker, May 22 2012
a(n) = A001333(n+1)-2. - R. J. Mathar, Mar 28 2013
a(n) = A048739(n-3) +2*A048739(n-2) +A048739(n-1). - R. J. Mathar, Jun 15 2020

A171861 Expansion of x(1+x+x^2) / ( (x-1)(x^3+x^2-1) ).

Original entry on oeis.org

1, 2, 4, 6, 9, 13, 18, 25, 34, 46, 62, 83, 111, 148, 197, 262, 348, 462, 613, 813, 1078, 1429, 1894, 2510, 3326, 4407, 5839, 7736, 10249, 13578, 17988, 23830, 31569, 41821, 55402, 73393, 97226, 128798, 170622, 226027, 299423, 396652, 525453, 696078, 922108

Offset: 1

Ed Pegg Jr, Oct 16 2010

Number of wins in Penney's game if the two players start HHT and TTT and HHT beats TTT.

HHT beats TTT 70% of the time. - Geoffrey Critzer, Mar 01 2014

			a(n) enumerates length n+2 sequences on {H,T} that end in HHT but do not contain the contiguous subsequence TTT.
a(3)=4 because we have: TTHHT, THHHT, HTHHT, HHHHT.
a(4)=6 because we have: TTHHHT, THTHHT, THHHHT, HTTHHT, HTHHHT, HHHHHT. - _Geoffrey Critzer_, Mar 01 2014

G. C. Greubel, Table of n, a(n) for n = 1..1000
Wikipedia, Penney's game
Index entries for linear recurrences with constant coefficients, signature (1,1,0,-1).

Related sequences are A000045 (HHH beats HHT, HTT beats TTH), A006498 (HHH beats HTH), A023434 (HHH beats HTT), A000930 (HHH beats THT, HTH beats HHT), A000931 (HHH beats TTH), A077868 (HHT beats HTH), A002620 (HHT beats HTT), A000012 (HHT beats THH), A004277 (HHT beats THT), A070550 (HTH beats HHH), A000027 (HTH beats HTT), A097333 (HTH beats THH), A040000 (HTH beats TTH), A068921 (HTH beats TTT), A054405 (HTT beats HHH), A008619 (HTT beats HHT), A038718 (HTT beats THT), A128588 (HTT beats TTT).

Cf. A164315 (essentially the same sequence).

A171861 := proc(n) option remember; if n <=4 then op(n,[1,2,4,6]); else procname(n-1)+procname(n-2)-procname(n-4) ; end if; end proc:

nn=44;CoefficientList[Series[x(1+x+x^2)/(1-x-x^2+x^4),{x,0,nn}],x] (* Geoffrey Critzer, Mar 01 2014 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,0,1,1]^(n-1)*[1;2;4;6])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

a(n) = a(n-1) +a(n-2) -a(n-4) = A000931(n+10)-3 = A134816(n+6)-3 = A078027(n+12)-3.

a(n) = A164315(n-1). - Alois P. Heinz, Oct 12 2017

A186021 a(n) = Bell(n)*(2 - 0^n).

Original entry on oeis.org

1, 2, 4, 10, 30, 104, 406, 1754, 8280, 42294, 231950, 1357140, 8427194, 55288874, 381798644, 2765917090, 20960284294, 165729739608, 1364153612318, 11665484410114, 103448316470744, 949739632313502, 9013431476894646, 88304011710168692, 891917738589610578, 9277180664459998706

Offset: 0

Paul Barry, Feb 10 2011

a(n) is the number of collections of subsets of {1,2,...,n-1} that are pairwise disjoint. a(n+1) = 2*Sum_{j=0..n} C(n,j)*Bell(j). For example a(3)=10 because we have: {}, {{}}, {{1}}, {{2}}, {{1,2}}, {{},{1}}, {{},{2}}, {{},{1,2}}, {{1},{2}}, {{},{1},{2}}. - Geoffrey Critzer, Aug 28 2014

a(n) is the number of collections of subsets of [n] that are pairwise disjoint and cover [n], with [0] = {}. For disjoint collections of nonempty subsets see A000110. For arbitrary collections of subsets see A000371. For arbitrary collections of nonempty subsets see A003465. - Manfred Boergens, May 02 2024 and Apr 09 2025

			a(4) = A060719(3) + 1 = 29 + 1 = 30.

G. C. Greubel, Table of n, a(n) for n = 0..575

Row sums of A186020 and A256894.
Main diagonal of A271466 (shifted) and A381682.
Cf. A000110, A000371, A003465.

[Bell(n)*(2-0^n): n in [0..50]]; // Vincenzo Librandi, Apr 06 2011

A186021List := proc(m) local A, P, n; A := [1,2]; P := [2];
for n from 1 to m - 2 do P := ListTools:-PartialSums([P[-1], op(P)]);
A := [op(A), P[-1]] od; A end: A186021List(26); # Peter Luschny, Mar 24 2022

Prepend[Table[2 Sum[Binomial[n, j] BellB[j], {j, 0, n}], {n, 0, 25}], 1] (* Geoffrey Critzer, Aug 28 2014 *)
With[{nmax = 50}, CoefficientList[Series[2*Exp[Exp[x] - 1] - 1, {x, 0, nmax}], x]*Range[0, nmax]!] (* G. C. Greubel, Jul 24 2017 *)

x='x+O('x^50); Vec(serlaplace(2*exp(exp(x) - 1) -1)) \\ G. C. Greubel, Jul 24 2017

from itertools import accumulate
def A186021_list(size):
    if size < 1: return []
    L, accu = [1], [2]
    for _ in range(size-1):
        accu = list(accumulate([accu[-1]] + accu))
        L.append(accu[0])
    return L
print(A186021_list(26)) # Peter Luschny, Apr 25 2016

E.g.f.: 2*exp(exp(x)-1)-1. - Paul Barry, Apr 06 2011
a(n) = A000110(n)*A040000(n).
a(n+1) = 1 + Sum_{k=0..n} C(n,k)*a(k). - Franklin T. Adams-Watters, Oct 02 2011
From Sergei N. Gladkovskii, Nov 11 2012 to Mar 29 2013: (Start)
Continued fractions:
G.f.: A(x)= 1 + 2*x/(G(0)-x) where G(k)= 1 - x*(k+1)/(1 - x/G(k+1)).
G.f.: G(0)-1 where G(k) = 1-(x*k+1)/(x*k - 1 - x*(x*k - 1)/(x + (x*k + 1)/G(k+1))).
G.f.: (G(0)-2)/x - 1 where G(k) = 1 + 1/(1 - x/(x + (1 - x*k)/G(k+1))).
G.f.: (S-2)/x - 1 where S = 2*Sum_{k>=0} x^k/Product_{n=0..k-1}(1 - n*x).
G.f.: 1/(1-x) - x/(G(0)-x^2+x) where G(k) =x^2 + x - 1 + k*(2*x-x^2) - x^2*k^2 + x*(x*k - 1)*(x*k + 2*x - 1)^2/G(k+1).
E.g.f.: E(0) - 1 where E(k) = 1 + 1/(1 - 1/(1 + (k+1)/x*Bell(k)/Bell(k+1)/E(k+1))). (End)
a(n) = A060719(n-1) + 1, and the inverse binomial transform of A060719. - Gary W. Adamson, May 20 2013
G.f. A(x) satisfies: A(x) = 1 + (x/(1 - x)) * (1 + A(x/(1 - x))). - Ilya Gutkovskiy, Jun 30 2020

A040006 Continued fraction for sqrt(10).

Original entry on oeis.org

3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset: 0

N. J. A. Sloane

Eventual period is (6). - Zak Seidov, Mar 05 2011
The convergents are given in A005667(n+1)/A005668(n+1), n >= 0. - Wolfdieter Lang, Nov 23 2017
Decimal expansion of 11/30. - Elmo R. Oliveira, Feb 16 2024

			3.162277660168379331998893544... = 3 + 1/(6 + 1/(6 + 1/(6 + 1/(6 + ...)))).

James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 276.

Harry J. Smith, Table of n, a(n) for n = 0..20000
G. Xiao, Contfrac
Index entries for continued fractions for constants
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A010467 (decimal expansion), A005667(n+1)/A005668(n+1) (convergents), A248239 (Egyptian fraction).

Cf. A040000.

[6-3*(Binomial(2*n,n) mod 2): n in [0..100]]; // Vincenzo Librandi, Jan 03 2016

Digits := 100: convert(evalf(sqrt(N)),confrac,90,'cvgts'):

ContinuedFraction[Sqrt[10],300] (* Vladimir Joseph Stephan Orlovsky, Mar 04 2011 *)
PadRight[{3},120,{6}] (* Harvey P. Dale, Aug 25 2024 *)

contfrac(sqrt(10)) \\ For illustration.

A040006(n)=if(n,6,3) \\ M. F. Hasler, Nov 02 2019

a(n) = 3 + 3*sign(n). a(n) = 6, n > 0. - Wesley Ivan Hurt, Nov 01 2013
From Elmo R. Oliveira, Feb 16 2024: (Start)
G.f.: 3*(1+x)/(1-x).
E.g.f.: 6*exp(x) - 3.
a(n) = 3*A040000(n). (End)

A113413 A Riordan array of coordination sequences.

Original entry on oeis.org

1, 2, 1, 2, 4, 1, 2, 8, 6, 1, 2, 12, 18, 8, 1, 2, 16, 38, 32, 10, 1, 2, 20, 66, 88, 50, 12, 1, 2, 24, 102, 192, 170, 72, 14, 1, 2, 28, 146, 360, 450, 292, 98, 16, 1, 2, 32, 198, 608, 1002, 912, 462, 128, 18, 1, 2, 36, 258, 952, 1970, 2364, 1666, 688, 162, 20, 1, 2, 40, 326

Offset: 0

Paul Barry, Oct 29 2005

Columns include A040000, A008574, A005899, A008412, A008413, A008414. Row sums are A078057(n)=A001333(n+1). Diagonal sums are A001590(n+3). Reverse of A035607. Signed version is A080246. Inverse is A080245.
For another version see A122542. - Philippe Deléham, Oct 15 2006
T(n,k) is the number of length n words on alphabet {0,1,2} with no two consecutive 1's and no two consecutive 2's and having exactly k 0's. - Geoffrey Critzer, Jun 11 2015
From Eric W. Weisstein, Feb 17 2016: (Start)
Triangle of coefficients (from low to high degree) of x^-n * vertex cover polynomial of the n-ladder graph P_2 \square p_n:
  Psi_{L_1}: x*(2 + x) -> {2, 1}
  Psi_{L_2}: x^2*(2 + 4 x + x^2) -> {2, 4, 1}
  Psi_{L_3}: x^3*(2 + 8 x + 6 x^2 + x^3) -> {2, 8, 6, 1}
(End)
Let c(n, k), n > 0, be multiplicative sequences for some fixed integer k >= 0 with c(p^e, k) = T(e+k, k) for prime p and e >= 0. Then we have Dirichlet g.f.: Sum_{n>0} c(n, k) / n^s = zeta(s)^(2*k+2) / zeta(2*s)^(k+1). Examples: For k = 0 see A034444 and for k = 1 see A322328. Dirichlet convolution of c(n, k) and lambda(n) is Dirichlet inverse of c(n, k). - Werner Schulte, Oct 31 2022

			Triangle begins
  1;
  2,  1;
  2,  4,  1;
  2,  8,  6,  1;
  2, 12, 18,  8,  1;
  2, 16, 38, 32, 10,  1;
  2, 20, 66, 88, 50, 12,  1;

G. C. Greubel, Table of n, a(n) for the first 50 rows
Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
P. Holub, M. Miller, H. Perez-Roses, and J. Ryan, Degree diameter problem on honeycomb networks, Disc. Appl. Math. 179 (2014) 139-151.
Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 2.
Mirka Miller, Hebert Perez-Roses, and Joe Ryan, The Maximum Degree-and-Diameter-Bounded Subgraph in the Mesh, arXiv preprint arXiv:1203.4069 [math.CO], 2012.

Other versions: A035607, A119800, A122542, A266213.

nn = 10; Map[Select[#, # > 0 &] &, CoefficientList[Series[1/(1 - 2 x/(1 + x) - y x), {x, 0, nn}], {x, y}]] // Grid (* Geoffrey Critzer, Jun 11 2015 *)
CoefficientList[CoefficientList[Series[1/(1 - 2 x/(1 + x) - y x), {x, 0, 10}, {y, 0, 10}], x], y] (* Eric W. Weisstein, Feb 17 2016 *)

T = lambda n,k : binomial(n, k)*hypergeometric([-k-1, k-n], [-n], -1).simplify_hypergeometric()
A113413 = lambda n,k : 1 if n==0 and k==0 else T(n, k)
for n in (0..12): print([A113413(n,k) for k in (0..n)]) # Peter Luschny, Sep 17 2014 and Mar 16 2016

# Alternatively:
def A113413_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return prec(n-1,k-1)+2*sum(prec(n-i,k-1) for i in (2..n-k+1))
    return [prec(n, k) for k in (1..n)]
for n in (1..10): print(A113413_row(n)) # Peter Luschny, Mar 16 2016

From Paul Barry, Nov 13 2005: (Start)
Riordan array ((1+x)/(1-x), x(1+x)/(1-x)).
T(n, k) = Sum_{i=0..n-k} C(k+1, i)*C(n-i, k).
T(n, k) = Sum_{j=0..n-k} C(k+j, j)*C(k+1, n-k-j).
T(n, k) = D(n, k) + D(n-1, k) where D(n, k) = Sum_{j=0..n-k} C(n-k, j)*C(k, j)*2^j = A008288(n, k).
T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-2, k-1).
T(n, k) = Sum_{j=0..n} C(floor((n+j)/2), k)*C(k, floor((n-j)/2)). (End)
T(n, k) = C(n, k)*hypergeometric([-k-1, k-n], [-n], -1). - Peter Luschny, Sep 17 2014
T(n, k) = (Sum_{i=2..k+2} A137513(k+2, i) * (n-k)^(i-2)) / (k!) for 0 <= k < n (conjectured). - Werner Schulte, Oct 31 2022

A158799 a(0)=1, a(1)=2, a(n)=3 for n >= 2.

Original entry on oeis.org

1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 0

Jaume Oliver Lafont, Mar 27 2009

a(n) = number of neighboring natural numbers of n (i.e., n, n - 1, n + 1). a(n) = number of natural numbers m such that n - 1 <= m <= n + 1. Generalization: If a(n,k) = number of natural numbers m such that n - k <= m <= n + k (k >= 1) then a(n,k) = a(n-1,k) + 1 = n + k for 0 <= n <= k, a(n,k) = a(n-1,k) = 2*k + 1 for n >= k + 1. - Jaroslav Krizek, Nov 18 2009
Partial sums of A130716; partial sums give A008486. - Jaroslav Krizek, Dec 06 2009
In atomic spectroscopy, a(n) is the number of P term symbols with spin multiplicity equal to n+1, i.e., there is one singlet-P term (n=0), there are two doublet-P terms (n=1), and there are three P terms for triple multiplicity (n=2) and higher (n>2). - A. Timothy Royappa, Mar 16 2012
a(n+1) is also the domination number of the n-Andrásfai graph. - Eric W. Weisstein, Apr 09 2016
Decimal expansion of 37/300. - Elmo R. Oliveira, May 11 2024
a(n+1) is also the domination number of the n X n rook complement graph. - Eric W. Weisstein, Mar 10 2025

David Applegate, The movie version
Eric Weisstein's World of Mathematics, Andrásfai Graph.
Eric Weisstein's World of Mathematics, Domination Number.
Eric Weisstein's World of Mathematics, Rook Complement Graph.
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A040000, A122553, A130130, A139250, A157532, A158411, A158478, A158515.

Cf. A008486, A130716.

PadRight[{1,2},120,{3}] (* or *) Min[#,3]&/@Range[120] (* Harvey P. Dale, Apr 08 2018 *)

PARI
```
a(n)=if(n>1,3,if(n<0,0,n++))
```

G.f.: (1+x+x^2)/(1-x) = (1-x^3)/(1-x)^2.
a(n) = (n>=0)+(n>=1)+(n>=2).
a(n) = 1 + n for 0 <= n <= 1, a(n) = 3 for n >= 2. a(n) = A157532(n) for n >= 1. - Jaroslav Krizek, Nov 18 2009
E.g.f.: 3*exp(x) - x - 2 = x^2/(2*G(0)) where G(k) = 1 + (k+2)/(x - x*(k+1)/(x + k + 1 - x^4/(x^3 + (k+1)*(k+2)*(k+3)/G(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Jul 06 2012
a(n) = min(n+1,3). - Wesley Ivan Hurt, Apr 16 2014
a(n) = 1 + A130130(n). - Elmo R. Oliveira, May 11 2024

Corrected by Jaroslav Krizek, Dec 17 2009

A115291 Expansion of (1+x)^3/(1-x).

Original entry on oeis.org

1, 4, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8

Offset: 0

Paul Barry, Jan 19 2006

Partial sums are A086570. Partial sums of squares are A115295. Correlation triangle is A115292.
Let m=4. We observe that a(n) = Sum_{k=0..floor(n/2)} C(m,n-2*k). Then there is a link with A113311 and A040000: it is the same formula with respectively m=3 and m=2. We can generalize this result with the sequence whose G.f is given by (1+z)^(m-1)/(1-z). - Richard Choulet, Dec 08 2009
Also continued fraction expansion of (132-sqrt(17))/103. - Bruno Berselli, Sep 23 2011
Also decimal expansion of 1331/9000. - Vincenzo Librandi, Sep 23 2011

Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A040000, A113311, A171418, A171440, A171441, A171442, A171443.

CoefficientList[Series[(1+x)^3/(1-x),{x,0,100}],x] (* or *) PadRight[ {1,4,7},120,{8}] (* Harvey P. Dale, May 23 2016 *)

a(n) = 8 - C(2, n) - 2*C(1, n) - 4*C(0, n).
a(n) = Sum_{k=0..n} C(3, k).
a(n) = A004070(n, 3).
From Elmo R. Oliveira, Aug 09 2024: (Start)
E.g.f.: 8*exp(x) - 7 - 4*x - x^2/2.
a(n) = 8, n > 2. (End)

A287825 Number of sequences over the alphabet {0,1,...,9} such that no two consecutive terms have distance 1.

Original entry on oeis.org

1, 10, 82, 674, 5540, 45538, 374316, 3076828, 25291120, 207889674, 1708825732, 14046322404, 115458919774, 949057110644, 7801124426174, 64124215108032, 527092600834054, 4332631742719370, 35613662169258228, 292739611493034596, 2406281042646218328

Offset: 0

David Nacin, Jun 02 2017

Index entries for linear recurrences with constant coefficients, signature (9, -4, -21, 9, 5).

Cf. A040000, A003945, A083318, A078057, A003946, A126358, A003946, A055099, A003947, A015448, A126473. A287804-A287819. A287825-A287831.

LinearRecurrence[{9, -4, -21, 9, 5}, {1, 10, 82, 674, 5540, 45538}, 40]

def a(n):
    if n in [0, 1, 2, 3, 4, 5]:
        return [1, 10, 82, 674, 5540, 45538][n]
    return 9*a(n-1) - 4*a(n-2) - 21*a(n-3) + 9*a(n-4) + 5*a(n-5)

For n>5, a(n) = 9*a(n-1) - 4*a(n-2) - 21*a(n-3) + 9*a(n-4) + 5*a(n-5), a(0)=1, a(1)=10, a(2)=82, a(3)=674, a(4)=5540, a(5)=45538.

G.f.: (-1 - x + 4*x^2 + 3*x^3 - 3*x^4 - x^5)/(-1 + 9*x - 4*x^2 - 21*x^3 + 9*x^4 + 5*x^5).

A306209 Number A(n,k) of permutations of [n] within distance k of a fixed permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 6, 5, 1, 1, 1, 2, 6, 14, 8, 1, 1, 1, 2, 6, 24, 31, 13, 1, 1, 1, 2, 6, 24, 78, 73, 21, 1, 1, 1, 2, 6, 24, 120, 230, 172, 34, 1, 1, 1, 2, 6, 24, 120, 504, 675, 400, 55, 1, 1, 1, 2, 6, 24, 120, 720, 1902, 2069, 932, 89, 1, 1, 1, 2, 6, 24, 120, 720, 3720, 6902, 6404, 2177, 144, 1

Offset: 0

Alois P. Heinz, Jan 29 2019

A(n,k) counts permutations p of [n] such that |p(j)-j| <= k for all j in [n].

			A(4,1) = 5: 1234, 1243, 1324, 2134, 2143.
A(5,2) = 31: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13524, 14235, 14253, 14325, 14523, 21345, 21354, 21435, 21453, 21534, 21543, 23145, 23154, 24135, 24153, 31245, 31254, 31425, 31524, 32145, 32154, 34125.
Square array A(n,k) begins:
  1,  1,   1,    1,    1,     1,     1,     1,     1, ...
  1,  1,   1,    1,    1,     1,     1,     1,     1, ...
  1,  2,   2,    2,    2,     2,     2,     2,     2, ...
  1,  3,   6,    6,    6,     6,     6,     6,     6, ...
  1,  5,  14,   24,   24,    24,    24,    24,    24, ...
  1,  8,  31,   78,  120,   120,   120,   120,   120, ...
  1, 13,  73,  230,  504,   720,   720,   720,   720, ...
  1, 21, 172,  675, 1902,  3720,  5040,  5040,  5040, ...
  1, 34, 400, 2069, 6902, 17304, 30960, 40320, 40320, ...

Alois P. Heinz, Antidiagonals n = 0..36, flattened
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
Torleiv Kløve, Generating functions for the number of permutations with limited displacement, Electron. J. Combin., 16 (2009), #R104.

Columns k=0..10 give: A000012, A000045(n+1), A002524, A002526, A072856, A154654, A154655, A154656, A154657, A154658, A154659.
Rows n=1-2 give: A000012, A040000.
Main diagonal gives A000142.
A(2n,n) gives A048163(n+1).
A(2n+1,n) gives A092552(n+1).
A(n,floor(n/2)) gives A306267.
A(n+2,n) gives A001564.
Cf. A130152.

A[0, _] = 1;
A[n_ /; n > 0, k_] := A[n, k] = Permanent[Table[If[Abs[i - j] <= k, 1, 0], {i, 1, n}, {j, 1, n}]];
Table[A[n - k, k], {n, 0, 12}, {k, n, 0, -1 }] // Flatten (* Jean-François Alcover, Oct 18 2021, after Alois P. Heinz in A130152 *)

A(n,k) = Sum_{j=0..k} A130152(n,j) for n > 0, A(0,k) = 1.

A220062 Number A(n,k) of n length words over k-ary alphabet, where neighboring letters are neighbors in the alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 4, 2, 0, 0, 1, 5, 6, 6, 2, 0, 0, 1, 6, 8, 10, 8, 2, 0, 0, 1, 7, 10, 14, 16, 12, 2, 0, 0, 1, 8, 12, 18, 24, 26, 16, 2, 0, 0, 1, 9, 14, 22, 32, 42, 42, 24, 2, 0, 0, 1, 10, 16, 26, 40, 58, 72, 68, 32, 2, 0, 0

Offset: 0

Alois P. Heinz, Dec 03 2012

Equivalently, the number of walks of length n-1 on the path graph P_k. - Andrew Howroyd, Apr 17 2017

			A(5,3) = 12: there are 12 words of length 5 over 3-ary alphabet {a,b,c}, where neighboring letters are neighbors in the alphabet: ababa, ababc, abcba, abcbc, babab, babcb, bcbab, bcbcb, cbaba, cbabc, cbcba, cbcbc.
Square array A(n,k) begins:
  1,  1,  1,  1,  1,   1,   1,   1, ...
  0,  1,  2,  3,  4,   5,   6,   7, ...
  0,  0,  2,  4,  6,   8,  10,  12, ...
  0,  0,  2,  6, 10,  14,  18,  22, ...
  0,  0,  2,  8, 16,  24,  32,  40, ...
  0,  0,  2, 12, 26,  42,  58,  74, ...
  0,  0,  2, 16, 42,  72, 104, 136, ...
  0,  0,  2, 24, 68, 126, 188, 252, ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0, 2-10 give: A000007, A040000, A029744(n+2) for n>0, A006355(n+3) for n>0, A090993(n+1) for n>0, A090995(n-1) for n>2, A129639, A153340, A153362, A153360.
Rows 0-6 give: A000012, A001477, A005843(k-1) for k>0, A016825(k-2) for k>1, A008590(k-2) for k>2, A113770(k-2) for k>3, A063164(k-2) for k>4.
Main diagonal gives: A102699.
Cf. A198632, A188866, A276562, A208727, A208671.

b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i=0, add(b(n-1, j, k), j=1..k),
      `if`(i>1, b(n-1, i-1, k), 0)+
      `if`(i b(n, 0, k):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i == 0, Sum[b[n-1, j, k], {j, 1, k}], If[i>1, b[n-1, i-1, k], 0] + If[iJean-François Alcover, Jan 19 2015, after Alois P. Heinz *)

TransferGf(m,u,t,v,z)=vector(m,i,u(i))*matsolve(matid(m)-z*matrix(m,m,i,j,t(i,j)),vectorv(m,i,v(i)));
ColGf(m,z)=1+z*TransferGf(m, i->1, (i,j)->abs(i-j)==1, j->1, z);
a(n,k)=Vec(ColGf(k,x) + O(x^(n+1)))[n+1];
for(n=0, 7, for(k=0, 7, print1( a(n,k), ", ") ); print(); );
\\ Andrew Howroyd, Apr 17 2017

cp's OEIS Frontend

A034182 Number of not-necessarily-symmetric n X 2 crossword puzzle grids.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A171861 Expansion of x*(1+x+x^2) / ( (x-1)*(x^3+x^2-1) ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A186021 a(n) = Bell(n)*(2 - 0^n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A040006 Continued fraction for sqrt(10).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A113413 A Riordan array of coordination sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Sage

Formula

A158799 a(0)=1, a(1)=2, a(n)=3 for n >= 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A171861 Expansion of x(1+x+x^2) / ( (x-1)(x^3+x^2-1) ).