A112575 -id:A112575 - cp's OEIS frontend

A033305 Number of permutations (p1,...,pn) such that 1 <= |pk - k| <= 2 for all k.

1, 0, 1, 2, 4, 6, 13, 24, 45, 84, 160, 300, 565, 1064, 2005, 3774, 7108, 13386, 25209, 47472, 89401, 168360, 317056, 597080, 1124425, 2117520, 3987721, 7509690, 14142276, 26632782, 50154949, 94451976, 177872293

Offset: 0

N. J. A. Sloane

Lehmer, D. H.; Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.
R. P. Stanley, Enumerative Combinatorics I, p. 252, Example 4.7.16.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,-1).

Column k=2 of A259776.

Cf. A112575, A183324, A260074.

I:=[1,0,1,2,4]; [n le 5 select I[n] else Self(n-1) +Self(n-2) +Self(n-3) +Self(n-4) -Self(n-5): n in [1..41]]; // G. C. Greubel, Jan 14 2022

LinearRecurrence[{1,1,1,1,-1},{1,0,1,2,4},40] (* Harvey P. Dale, Aug 28 2012 *)

h(n) := sum(sum(binomial(k,r) *sum(binomial(r,m) *sum(binomial(m,j) *binomial(j,n-m-k-j-r) *(-1)^(n-m-k-j-r), j,0,m), m,0,r), r,0,k), k,1,n); a(n):=h(n)-h(n-1); /* Vladimir Kruchinin, Sep 10 2010 */

[( (1-x)/((1+x)*(1-2*x+x^2-2*x^3+x^4)) ).series(x,n+1).list()[n] for n in (0..40)] # G. C. Greubel, Jan 14 2022

G.f.: (1-x)/((1+x)*(1 - 2*x + x^2 - 2*x^3 + x^4)).
a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) - a(n-5).
a(n) = h(n) - h(n-1), n>0, h(n) = Sum_{k=1..n} (Sum_{r=0..k} (C(k,r)*Sum_{m=0..r}(C(r,m)*Sum_{j=0..m} C(m,j)*C(j,n-m-k-j-r)*(-1)^(n-m-k-j-r) ))). - Vladimir Kruchinin, Sep 10 2010
Limit_{n -> oo} a(n)/a(n-1) = (1 + sqrt(2) + sqrt(2*sqrt(2)-1)) /2 = 1.88320350591... for n>2. Limit_{n -> oo} a(n-1)/a(n) = (1 + sqrt(2) - sqrt(2*sqrt(2)-1)) /2 = 0.53101005645... for n>0. - Tim Monahan, Aug 09 2011
7*a(n) = 2*(-1)^n - 8*A112575(n) - 2*A112575(n-2) + 6*A112575(n-1) + 5*A112575(n+1). - R. J. Mathar, Sep 27 2013
Empirical: a(n) + a(n+1) = A183324(n). - R. J. Mathar, Sep 27 2013

New description from Max Alekseyev, Jul 09 2006

A367400 Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.

Original entry on oeis.org

1, 2, 4, 7, 13, 25, 47, 88, 166, 313, 589, 1109, 2089, 3934, 7408, 13951, 26273, 49477, 93175, 175468, 330442, 622289, 1171897, 2206921, 4156081, 7826746, 14739356, 27757207, 52272469, 98439697, 185381983, 349112000, 657448942, 1238110153

Offset: 0

Gus Wiseman, Nov 21 2023

			The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is counted under a(8).
The a(0) = 1 through a(4) = 13 subsets:
  {}  {}   {}     {}     {}
      {1}  {1}    {1}    {1}
           {2}    {2}    {2}
           {1,2}  {3}    {3}
                  {1,2}  {4}
                  {1,3}  {1,2}
                  {2,3}  {1,3}
                         {1,4}
                         {2,3}
                         {2,4}
                         {3,4}
                         {1,3,4}
                         {2,3,4}

The version containing n appears to be A112575.
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398
strict:      A367214   A367215   A367220   A367221   A367395   A367399
subsets:     A367216   A367217   A367222   A367223   A367396   A367400*
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A002865 counts partitions whose length is a part, complement A229816.
A364534 counts sum-full subsets.
A088809 and A093971 count subsets containing semi-sums.
A236912 counts partitions with no semi-sum of the parts, ranks A364461.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A237113, A237667, A238628, A304792, A363225, A364272, A365543, A365658, A365918, A366131, A366740.

Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#, {2}], Length[#]]&]], {n,0,10}]

from itertools import combinations
def A367400(n): return (n*(n+1)>>1)+1+sum(1 for k in range(3,n+1) for w in (set(d) for d in combinations(range(1,n+1),k)) if not any({a,k-a}<=w for a in range(1,k+1>>1))) # Chai Wah Wu, Nov 21 2023

Conjectures from Chai Wah Wu, Nov 21 2023: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n > 3.
G.f.: (-x^3 + x^2 + 1)/(x^4 - 2*x^3 + x^2 - 2*x + 1). (End)

a(18)-a(33) from Chai Wah Wu, Nov 21 2023

A118870 Number of binary sequences of length n with no subsequence 0101.

Original entry on oeis.org

1, 2, 4, 8, 15, 28, 53, 100, 188, 354, 667, 1256, 2365, 4454, 8388, 15796, 29747, 56020, 105497, 198672, 374140, 704582, 1326871, 2498768, 4705689, 8861770, 16688516, 31427872, 59185079, 111457548, 209897245, 395279228, 744391228, 1401840170

