A003520 -id:A003520 - cp's OEIS frontend

A193147 Expansion of 1/(1 - x - 2*x^3 - x^5).

1, 1, 1, 3, 5, 8, 15, 26, 45, 80, 140, 245, 431, 756, 1326, 2328, 4085, 7168, 12580, 22076, 38740, 67985, 119305, 209365, 367411, 644761, 1131476, 1985603, 3484490, 6114853, 10730820, 18831276, 33046585, 57992715, 101770120, 178594110, 313410816, 549997641

Offset: 0

Johannes W. Meijer, Jul 20 2011

The Ze3 sums, see A180662 for the definition of these sums, of the "Races with Ties" triangle A035317 equal this sequence.

Number of tilings of a 5 X 2n rectangle with 5 X 1 pentominoes. - M. Poyraz Torcuk, Dec 18 2021

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

Bisection of A003520.

Cf. A035317, A180662, A373578.

A193147 := proc(n) option remember: if n>=-4 and n<=-1 then 0 elif n=0 then 1 else procname(n-1) + 2*procname(n-3) + procname(n-5) fi: end: seq(A193147(n), n=0..32);

Series[1/(1 - x - 2*x^3 - x^5), {x, 0, 32}] // CoefficientList[#, x]& (* Jean-François Alcover, Apr 02 2015 *)

a(n):=sum(sum(binomial(j,3*n-5*m+2*j)*binomial(2*m-n,j)*2^(3*n-5*m+2*j), j,0,2*m-n),m,floor((n+1)/2),n); /* Vladimir Kruchinin, Mar 10 2013 */

G.f.: 1/(1-x-2*x^3-x^5) = -1 / ( (1+x+x^2)*(x^3-x^2+2*x-1) ).
a(n) = a(n-1) + 2*a(n-3) + a(n-5) with a(n) = 0 for n= -4, -3, -2, -1 and a(0) = 1.
a(n) = (5*b(n+1) - 4*b(n) + 3*b(n-1) + 2*c(n) + 3*c(n-1))/7 with b(n) = A005314(n) and c(n) = A049347(n).
G.f.: 1 + x/(U(0)-x) where G(k)= 1 - x^2*(k+1)/(1 - 1/(1 + (k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2012
a(n) = Sum_{m=floor((n+1)/2)..n} Sum_{j=0..2*m-n} C(j,3*n-5*m+2*j) * C(2*m-n,j) * 2^(3*n-5*m+2*j). - Vladimir Kruchinin, Mar 10 2013
With offset 1, the INVERT transform of (1 + 2x^2 + x^4). - Gary W. Adamson, Mar 30 2017
a(n) = Sum_{k=0..floor(2*n/5)} binomial(2*n-4*k,k). - Seiichi Manyama, Jun 14 2024

A369836 Number of compositions of 5*n into parts 1 and 5.

Original entry on oeis.org

1, 2, 8, 34, 140, 571, 2328, 9496, 38740, 158045, 644761, 2630364, 10730820, 43777405, 178594110, 728591751, 2972359720, 12126025705, 49469281395, 201814663875, 823322219501, 3358821723401, 13702634402876, 55901207340276, 228054320813276, 930369409108152

Offset: 0

Seiichi Manyama, Feb 03 2024

nonn

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-10,10,-5,1).

Cf. A079675, A369837, A369838, A369839.
Cf. A099131, A369840, A369845.
Cf. A003520.

LinearRecurrence[{6, -10, 10, -5, 1}, {1, 2, 8, 34, 140}, 50] (* Paolo Xausa, Mar 15 2024 *)

a(n) = sum(k=0, n, binomial(n+4*k, n-k));

a(n) = A003520(5*n).
a(n) = Sum_{k=0..n} binomial(n+4*k,n-k).
a(n) = 6*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5).
G.f.: (1-x)^4/((1-x)^5 - x).

A099235 A quadrisection of 1/(1-x-x^5).

Original entry on oeis.org

1, 1, 5, 15, 45, 140, 431, 1326, 4085, 12580, 38740, 119305, 367411, 1131476, 3484490, 10730820, 33046585, 101770120, 313410816, 965178576, 2972359720, 9153665985, 28189589705, 86812537085, 267347509271, 823322219501

Offset: 0

Paul Barry, Oct 08 2004

A row of A099233.

The number of ways to place non-overlapping Young diagrams of shape (2,1,1,1) on an 7 by n rectangle. - Per Alexandersson, Jun 23 2025

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,4,6,4,1).

Cf. A003520, A099233.

Take[CoefficientList[Series[1/(1-x-x^5),{x,0,100}],x],{1,-1,4}] (* or *) LinearRecurrence[{1,4,6,4,1},{1,1,5,15,45},30] (* Harvey P. Dale, Mar 06 2015 *)

G.f.: 1/(1-x*(1+x)^4).
a(n) = Sum_{k=0..n} binomial(4(n-k), k).
a(n) = a(n-1) + 4*a(n-2) + 6*a(n-3) + 4*a(n-4) + a(n-5).
a(n) = A003520(4n).

A141539 Square array A(n,k) of numbers of length n binary words with at least k "0" between any two "1" digits (n,k >= 0), read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 3, 5, 16, 1, 2, 3, 4, 8, 32, 1, 2, 3, 4, 6, 13, 64, 1, 2, 3, 4, 5, 9, 21, 128, 1, 2, 3, 4, 5, 7, 13, 34, 256, 1, 2, 3, 4, 5, 6, 10, 19, 55, 512, 1, 2, 3, 4, 5, 6, 8, 14, 28, 89, 1024, 1, 2, 3, 4, 5, 6, 7, 11, 19, 41, 144, 2048, 1, 2, 3, 4, 5, 6, 7, 9, 15, 26, 60, 233, 4096

Offset: 0

Alois P. Heinz, Aug 15 2008

A(n,k+1) = A(n,k) - A143291(n,k).
From Gary W. Adamson, Dec 19 2009: (Start)
Alternative method generated from variants of an infinite lower triangle T(n) = A000012 = (1; 1,1; 1,1,1; ...) such that T(n) has the leftmost column shifted up n times. Then take lim_{k->infinity} T(n)^k, obtaining a left-shifted vector considered as rows of an array (deleting the first 1) as follows:
  1, 2, 4, 8, 16, 32, 64, 128, 256, ... = powers of 2
  1, 1, 2, 3,  5,  8, 13,  21,  34, ... = Fibonacci numbers
  1, 1, 1, 2,  3,  4,  6,   9,  13, ... = A000930
  1, 1, 1, 1,  2,  3,  4,   5,   7, ... = A003269
  ... with the next rows A003520, A005708, A005709, ... such that beginning with the Fibonacci row, the succession of rows are recursive sequences generated from a(n) = a(n-1) + a(n-2); a(n) = a(n-1) + a(n-3), ... a(n) = a(n-1) + a(n-k); k = 2,3,4,... Last, columns going up from the topmost 1 become rows of triangle A141539. (End)

			A(4,2) = 6, because 6 binary words of length 4 have at least 2 "0" between any two "1" digits: 0000, 0001, 0010, 0100, 1000, 1001.
Square array A(n,k) begins:
    1,  1,  1,  1,  1,  1,  1,  1, ...
    2,  2,  2,  2,  2,  2,  2,  2, ...
    4,  3,  3,  3,  3,  3,  3,  3, ...
    8,  5,  4,  4,  4,  4,  4,  4, ...
   16,  8,  6,  5,  5,  5,  5,  5, ...
   32, 13,  9,  7,  6,  6,  6,  6, ...
   64, 21, 13, 10,  8,  7,  7,  7, ...
  128, 34, 19, 14, 11,  9,  8,  8, ...

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

Cf. column k=0: A000079, k=1: A000045(n+2), k=2: A000930(n+2), A068921, A078012(n+5), k=3: A003269(n+4), A017898(n+7), k=4: A003520(n+4), A017899(n+9), k=5: A005708(n+5), A017900(n+11), k=6: A005709(n+6), A017901(n+13), k=7: A005710(n+7), A017902(n+15), k=8: A005711(n+7), A017903(n+17), k=9: A017904(n+19), k=10: A017905(n+21), k=11: A017906(n+23), k=12: A017907(n+25), k=13: A017908(n+27), k=14: A017909(n+29).
Main diagonal gives A000027(n+1).
A(2n,n) gives A000217(n+1)
A(3n,n) gives A008778.
A(3n,2n) gives A034856(n+1).
A(2n,3n) gives A005408.
A(2^n-1,n) gives A376697.
See also A143291.

A:= proc(n, k) option remember;
      if k=0 then 2^n
    elif n<=k and n>=0 then n+1
    elif n>0 then A(n-1, k) +A(n-k-1, k)
    else          A(n+1+k, k) -A(n+k, k)
      fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

a[n_, k_] := a[n, k] = Which[k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, a[n-1, k] + a[n-k-1, k], True, a[n+1+k, k] - a[n+k, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

G.f. of column k: x^(-k)/(1-x-x^(k+1)).

A(n,k) = 2^n if k=0, otherwise A(n,k) = n+1 if n<=k, otherwise A(n,k) = A(n-1,k) + A(n-k-1,k).

A005376 a(n) = n - a(a(a(a(a(n-1))))).

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 16, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 25, 26, 26, 27, 27, 28, 29, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 38, 39, 40, 40, 41, 41, 42, 43, 43, 44, 45, 46, 46, 47, 48, 49, 50, 51, 51, 52, 52, 53, 54, 54

Offset: 0

N. J. A. Sloane

nonn

Conjecture: a(n) is approximately c*n, where c is the real root of x^5+x-1 = 0, c=0.754877666246692760049508896... - Benoit Cloitre, Nov 05 2002
Rule for n-th term: a(n) = An, where An denotes the Lamé antecedent to (or right shift of) n, which is found by replacing each Lm(i) (Lm(n) = Lm(n-1) + Lm(n-5): A003520) in the Zeckendorffian expansion (obtained by repeatedly subtracting the largest Lamé number you can until nothing remains) with Lm(i-1) (A1=1). For example: 58 = 45 + 11 + 2, so a(58) = 34 + 8 + 1 = 43. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002
From Pierre Letouzey, Mar 06 2025: (Start)
For all n >= 0, A005375(n) <= a(n) <= A100721(n) as proved in Letouzey-Li-Steiner link. Last equality A005375(n) = a(n) for n = 25; last equality a(n) = A100721(n) for n = 33.
a(n) = c*n + O(ln(n)), with c conjectured by Benoit Cloitre above; see Letouzey link and Dilcher 1993. (End)

Karl Dilcher, On a class of iterative recurrence relations, in G. E. Bergum, A. N. Philippou, and A. F. Horadam, editors, Applications of Fibonacci Numbers, vol. 5, p. 143-158, Springer, 1993.
Douglas R. Hofstadter, "Goedel, Escher, Bach", p. 137.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..10000
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, No. 1 (February 2012), pp. 11-18.
Nick Hobson, Python program for this sequence
Pierre Letouzey, Generalized Hofstadter functions G,H and beyond: numeration systems and discrepancy, arXiv:2502.12615 [cs.DM], 2025.
Pierre Letouzey, Shuo Li and Wolfgang Steiner, Pointwise order of generalized Hofstadter functions G,H and beyond, arXiv:2410.00529 [cs.DM], 2024.
Index entries for Hofstadter-type sequences
Index entries for sequences from "Goedel, Escher, Bach"

Cf. A005206, A005374, A005375, A100721.

H:=proc(n) option remember; if n=1 then 1 else n-H(H(H(H(H(n-1))))); fi; end proc;

a[n_]:= a[n]= If[n<1, 0, n -a[a[a[a[a[n-1]]]]]];
Table[a[n], {n, 0, 100}] (* G. C. Greubel, Nov 16 2022 *)

@CachedFunction # a = A005376
def a(n): return 0 if (n==0) else n - a(a(a(a(a(n-1)))))
[a(n) for n in range(101)] # G. C. Greubel, Nov 16 2022

a(n + a(a(a(a(n))))) = n (proved in Letouzey-Li-Steiner link). - Pierre Letouzey, Mar 06 2025

More terms from James Sellers, Jul 12 2000

A115423 Integers n > 0 such that n XOR 30n = 31n.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 33, 64, 65, 66, 128, 129, 130, 132, 256, 257, 258, 260, 264, 512, 513, 514, 516, 520, 528, 1024, 1025, 1026, 1028, 1032, 1040, 1056, 1057, 2048, 2049, 2050, 2052, 2056, 2064, 2080, 2081, 2112, 2113, 2114, 4096, 4097, 4098, 4100, 4104, 4112

Offset: 1

Paul D. Hanna, Jan 22 2006

nonn

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A003714 (Fibbinary numbers), A048715, A048718, A115422, A115424.

Select[Range[4200],BitXor[#,30#]==31#&] (* Harvey P. Dale, May 23 2017 *)

isok(n) = bitxor(n, 30*n) == 31*n; \\ Michel Marcus, Nov 11 2016

$cnt=0;
foreach(1..4_000){
    print ++$cnt," $\n" if ((30*$)^$)==31*$;
}
# Ivan Neretin, Nov 11 2016

This sequence also seems to satisfy:
3*a(n) XOR 21*a(n) = 22*a(n);
5*a(n) XOR 19*a(n) = 22*a(n);
6*a(n) XOR 19*a(n) = 21*a(n); etc.
a(A003520(n+4)) = 2^n. - Gheorghe Coserea, Nov 11 2016

A224811 Number of subsets of {1,2,...,n-8} without differences equal to 2, 4, 6 or 8.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 48, 64, 88, 121, 165, 225, 300, 400, 520, 676, 884, 1156, 1530, 2025, 2700, 3600, 4800, 6400, 8480, 11236, 14840, 19600, 25900, 34225, 45325, 60025, 79625, 105625, 140075, 185761, 246101, 326041, 431676, 571536, 756756, 1002001, 1327326, 1758276, 2329782, 3087049, 4090296, 5419584

Offset: 0

Vladimir Baltic, May 18 2013

nonn

Number of permutations (p(1), p(2), ..., p(n)) satisfying -k <= p(i)-i <= r and p(i)-i in the set I, i=1..n, with k=2, r=8, I={-2,0,8}.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 1, -1, 1, -1, 1, 2, -1, 1, 0, 0, -2, 1, -2, 0, 0, -1, 0, 0, 0, 0, 1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014, A217694,A224808-A224810.

CoefficientList[Series[(1 - x^10 - x^5 - x^7 + x^15)/((1 - x)*(1 + x)*(x^2 - x + 1)*(x^3 + x^2 - 1)*(x^6 - x^2 - 1)*(x^12 + x^10 + x^8 + 2*x^6 + x^4 + 1)), {x, 0, 50}], x] (* G. C. Greubel, Oct 28 2017 *)

x='x+O('x^50); Vec((1-x^10-x^5-x^7+x^15)/((1-x)*(1+x)*(x^2-x+1)*( x^3+x^2-1)*(x^6-x^2-1)*(x^12+x^10+x^8+2*x^6+x^4+1) )) \\ G. C. Greubel, Oct 28 2017

a(n) = a(n-1) +a(n-5) -a(n-6) +a(n-7) -a(n-8) +a(n-9) +2*a(n-10) -a(n-11) +a(n-12) -2*a(n-15) +a(n-16) -2*a(n-17) -a(n-20) +a(n-25).
G.f.: (1-x^10-x^5-x^7+x^15) / ( (1-x) *(1+x) *(x^2-x+1) *(x^3+x^2-1) *(x^6-x^2-1) *(x^12+x^10+x^8+2*x^6+x^4+1) ).
a(2*k) = (A003520(k))^2,
a(2*k+1) = A003520(k) * A003520(k+1)

A247703 Number T(n,k) of tilings of a 5 X n rectangle with pentominoes of any shape and exactly k pentominoes of shape I; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 4, 0, 1, 47, 8, 0, 1, 394, 94, 12, 0, 1, 2082, 1608, 282, 32, 0, 2, 15113, 8812, 3452, 512, 58, 0, 3, 111664, 73863, 22310, 5962, 790, 96, 0, 4, 789930, 631700, 218608, 45762, 9374, 1260, 142, 0, 5, 5388729, 5157928, 2067811, 491868, 81720, 15272, 1824, 196, 0, 6

Offset: 0

Alois P. Heinz, Sep 22 2014

Sum_{k>0} k * T(n,k) = A247736(n).

			T(5,5) = 2:
._._._._._.   ._________.
| | | | | |   |_________|
| | | | | |   |_________|
| | | | | |   |_________|
| | | | | |   |_________|
|_|_|_|_|_|   |_________| .
Triangle T(n,k) begins:
00 :      1;
01 :      0,      1;
02 :      4,      0,      1;
03 :     47,      8,      0,     1;
04 :    394,     94,     12,     0,    1;
05 :   2082,   1608,    282,    32,    0,    2;
06 :  15113,   8812,   3452,   512,   58,    0,   3;
07 : 111664,  73863,  22310,  5962,  790,   96,   0,  4;
08 : 789930, 631700, 218608, 45762, 9374, 1260, 142,  0,  5;

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

Row sums give A174249 or A233427(n,5).
Column k=0 gives A247767.
Main diagonal gives A003520.
Cf. A247736.

A369837 Number of compositions of 5*n-2 into parts 1 and 5.

Original entry on oeis.org

1, 5, 20, 80, 325, 1326, 5411, 22076, 90061, 367411, 1498887, 6114853, 24946129, 101770120, 415180936, 1693770328, 6909898016, 28189589705, 115002126790, 469162173146, 1913991948274, 7808313175575, 31854760257925, 129954540535600, 530161974821876

Offset: 1

Seiichi Manyama, Feb 03 2024

nonn

Paolo Xausa, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-10,10,-5,1).

Cf. A079675, A369836, A369838, A369839.

Cf. A003520, A055990.

LinearRecurrence[{6, -10, 10, -5, 1}, {1, 5, 20, 80, 325}, 50] (* Paolo Xausa, Mar 15 2024 *)

a(n) = sum(k=0, n, binomial(n+2+4*k, n-1-k));

a(n) = A003520(5*n-2).
a(n) = Sum_{k=0..n} binomial(n+2+4*k,n-1-k).
a(n) = 6*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5).
G.f.: x*(1-x)/((1-x)^5 - x).

A099238 Square array read by antidiagonals with rows generated by 1/(1-x-x^(k+1)).

Original entry on oeis.org

1, 1, 2, 1, 1, 4, 1, 1, 2, 8, 1, 1, 1, 3, 16, 1, 1, 1, 2, 5, 32, 1, 1, 1, 1, 3, 8, 64, 1, 1, 1, 1, 2, 4, 13, 128, 1, 1, 1, 1, 1, 3, 6, 21, 256, 1, 1, 1, 1, 1, 2, 4, 9, 34, 512, 1, 1, 1, 1, 1, 1, 3, 5, 13, 55, 1024, 1, 1, 1, 1, 1, 1, 2, 4, 7, 19, 89, 2048

Offset: 0

Paul Barry, Oct 08 2004

Sections of rows are given by array A099233. Sums of antidiagonals yield A097939.

The triangle of diagonals terminated after reaching the repeating value is A329146. - Andrey Zabolotskiy, Sep 01 2020

			Rows begin
1,   2,   4,   8,  16,  32,  64, 128, 256, ... (A000079)
1,   1,   2,   3,   5,   8,  13,  21,  34, ... (A000045)
1,   1,   1,   2,   3,   4,   6,   9,  13, ... (A000930)
1,   1,   1,   1,   2,   3,   4,   5,   7, ... (A003269)
1,   1,   1,   1,   1,   2,   3,   4,   5, ... (A003520)

Square array T(n, k) = Sum_{j=0..floor(n/(k+1))} binomial(n-k*j, j), n, k>=0.

cp's OEIS Frontend

A193147 Expansion of 1/(1 - x - 2*x^3 - x^5).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A369836 Number of compositions of 5*n into parts 1 and 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A099235 A quadrisection of 1/(1-x-x^5).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A141539 Square array A(n,k) of numbers of length n binary words with at least k "0" between any two "1" digits (n,k >= 0), read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005376 a(n) = n - a(a(a(a(a(n-1))))).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

Extensions

A115423 Integers n > 0 such that n XOR 30*n = 31*n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Formula

A224811 Number of subsets of {1,2,...,n-8} without differences equal to 2, 4, 6 or 8.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A115423 Integers n > 0 such that n XOR 30n = 31n.