A005317 -id:A005317 - cp's OEIS frontend

A259776 Number A(n,k) of permutations p of [n] with no fixed points and displacement of elements restricted by k: 1 <= |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 4, 0, 0, 1, 0, 1, 2, 9, 6, 1, 0, 1, 0, 1, 2, 9, 24, 13, 0, 0, 1, 0, 1, 2, 9, 44, 57, 24, 1, 0, 1, 0, 1, 2, 9, 44, 168, 140, 45, 0, 0, 1, 0, 1, 2, 9, 44, 265, 536, 376, 84, 1, 0

Offset: 0

Alois P. Heinz, Jul 05 2015

Conjecture: Column k > 0 has a linear recurrence (with constant coefficients) of order = A005317(k) = (2^k + C(2*k,k))/2. - Vaclav Kotesovec, Jul 07 2015
From Vaclav Kotesovec, Jul 07 2015: (Start) For k > 1, A(n,k) ~ c(k) * d(k)^n
k  c(k)                                  d(k)
2  0.2840509026895102746628049030651...  1.8832035059135258641689474653620...
3  0.1678494211968692989590951622212...  2.6304414743928951523517253855770...
4  0.0973070675347403976445165510589...  3.3758288741377846847522960161445...
5  0.0552389982575367440330445172521...  4.1183824671958029895499633437571...
6  0.0309726120341077011398575643793...  4.8588208495640240252838055706997...
7  0.0172064353582683268003622374813...  5.5979905586951369718393573797927...
8  0.0094902135663231445267663712259...  6.3363450921766600853069060904417...
9  0.00520430877801650454166967632...    7.0741444217884608367707985...
10 0.0028405987031922...                 7.811548995086...
(End)

			Square array A(n,k) begins:
  1, 1,  1,   1,   1,    1,    1,    1, ...
  0, 0,  0,   0,   0,    0,    0,    0, ...
  0, 1,  1,   1,   1,    1,    1,    1, ...
  0, 0,  2,   2,   2,    2,    2,    2, ...
  0, 1,  4,   9,   9,    9,    9,    9, ...
  0, 0,  6,  24,  44,   44,   44,   44, ...
  0, 1, 13,  57, 168,  265,  265,  265, ...
  0, 0, 24, 140, 536, 1280, 1854, 1854, ...

Alois P. Heinz, Antidiagonals n = 0..36, flattened

Columns k=0-10 give: A000007, A059841, A033305, A079997, A259777, A259778, A259779, A259780, A259781, A259782, A259783.
Main diagonal gives: A000166.
Cf. A259784.

b:= proc(n, s, k) option remember; `if`(n=0, 1, `if`(n+k in s,
      b(n-1, (s minus {n+k}) union `if`(n-k>1, {n-k-1}, {}), k),
      add(`if`(j=n, 0, b(n-1, (s minus {j}) union
      `if`(n-k>1, {n-k-1}, {}), k)), j=s)))
    end:
A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), b(n, {$max(1, n-k)..n}, k)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, s_, k_] := b[n, s, k] = If[n==0, 1, If[MemberQ[s, n+k], b[n-1, Join[s ~Complement~ {n+k}] ~Union~ If[n-k>1, {n-k-1}, {}], k], Sum[If[j==n, 0, b[n -1, Join[s ~Complement~ {j}] ~Union~ If[n-k>1, {n-k-1}, {}], k]], {j, s}]] ];
A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]];
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

A(n,k) = Sum_{j=0..k} A259784(n,j).

A176332 Row sums of triangle A176331.

Original entry on oeis.org

1, 2, 5, 16, 56, 202, 741, 2752, 10318, 38972, 148070, 565280, 2166646, 8332378, 32136205, 124249856, 481433286, 1868972828, 7267804550, 28304698336, 110383060776, 431000853028, 1684754608210, 6592277745536, 25818887839956

Offset: 0

Paul Barry, Apr 15 2010

Hankel transform is A176333.

Let A(n) denote the n X n array such that the i-th row of this array is the sequence obtained by applying the partial sum operator i-1 times to the tuple ((sqrt(-1))^m, 1 <= m <= n). Then the negative of the real part of the (n, n)-entry of A(n) equals a(n-2) for all n > 2. - John M. Campbell, Jan 20 2019

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A000108, A176331, A176333.

Cf. A005317, A024718, A360185, A360211.

List([0..30], n -> Sum([0..n], k -> Sum([0..n], j -> (-1)^(n-j)* Binomial(j, n-k)*Binomial(j, k) ))) # G. C. Greubel, Feb 22 2019

[(&+[ (&+[(-1)^(n-j)*Binomial(j,n-k)*Binomial(j,k): j in [0..n]]): k in [0..n]]): n in [0..30]]; // G. C. Greubel, Feb 21 2019

a:=n->add(add(binomial(j,n-k)*binomial(j,k)*(-1)^(n-j),j=0..n),k=0..n): seq(a(n),n=0..30); # Muniru A Asiru, Jan 23 2019

f[n_]:= (-1)^n*Sum[Binomial[n+k, k] Cos[Pi(n+k)/2], {k, 0, n}]; Array[f, 24, 0] (* Robert G. Wilson v, Apr 02 2012 *)

{a(n) = sum(k=0,n, sum(j=0,n, (-1)^(n-j)*binomial(j,n-k)* binomial(j,k))) };vector(30, n, n--; a(n)) \\ G. C. Greubel, Feb 21 2019

a(n) = {my(v = vector(n, k, I^k)); for (k=1, n-1, v = vector(n, i, sum(j=1, i, v[j]));); -real(v[n]);} \\ Michel Marcus, Feb 25 2019

a(n) = sum(k=0, n\2, (-1)^k*binomial(2*n-2*k, n)); \\ Seiichi Manyama, Jan 29 2023

my(N=30, x='x+O('x^N)); Vec(1/(sqrt(1-4*x)*(1+x^2*(2/(1+sqrt(1-4*x)))^2))) \\ Seiichi Manyama, Jan 29 2023

[sum(sum((-1)^(n-j)*binomial(j,n-k)*binomial(j,k) for j in (0..n)) for k in (0..n)) for n in (0..30)] # G. C. Greubel, Feb 21 2019

a(n) = Sum_{k=0..n} Sum_{j=0..n} binomial(j,n-k)*binomial(j,k)*(-1)^(n-j).
Logarithm g.f.: arctan(x*C(x)) = Sum_{n>=1} a(n)/n*x^n, where C(x) = (1-sqrt(1-4*x))/(2*x) (A000108). - Vladimir Kruchinin, Aug 10 2010
Conjecture: 6*n*a(n) + 2*(-17*n+10)*a(n-1) + (47*n-60)*a(n-2) + 10*(-3*n+5)*a(n-3) + 4*(2*n-5)*a(n-4) = 0. - R. J. Mathar, Nov 24 2012
Recurrence: 2*n*(5*n-8)*a(n) = 2*(25*n^2 - 50*n + 18)*a(n-1) - (45*n^2 - 92*n + 36)*a(n-2) + 2*(2*n-3)*(5*n-3)*a(n-3). - Vaclav Kotesovec, Feb 12 2014
a(n) ~ 4^(n+1) / (5*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 12 2014
From Seiichi Manyama, Jan 29 2023: (Start)
a(n) = Sum_{k=0..floor(n/2)} (-1)^k * binomial(2*n-2*k,n).
G.f.: 1 / ( sqrt(1-4*x) * (1 + x^2 * c(x)^2) ), where c(x) is the g.f. of A000108. (End)
a(n) = [x^n] 1/((1+x^2) * (1-x)^(n+1)). - Seiichi Manyama, Apr 08 2024

A108958 Number of unordered pairs of distinct length-n binary words having the same number of 1's.

Original entry on oeis.org

0, 1, 6, 27, 110, 430, 1652, 6307, 24054, 91866, 351692, 1350030, 5196204, 20050108, 77542376, 300507427, 1166737574, 4537436578, 17672369756, 68922740122, 269127888644, 1052047384708, 4116711169496, 16123793452942, 63205286441660, 247959232919620, 973469645715192

Offset: 1

Jeffrey Shallit, Jul 22 2005

Equals row sums of triangle A143418, starting with a(2). - Gary W. Adamson, Aug 14 2008
In coupled systems of n spin 1/2 particles (magnetic resonance) where the spin state of the i-th particle can be coded as 0 (Sz_i=-1/2) or 1 (Sz_i=+1/2), number of distinct (vw). - Stanislav Sykora, Jun 07 2012
a(n) is the number of lattice paths from (0,0) to (n,n) using E(1,0) and N(0,1) as steps that horizontally cross the diagonal y = x with odd many times. For example, a(2) = 1 because there is only one path that horizontally crosses the diagonal with odd many times, namely, NEEN. - Ran Pan, Feb 01 2016

			a(3) = 6 because the pairs are {001,010}, {001,100}, {010,100}, {011,101}, {011,110}, {101,110}.

Michael De Vlieger, Table of n, a(n) for n = 1..1664
Mircea Merca, A Special Case of the Generalized Girard-Waring Formula, J. Integer Sequences, Vol. 15 (2012), Article 12.5.7.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.
Stanislav Sýkora, Magnetic Resonance on OEIS, Stan's NMR Blog (Dec 31, 2014), Retrieved Nov 12, 2019.

Cf. A005317, A011782, A088218, A143418.

[Binomial(2*n,n)-(2^n+Binomial(2*n,n))/2: n in [1..30]]; // Vincenzo Librandi, Feb 01 2016

with(combinat) a:= proc(n) add(binomial(binomial(n,k), 2), k=0..n) end;

Table[Binomial[2 n, n] - (2^n + Binomial[2 n, n])/2, {n, 30}] (* Vincenzo Librandi, Feb 01 2016 *)

a(n)=binomial(2*n-1,n-1)-2^(n-1) \\ Charles R Greathouse IV, Feb 01 2016

from math import comb
def A108958(n): return comb((n<<1)-1,n-1)-(1<Chai Wah Wu, Sep 23 2022

a(n) = Sum_{k=0..n} binomial(binomial(n, k), 2).
From Vladeta Jovovic, Jul 24 2005: (Start)
a(n) = binomial(2*n-1, n-1)-2^(n-1) = A088218(n) - A011782(n).
E.g.f.: exp(2*x)*(BesselI(0, 2*x)-1)/2. (End)
a(n) = (1/2)*Sum_{i+j>n,0<=i,j<=n} binomial(i+j,i). - Benoit Cloitre, May 26 2006
Conjecture: n*(n-2)*a(n) +2*(-3*n^2+7*n-3)*a(n-1) +4*(n-1)*(2*n-3) *a(n-2)=0. - R. J. Mathar, Apr 04 2012
a(n) = Sum_{0Mircea Merca, Apr 05 2012
a(n) = binomial(2*n,n) - A005317(n), - Ran Pan, Feb 01 2016
a(n) = 1/2*Sum_{k=1..n} binomial(n,k)^2 - binomial(n,k).  - Gerry Martens, Oct 09 2022
a(n) ~ 2^(2*n-1)/sqrt(n*Pi). - Stefano Spezia, Apr 17 2024

A259783 Number of permutations p of [n] with no fixed points and displacement of elements restricted by ten: 1 <= |p(i)-i| <= 10.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 145510740, 1314803006, 11013531389, 87155940048, 663875231097, 4947896842392, 36563337902968, 270617834212996, 2021217246729905, 15317729587621252, 118254506519672137, 924131987256868248

Offset: 0

Alois P. Heinz, Jul 05 2015

nonn

Conjecture: Column k > 0 of A259776 has a linear recurrence (with constant coefficients) of order = A005317(k) = (2^k + C(2*k,k))/2. For k=10 is conjectured recurrence order 92890. - Vaclav Kotesovec, Jul 07 2015

Alois P. Heinz, Table of n, a(n) for n = 0..175

Column k=10 of A259776.

Cf. A260216.

A191993 a(n) = 3^(n-1) + C(2*n, n)/2.

Original entry on oeis.org

2, 6, 19, 62, 207, 705, 2445, 8622, 30871, 112061, 411765, 1529225, 5731741, 21652623, 82341729, 314889102, 1209849831, 4666707813, 18060052389, 70085525877, 272615721621, 1062509835063, 4148096423409, 16217945020377, 63487732755357, 248806555083495

Offset: 1

Mircea Merca, Jun 21 2011

			a(5) = 3^4 + C(10,5)/2 = 81 + 126 = 207.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

Cf. A000244, A001700, A005317.

Maple
```
seq(3^(n-1)+binomial(2*n-1,n),n=1..20)
```

Table[3^(n-1)+Binomial[2n,n]/2,{n,30}] (* Harvey P. Dale, Dec 27 2011 *)

a(n)=3^(n-1)+binomial(n+n,n)/2 \\ Charles R Greathouse IV, Jun 21 2011

a(n) = A000244(n-1) + A001700(n-1).
a(n) = Sum_{k=0..floor(n/3)} (-1)^k*C(2*n, n-3*k).
G.f.: ((x-1)*(4*x-1) + sqrt((1-4*x)*(3*x-1)^2))/(2*(4*x-1)*(3*x-1)) - 1.
Conjecture: n*(n-3)*a(n) - (7*n^2 -23*n +12)*a(n-1) +6*(2*n-3)*(n-2)*a(n-2)=0. - R. J. Mathar, Oct 18 2017
E.g.f.: (exp(2*x)*(2*exp(x) + 3*BesselI(0,2*x)) - 5)/6. - Stefano Spezia, Aug 22 2025

A107105 Triangle, read by rows, where T(n,k) = C(n,k)*(C(n,k) + 1)/2, n>=k>=0.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 21, 10, 1, 1, 15, 55, 55, 15, 1, 1, 21, 120, 210, 120, 21, 1, 1, 28, 231, 630, 630, 231, 28, 1, 1, 36, 406, 1596, 2485, 1596, 406, 36, 1, 1, 45, 666, 3570, 8001, 8001, 3570, 666, 45, 1, 1, 55, 1035, 7260, 22155, 31878, 22155, 7260

Offset: 0

Paul D. Hanna, May 21 2005

Replace each number x in Pascal's triangle by x(x+1)/2. - Charlie Marion, May 31 2013

			Triangle begins:
1;
1,1;
1,3,1;
1,6,6,1;
1,10,21,10,1;
1,15,55,55,15,1;
1,21,120,210,120,21,1;
1,28,231,630,630,231,28,1; ...

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Cf. A005317 (row sums), A107597 (antidiagonal sums).

Table[Binomial[n,k] (Binomial[n,k]+1)/2,{n,0,10},{k,0,n}]//Flatten (* Harvey P. Dale, Jul 20 2025 *)

T(n,k)=binomial(n,k)*(binomial(n,k)+1)/2

n-th row sum equals A005317(n) = (C(2n, n) + 2^n)/2.

A360211 a(n) = Sum_{k=0..floor(n/2)} (-1)^k * binomial(2n-3k,n-2*k).

Original entry on oeis.org

1, 2, 5, 17, 61, 221, 812, 3021, 11344, 42899, 163146, 623320, 2390653, 9198879, 35494701, 137290466, 532149805, 2066501909, 8038146035, 31312535610, 122140123201, 477002869614, 1864912495716, 7298427590543, 28588888586743, 112080607196843, 439744801379594

Offset: 0

Seiichi Manyama, Jan 30 2023

nonn

Cf. A005317, A024718, A176332, A360185.
Cf. A000108, A176287.
Cf. A026641, A360212.

A360211 := proc(n)
    add((-1)^k*binomial(2*n-3*k,n-2*k),k=0..floor(n/2)) ;
end proc:
seq(A360211(n),n=0..40) ; # R. J. Mathar, Mar 02 2023

a(n) = sum(k=0, n\2, (-1)^k*binomial(2*n-3*k, n-2*k));

my(N=30, x='x+O('x^N)); Vec(1/(sqrt(1-4*x)*(1+2*x^2/(1+sqrt(1-4*x)))))

G.f.: 1 / ( sqrt(1-4*x) * (1 + x^2 * c(x)) ), where c(x) is the g.f. of A000108.
a(n) ~ 2^(2*n+3) / (9*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 18 2023
D-finite with recurrence 2*n*a(n) +(-5*n+2)*a(n-1) +(-11*n+12)*a(n-2) +2*(-n+5)*a(n-3) +(-7*n+2)*a(n-4) +2*(-2*n+5)*a(n-5)=0. - R. J. Mathar, Mar 02 2023

A307668 A(n,k) = Sum_{j=0..floor(n/k)} (-1)^jbinomial(2n,k*j+n), square array A(n,k) read by antidiagonals, for n >= 0, k >= 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 2, 5, 10, 1, 2, 6, 14, 35, 1, 2, 6, 19, 43, 126, 1, 2, 6, 20, 62, 142, 462, 1, 2, 6, 20, 69, 207, 494, 1716, 1, 2, 6, 20, 70, 242, 705, 1780, 6435, 1, 2, 6, 20, 70, 251, 858, 2445, 6563, 24310, 1, 2, 6, 20, 70, 252, 912, 3068, 8622, 24566, 92378

Offset: 0

Seiichi Manyama, Apr 20 2019

			Square array begins:
      1,    1,    1,     1,     1,     1,     1, ...
      1,    2,    2,     2,     2,     2,     2, ...
      3,    5,    6,     6,     6,     6,     6, ...
     10,   14,   19,    20,    20,    20,    20, ...
     35,   43,   62,    69,    70,    70,    70, ...
    126,  142,  207,   242,   251,   252,   252, ...
    462,  494,  705,   858,   912,   923,   924, ...
   1716, 1780, 2445,  3068,  3341,  3418,  3431, ...
   6435, 6563, 8622, 11051, 12310, 12750, 12854, ...

Columns 1-2 give A088218, A005317.

Cf. A306914, A307039, A307394, A307665.

T[n_, k_] := Sum[(-1)^j*Binomial[2*n, k*j + n], {j, 0, Floor[n/k]}]; Table[T[n - k, k], {n, 0, 11}, {k, n, 1, -1}] // Flatten (* Amiram Eldar, May 13 2021*)

cp's OEIS Frontend

A259776 Number A(n,k) of permutations p of [n] with no fixed points and displacement of elements restricted by k: 1 <= |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A176332 Row sums of triangle A176331.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Sage

Formula

A108958 Number of unordered pairs of distinct length-n binary words having the same number of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A259783 Number of permutations p of [n] with no fixed points and displacement of elements restricted by ten: 1 <= |p(i)-i| <= 10.

Views

Author

Keywords

Comments

Links

Crossrefs

A191993 a(n) = 3^(n-1) + C(2*n, n)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A107105 Triangle, read by rows, where T(n,k) = C(n,k)*(C(n,k) + 1)/2, n>=k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A360211 a(n) = Sum_{k=0..floor(n/2)} (-1)^k * binomial(2*n-3*k,n-2*k).

Views

Author

A360211 a(n) = Sum_{k=0..floor(n/2)} (-1)^k * binomial(2n-3k,n-2*k).

A307668 A(n,k) = Sum_{j=0..floor(n/k)} (-1)^jbinomial(2n,k*j+n), square array A(n,k) read by antidiagonals, for n >= 0, k >= 1.