Offset: 0

Emeric Deutsch, May 03 2006

nonn

Column 0 of A118869 and column 10 of A209972.

			a(5) = 28 because among the 32 (=2^5) binary sequences of length 5 only 01010, 01011, 00101 and 10101 contain the subsequence 0101.

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

Cf. A000071, A000073, A005251, A112575, A118869, A209972, A332052.

[n le 4 select 2^(n-1) else 2*Self(n-1) -Self(n-2) +2*Self(n-3) -Self(n-4): n in [1..41]]; // G. C. Greubel, Jan 14 2022

a[0]:=1:a[1]:=2:a[2]:=4:a[3]:=8: for n from 4 to 35 do a[n]:=2*a[n-1]-a[n-2]+2*a[n-3]-a[n-4] od: seq(a[n], n=0..35);

CoefficientList[Series[(1+x^2)/(1-2x+x^2-2x^3+x^4),{x,0,40}],x] (* Geoffrey Critzer, Nov 28 2013 *)

@CachedFunction
def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
def A118870(n): return A112575(n-1) + A112575(n+1)
[A118870(n) for n in (0..40)] # G. C. Greubel, Jan 14 2022

G.f.: (1 +x^2)/(1 -2*x +x^2 -2*x^3 +x^4).
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n>=4.
a(n) = A112575(n-1) + A112575(n+1). - R. J. Mathar, Dec 10 2011

A099854 A Chebyshev transform of A048739 related to the knot 8_5.

Original entry on oeis.org

1, 3, 7, 14, 26, 48, 90, 170, 321, 605, 1139, 2144, 4037, 7603, 14319, 26966, 50782, 95632, 180094, 339154, 638697, 1202797, 2265111, 4265664, 8033113, 15127987, 28489079, 53650734, 101035250, 190269936, 358317010, 674783850, 1270755313

Offset: 0

Paul Barry, Oct 27 2004

The g.f. is a transformation of the g.f. 1/((1-x)*(1-2*x-x^2)) of A048739 under the Chebyshev transform G(x)->(1/(1+x^2))*G(x/(1+x^2)). The denominator of the g.f. is a parameterization of the Alexander polynomial of the knot 8_5.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-4,5,-4,3,-1).

Cf. A010892, A048739, A099846, A112575.

R:=PowerSeriesRing(Integers(), 50); Coefficients(R!( (1+x^2)^2/((1-x+x^2)*(1-2*x+x^2-2*x^3+x^4)) )); // G. C. Greubel, Apr 20 2023

LinearRecurrence[{3,-4,5,-4,3,-1}, {1,3,7,14,26,48}, 51] (* G. C. Greubel, Apr 20 2023 *)

def A099854_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x^2)^2/((1-x+x^2)*(1-2*x+x^2-2*x^3+x^4)) ).list()
A099854_list(50) # G. C. Greubel, Apr 20 2023

G.f.: (1 + x^2)^2/(1 - 3*x + 4*x^2 - 5*x^3 + 4*x^4 - 3*x^5 + x^6).
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*A048739(n-2*k).
a(n) = Sum_{k=0..n} A099846(n-k)*binomial(2, k/2)*(1+(-1)^k)/2.
a(n) = (1/2)*(3*A112575(n+1) + A112575(n) + 3*A112575(n-1) - A010892(n)). - G. C. Greubel, Apr 20 2023

A118871 Number of binary sequences of length n containing exactly one subsequence 0101.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 10, 24, 57, 128, 278, 596, 1260, 2628, 5430, 11136, 22683, 45936, 92574, 185764, 371347, 739840, 1469580, 2911224, 5753048, 11343800, 22322444, 43845120, 85973013, 168314604, 329041842, 642385248, 1252552077, 2439430272, 4745767138, 9223159852

Offset: 0

Emeric Deutsch, May 03 2006

nonn

With only two 0's at the beginning, the convolution of A112575 with itself. Column 1 of A118869.

			a(5) = 4 because we have 01010, 01011, 00101 and 10101.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,8,-11,8,-6,4,-1).

Cf. A112575, A118430, A118869, A118870.

R:=PowerSeriesRing(Integers(), 40); [0,0,0,0] cat Coefficients(R!( x^4/(1 -2*x +x^2 -2*x^3 +x^4)^2 )); // G. C. Greubel, Jan 14 2022

g:=z^4/(1-2*z+z^2-2*z^3+z^4)^2: gser:=series(g,z=0,40): seq(coeff(gser, z, n), n=0..35);

LinearRecurrence[{4,-6,8,-11,8,-6,4,-1}, {0,0,0,0,1,4,10,24}, 40] (* G. C. Greubel, Jan 14 2022 *)

@CachedFunction
def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
def A118871(n): return sum( A112575(j+1)*A112575(n-j-3) for j in (0..n-4) )
[A118871(n) for n in (0..40)] # G. C. Greubel, Jan 14 2022

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

a(n) = Sum_{j=0..n-4} A112575(j+1)*A112575(n-j-3). - G. C. Greubel, Jan 14 2022

cp's OEIS Frontend

A033305 Number of permutations (p1,...,pn) such that 1 <= |pk - k| <= 2 for all k.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

SageMath

Formula

Extensions

A367400 Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A118870 Number of binary sequences of length n with no subsequence 0101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A099854 A Chebyshev transform of A048739 related to the knot 8_5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A118871 Number of binary sequences of length n containing exactly one subsequence 0101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula