A123110 -id:A123110 - cp's OEIS frontend

A028310 Expansion of (1 - x + x^2) / (1 - x)^2 in powers of x.

1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

N. J. A. Sloane

1 followed by the natural numbers.
Molien series for ring of Hamming weight enumerators of self-dual codes (with respect to Euclidean inner product) of length n over GF(4).
Engel expansion of e (see A006784 for definition) [when offset by 1]. - Henry Bottomley, Dec 18 2000
Also the denominators of the series expansion of log(1+x). Numerators are A062157. - Robert G. Wilson v, Aug 14 2015
The right-shifted sequence (with a(0)=0) is an autosequence (of the first kind - see definition in links). - Jean-François Alcover, Mar 14 2017

			G.f. = 1 + x + 2*x^2 + 3*x^3 + 4*x^4 + 5*x^5 + 6*x^6 + 7*x^7 + 8*x^8 + 9*x^9  + ...

G. C. Greubel, Table of n, a(n) for n = 0..10000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
Olivia Nabawanda and Fanja Rakotondrajao, The sets of flattened partitions with forbidden patterns, arXiv:2011.07304 [math.CO], 2020.
G. Nebe, E. M. Rains and N. J. A. Sloane, Self-Dual Codes and Invariant Theory, Springer, Berlin, 2006.
Oeis Wiki, Autosequence
E. M. Rains and N. J. A. Sloane, Self-dual codes, pp. 177-294 of Handbook of Coding Theory, Elsevier, 1998 (Abstract, pdf, ps).
Michael Somos, Rational Function Multiplicative Coefficients
Index entries for linear recurrences with constant coefficients, signature (2,-1).
Index entries for Molien series
Index entries for sequences related to Engel expansions

Cf. A000007, A000027, A000660 (boustrophedon transform).

Cf. A001477, A004001, A005229, A112934, A123110, A212393, A204503.

a028310 n = 0 ^ n + n
a028310_list = 1 : [1..]  -- Reinhard Zumkeller, Nov 06 2012

[n eq 0 select 1 else n: n in [0..75]]; // G. C. Greubel, Jan 05 2024

a:= n-> `if`(n=0, 1, n):
seq(a(n), n=0..60);

Denominator@ CoefficientList[Series[Log[1+x], {x,0,75}], x] (* or *)
CoefficientList[ Series[(1 -x +x^2)/(1-x)^2, {x,0,75}], x] (* Robert G. Wilson v, Aug 14 2015 *)
Join[{1}, Range[75]] (* G. C. Greubel, Jan 05 2024 *)
LinearRecurrence[{2,-1},{1,1,2},80] (* Harvey P. Dale, Jan 29 2025 *)

{a(n) = (n==0) + max(n, 0)} /* Michael Somos, Feb 02 2004 */

A028310(n)=n+!n  \\ M. F. Hasler, Jan 16 2012

def A028310(n): return n|bool(n)^1 # Chai Wah Wu, Jul 13 2023

[n + int(n==0) for n in range(76)] # G. C. Greubel, Jan 05 2024

Binomial transform is A005183. - Paul Barry, Jul 21 2003
G.f.: (1 - x + x^2) / (1 - x)^2 = (1 - x^6) /((1 - x) * (1 - x^2) * (1 - x^3)) = (1 + x^3) / ((1 - x) * (1 - x^2)). a(0) = 1, a(n) = n if n>0.
Euler transform of length 6 sequence [ 1, 1, 1, 0, 0, -1]. - Michael Somos Jul 30 2006
G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 - x)))). - Michael Somos, Apr 05 2012
G.f. of A112934(x) = 1 / (1 - a(0)*x / (1 - a(1)*x / ...)). - Michael Somos, Apr 05 2012
a(n) = A000027(n) unless n=0.
a(n) = Sum_{k=0..n} A123110(n,k). - Philippe Deléham, Oct 06 2009
E.g.f: 1+x*exp(x). - Wolfdieter Lang, May 03 2010
a(n) = sqrt(floor[A204503(n+3)/9]). - M. F. Hasler, Jan 16 2012
E.g.f.: 1-x + x*E(0), where E(k) = 2 + x/(2*k+1 - x/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
a(n) = A001477(n) + A000007(n). - Miko Labalan, Dec 12 2015 (See the first comment.)

A023532 a(n) = 0 if n is of the form m*(m+3)/2, otherwise 1.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Clark Kimberling

From Stark: "alpha = 0.101101110111101111101111110 ... is irrational. For if alpha were rational, its decimal expansion would be periodic and have a period of length r starting with the k-th digit of the expansion.
"But by the very nature of alpha, there will be blocks of r digits, all 1, in this expansion after the k-th digit and the periodicity would then guarantee that everything after such a block of r digits would also be all ones.
"This contradicts the fact that there will always be zeros occurring after any given point in the expansion of alpha. Hence alpha is irrational."
a(A000096(n)) = 0; a(A007401(n)) = 1. - Reinhard Zumkeller, Dec 04 2012
Sequence B is called a reverse reluctant sequence of sequence A, if B is triangle array read by rows: row number k lists first k elements of the sequence A in reverse order. A023532 is reverse reluctant sequence of sequence A211666. - Boris Putievskiy, Jan 11 2013
An example of a sequence with infinite critical exponent [Vaslet]. - N. J. A. Sloane, May 05 2013

			From _Boris Putievskiy_, Jan 11 2013: (Start)
As a triangular array written by rows, the sequence begins:
  0;
  1, 0;
  1, 1, 0;
  1, 1, 1, 0;
  1, 1, 1, 1, 0;
  1, 1, 1, 1, 1, 0;
  1, 1, 1, 1, 1, 1, 0;
  ...
(End)

Harold M. Stark, An Introduction to Number Theory, The MIT Press, Cambridge, Mass, eighth printing 1994, page 170.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Boris Putievskiy, Transformations Integer Sequences And Pairing Functions arXiv:1212.2732 [math.CO], 2012.
Elise Vaslet, Critical exponents of words over 3 letters, Electronic Journal of Combinatorics, 18 (2011), #P125.
Index entries for characteristic functions

Cf. A023531, A211666.

Essentially the same sequence as A114607 and A123110. - N. J. A. Sloane, Feb 07 2020

a023532 = (1 -) . a010052 . (+ 9) . (* 8)
a023532_list = concat $ iterate (\rs -> 1 : rs) [0]
-- Reinhard Zumkeller, Dec 04 2012

A023532 := proc(n)
    option remember ;
    local m,t ;
    for m from 0 do
        t := m*(m+3)/2 ;
        if t > n then
            return 1 ;
        elif t = n then
            return 0 ;
        end if;
    end do:
end proc:
seq(A023532(n),n=0..40) ; # R. J. Mathar, May 15 2025

a = {}; Do[a = Append[a, Join[ {0}, Table[1, {n} ] ] ], {n, 1, 13} ]; a = Flatten[a]
Table[PadLeft[{0},n,1],{n,0,20}]//Flatten (* Harvey P. Dale, Jul 10 2019 *)

for(n=1,9,print1("0, ");for(i=1,n,print1("1, "))) \\ Charles R Greathouse IV, Jun 16 2011

a(n)=!issquare(8*n+9) \\ Charles R Greathouse IV, Jun 16 2011

from sympy.ntheory.primetest import is_square
def A023532(n): return bool(is_square((n<<3)+9))^1 # Chai Wah Wu, Feb 10 2023

a(n) = 0 if and only if 8n+9 is a square. - Charles R Greathouse IV, Jun 16 2011
Blocks of lengths 1, 2, 3, 4, ... of ones separated by a single zero.
a(n) = 1 - floor((sqrt(9+8n)-1)/2) + floor((sqrt(1+8n)-1)/2). - Paul Barry, May 25 2004
a(n) = A211666(m), where m = (t^2 + 3*t + 4)/2n - n, t = floor((-1 + sqrt(8*n-7))/2). - Boris Putievskiy, Jan 11 2013
a(n) = [A002262(n) < A003056(n)]. - Yuchun Ji, May 18 2020
a(n) = 1-A023531(n). - R. J. Mathar, May 15 2025

Additional comments from Robert G. Wilson v, Nov 06 2000

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

Original entry on oeis.org

1, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534, 131070, 262142, 524286, 1048574, 2097150, 4194302, 8388606, 16777214, 33554430, 67108862, 134217726, 268435454, 536870910, 1073741822, 2147483646, 4294967294, 8589934590

Offset: 0

Paul Barry, May 28 2004

a(n+1)/2 = A000225(n). Binomial transform is A002783. Binomial transform of 2 - 2*0^n + (-1)^n or 1,1,3,1,3,1,3,1,...
From Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 2007: (Start)
Number of n-tuples where each entry is chosen from the subsets of {1,2} such that the intersection of all n entries contains exactly one element.
There is the following general formula: The number T(n,k,r) of n-tuples where each entry is chosen from the subsets of {1,2,..,k} such that the intersection of all n entries contains exactly r elements is: T(n,k,r) = binomial(k,r) * (2^n - 1)^(k-r). This may be shown by exhibiting a bijection to a set whose cardinality is obviously binomial(k,r) * (2^n - 1)^(k-r), namely the set of all k-tuples where each entry is chosen from subsets of {1,..,n} in the following way: Exactly r entries must be {1,..,n} itself (there are binomial(k,r) ways to choose them) and the remaining (k-r) entries must be chosen from the 2^n-1 proper subsets of {1,..,n}, i.e., for each of the (k-r) entries, {1,..,n} is forbidden (there are, independent of the choice of the full entries, (2^n - 1)^(k-r) possibilities to do that, hence the formula). The bijection into this set is given by (X_1,..,X_n) |-> (Y_1,..,Y_k) where for each j in {1,..,k} and each i in {1,..,n}, i is in Y_j if and only if j is in X_i.
Examples: a(1)=2 because the two tuples of length one are: ({1}) and ({2}).
a(3)=14 because the fourteen tuples of length three are: ({1},{1},{1}), ({2},{2},{2}), ({1,2},{1},{1}), ({1},{1,2},{1}), ({1},{1},{1,2}), ({1,2},{2},{2}), ({2},{1,2},{2}), ({2},{2},{1,2}), ({1,2},{1,2},{1}), ({1,2},{1},{1,2}), ({1},{1,2},{1,2}), ({1,2}{1,2}{2}), ({1,2}{2}{1,2}), ({2}{1,2}{1,2}).
The image of this set of tuples under the bijection described in the comment is: ({1,2,3},{}), ({},{1,2,3}), ({1,2,3},{1}), ({1,2,3},{2}), ({1,2,3},{3}), ({1},{1,2,3}), ({2},{1,2,3}), ({3},{1,2,3}), ({1,2,3},{1,2}), ({1,2,3},{1,3}), ({1,2,3},{2,3}), ({1,2},{1,2,3}), ({1,3},{1,2,3}), ({2,3},{1,2,3}). Here exactly one entry is {1,..,n}={1,2,3} and the other is a proper subset. (End)
An elephant sequence, see A175654. For the corner squares just one A[5] vector, with decimal value 170, leads to this sequence. For the central square this vector leads to the companion sequence A151821. - Johannes W. Meijer, Aug 15 2010
Conjecture: a(n) is the least m>0 such that A007814(A000108(m)) = n, where A000108 gives the Catalan numbers and A007814(x) is the 2-adic valuation of x (cf. A048881). - L. Edson Jeffery, Nov 26 2015
Also, the decimal representation of the diagonal from the corner to the origin of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 645", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Jul 19 2017

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000108, A000225, A000918, A002783, A007814, A048881, A123110, A127509, A151821, A175654.

Row sums of A131108, A132046, A153861, and A193815.

[-2+4*2^(n-1)+(Binomial(2*n,n) mod 2): n in [0..40]]; // Vincenzo Librandi, Aug 14 2015

ZL := [S, {S=Prod(B,B), B=Set(Z, 1 <= card)}, labeled]: seq(combstruct[ count](ZL, size=n), n=1..31); # Zerinvary Lajos, Mar 13 2007
for k from 1 to 31 do 2*(2^k-1); od;

Join[{1}, LinearRecurrence[{3, -2}, {2, 6}, 50]] (* Vladimir Joseph Stephan Orlovsky, Feb 24 2012 *)
Join[{1},NestList[2#+2&,2,40]] (* Harvey P. Dale, Dec 25 2013 *)

Vec((1-x+2*x^2)/((1-x)*(1-2*x)) + O(x^40)) \\ Michel Marcus, Aug 14 2015

vector(100, n, n--; if(n==0, 1, 2*2^n-2)) \\ Altug Alkan, Nov 26 2015

G.f.: (1-x+2*x^2)/((1-x)*(1-2*x)).
a(n) = A000918(n+1), n >= 1.
a(n) = 2*2^n - 2 + 0^n; a(n) = 3*a(n-1) - 2*a(n-2).
a(0)=1, a(1)=2, a(n) = 2*a(n-1) + 2 for n>1. - Philippe Deléham, Sep 28 2006
a(n) = Sum_{k=0..n} 2^k*A123110(n,k). - Philippe Deléham, Feb 09 2007
a(n) = 5*a(n-2) - 4*a(n-4) for n>4 [Because x(n)=f*x(n-1)+g*x(n-2) => x(n)=(f^2+2*g)*x(n-2)-g^2*x(n-4), here with f=3 and g=-2]. - Hermann Stamm-Wilbrandt, Aug 13 2015
E.g.f.: 1 + 2*exp(x)*(exp(x) - 1). - Stefano Spezia, Feb 25 2022

Edited by N. J. A. Sloane, Apr 25 2007

A355262 Array of Fuss-Catalan numbers read by ascending antidiagonals, A(n, k) = binomial(kn + 1, k)/(kn + 1).

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 3, 5, 1, 0, 1, 1, 4, 12, 14, 1, 0, 1, 1, 5, 22, 55, 42, 1, 0, 1, 1, 6, 35, 140, 273, 132, 1, 0, 1, 1, 7, 51, 285, 969, 1428, 429, 1, 0, 1, 1, 8, 70, 506, 2530, 7084, 7752, 1430, 1, 0

Offset: 0

Peter Luschny, Jun 26 2022

An alternative definition is: the Fuss-Catalan sequences (A(n, k), k >= 0 ) are the main diagonals of the Fuss-Catalan triangles of order n - 1. See A355173 for the definition of a Fuss-Catalan triangle.

			Array A(n, k) begins:
[0] 1, 1, 0,   0,    0,     0,      0,       0,         0, ...  A019590
[1] 1, 1, 1,   1,    1,     1,      1,       1,         1, ...  A000012
[2] 1, 1, 2,   5,   14,    42,    132,     429,      1430, ...  A000108
[3] 1, 1, 3,  12,   55,   273,   1428,    7752,     43263, ...  A001764
[4] 1, 1, 4,  22,  140,   969,   7084,   53820,    420732, ...  A002293
[5] 1, 1, 5,  35,  285,  2530,  23751,  231880,   2330445, ...  A002294
[6] 1, 1, 6,  51,  506,  5481,  62832,  749398,   9203634, ...  A002295
[7] 1, 1, 7,  70,  819, 10472, 141778, 1997688,  28989675, ...  A002296
[8] 1, 1, 8,  92, 1240, 18278, 285384, 4638348,  77652024, ...  A007556
[9] 1, 1, 9, 117, 1785, 29799, 527085, 9706503, 184138713, ...  A062994

N. I. Fuss, Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat, Nova Acta Academiae Scientiarum Imperialis Petropolitanae, vol.9 (1791), 243-251.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 1990, (Eqs. 5.70, 7.66, and sec. 7.5, example 5).

Per Alexandersson, Frether Getachew Kebede, Samuel Asefa Fufa, and Dun Qiu, Pattern-Avoidance and Fuss-Catalan Numbers, J. Int. Seq. (2023) Vol. 26, Art. 23.4.2.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 337-338.
Jean-Luc Baril, Mireille Bousquet-Mélou, Sergey Kirgizov, and Mehdi Naima, The ascent lattice on Dyck paths, arXiv:2409.15982 [math.CO], 2024. See p. 6.
Jean-Christophe Aval, Multivariate Fuss-Catalan Numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.
Thomas A. Dowling, Catalan Numbers, Chapter 7.
D. E. Knuth, Convolution polynomials, arXiv:math/9207221 [math.CA]; Mathematica J. 2.1 (1992), no. 4, 67-78.
Donald Knuth's 20th Annual Christmas Tree Lecture, (3/2)-ary Trees, Stanford Online, Video 2014.
Wojciech Młotkowski, Fuss-Catalan Numbers in Noncommutative Probability, Docum. Math. 15:939-955, (2010).
Wikipedia, Fuss-Catalan number.

Cf. A091144 (main diagonal), A019590, A000012, A000108, A001764, A002293, A002294, A002295, A002296, A007556, A062994.
Variants: A062993, A070914.
Fuss-Catalan triangles: A123110 (order 0), A355173 (order 1), A355172 (order 2), A355174 (order 3).

A := (n, k) -> binomial(k*n + 1, k)/(k*n + 1):
for n from 0 to 9 do seq(A(n, k), k = 0..8) od;

(* See the Knuth references. In the christmas lecture Knuth has fun calculating the Fuss-Catalan development of Pi and i. *)
B[t_, n_] := Sum[Binomial[t k+1, k] z^k / (t k+1), {k, 0, n-1}] + O[z]^n
Table[CoefficientList[B[n, 9], z], {n, 0, 9}] // TableForm

A(n, k) = (1/k!) * Product_{j=1..k-1} (k*n + 1 - j).
A(n, k) = (binomial(k*n, k) + binomial(k*n, k-1)) / (k*n + 1).
Let B(t, z) = Sum_{k>=0} binomial(k*t + 1, k)*z^k / (k*t + 1), then
A(n, k) = [z^k] B(n, z).

A153861 Triangle read by rows, binomial transform of triangle A153860.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 6, 4, 1, 4, 10, 10, 5, 1, 5, 15, 20, 15, 6, 1, 6, 21, 35, 35, 21, 7, 1, 7, 28, 56, 70, 56, 28, 8, 1, 8, 36, 84, 126, 126, 84, 36, 9, 1, 9, 45, 120, 210, 252, 210, 120, 45, 10, 1, 10, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1

Offset: 0

Gary W. Adamson, Jan 03 2009

Row sums = A095121: (1, 2, 6, 14, 30, 62, 126,...).
Triangle T(n,k), 0<=k<=n, read by rows, given by [1,1,-1,1,0,0,0,0,0,0,0,...] DELTA [1,0,-1,1,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Jan 03 2009
A123110*A007318 as infinite lower triangular matrices. - Philippe Deléham, Jan 06 2009
A153861 is the fusion of polynomial sequences p(n,x)=x^n+x^(n-1)+...+x+1 and q(n,x)=(x+1)^n; see A193722 for the definition of fusion. - Clark Kimberling, Aug 06 2011

			First few rows of the triangle are:
1;
1, 1;
2, 3, 1;
3, 6, 4, 1;
4, 10, 10, 5, 1;
5, 15, 20, 15, 6, 1;
6, 21, 35, 35, 21, 7, 1;
7, 28, 56, 70, 56, 28, 8, 1;
8, 36, 84, 126, 126, 84, 36, 9, 1;
9, 45, 120, 210, 252, 210, 120, 45, 10, 1;
...

G. C. Greubel, Table of n, a(n) for the first 46 rows

Cf. A153860, A095121, A130405.

This is A137396 without the initial column and without signs.

z = 10; c = 1; d = 1;
p[0, x_] := 1
p[n_, x_] := x*p[n - 1, x] + 1; p[n_, 0] := p[n, x] /. x -> 0;
q[n_, x_] := (c*x + d)^n
t[n_, k_] := Coefficient[p[n, x], x^k]; t[n_, 0] := p[n, x] /. x -> 0;
w[n_, x_] := Sum[t[n, k]*q[n + 1 - k, x], {k, 0, n}]; w[-1, x_] := 1
g[n_] := CoefficientList[w[n, x], {x}]
TableForm[Table[Reverse[g[n]], {n, -1, z}]]
Flatten[Table[Reverse[g[n]], {n, -1, z}]]  (* A193815 *)
TableForm[Table[g[n], {n, -1, z}]]
Flatten[Table[g[n], {n, -1, z}]]   (* A153861 *)
(* Clark Kimberling, Aug 06 2011 *)

Triangle read by rows, A007318 * A153860. Remove left two columns of Pascal's triangle and append (1, 1, 2, 3, 4, 5,...).
As a recursive operation by way of example, row 3 = (3, 6, 4, 1) =
[1, 1, 1, 0] * (flipped Pascal's triangle matrix) = [1, 3, 3, 1]
[1, 2, 1, 0]
[1, 1, 0, 0]
[1, 0, 0, 0].
(Cf. analogous operation in A130405, but in A153861 the linear multiplier = [1,1,1,...,0].)
T(n,k) = 2*T(n-1,k)+T(n-1,k-1)-T(n-2,k)-T(n-2,k-1), T(0,0) = T(1,0) = T(1,1) = T(2,2) = 1, T(2,0)=2, T(2,1)=3, T(n,k)=0 if k<0 or if k>n. - Philippe Deléham, Dec 15 2013
G.f.: (1-x+x^2+x^2*y)/((x-1)*(-1+x+x*y)). - R. J. Mathar, Aug 11 2015

A123108 a(n) = a(n-1) + a(n-2) - a(n-3), for n > 3, with a(0)=1, a(1)=0, a(2)=1, a(3)=1.

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37

Offset: 0

Philippe Deléham, Sep 28 2006

Diagonal sums of triangle A123110. - Philippe Deléham, Oct 08 2009

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

Cf. A065033, A110654, A123110.

I:=[0,1,1]; [1] cat [n le 3 select I[n] else Self(n-1) +Self(n-2) -Self(n-3): n in [1..31]]; // G. C. Greubel, Jul 21 2021

LinearRecurrence[{1,1,-1},{1,0,1,1},90] (* Harvey P. Dale, Aug 10 2020 *)

[(2*n - 1 + (-1)^n)/4 + bool(n==0) for n in (0..90)] # G. C. Greubel, Jul 21 2021

G.f.: (1 -x +x^3)/(1 -x -x^2 +x^3).
a(n) = A110654(n-1). - R. J. Mathar, Jun 18 2008
From G. C. Greubel, Jul 21 2021: (Start)
a(n) = (1/4)*(2*n - 1 + (-1)^n) + [n=0].
E.g.f.: (1/2)*(2 + x*cosh(x) + (x-1)*sinh(x)). (End)

A123109 a(0) = 1, a(1) = 3, a(n) = 3*a(n-1) + 3 for n > 1.

Original entry on oeis.org

1, 3, 12, 39, 120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160, 2391483, 7174452, 21523359, 64570080, 193710243, 581130732, 1743392199, 5230176600, 15690529803, 47071589412, 141214768239, 423644304720, 1270932914163

Offset: 0

Philippe Deléham, Sep 28 2006

From R. J. Mathar, Oct 12 2010: (Start)
The top row, n=2, of an array that counts chess king walks with k >= 0 steps on an n X n board, starting at one of the four corners:
1,3,12, 39,120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160,
1,3,21,101,501,2405,11653, 56197, 271493, 1310597, 6328709, 30556549,
1,3,21,126,741,4341,25416,148791, 871041, 5099166,29851041,174751041,
1,3,21,126,810,5169,33447,215796,1395588, 9018255,58302057,376845978,
1,3,21,126,810,5360,36167,246034,1680313,11495503,78705226,539048956,
1,3,21,126,810,5360,36700,254756,1788468,12617828,89338116,633604564,
1,3,21,126,810,5360,36700,256255,1816090,12993280,93566653,676648735,
1,3,21,126,810,5360,36700,256255,1820335,13080120,94845670,692120270,
1,3,21,126,810,5360,36700,256255,1820335,13092211,95117374,696421066,
1,3,21,126,810,5360,36700,256255,1820335,13092211,95151979,697268152,
1,3,21,126,810,5360,36700,256255,1820335,13092211,95151979,697367593,
These are partial sums along rows of the array described in A086346. (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
Index entries for linear recurrences with constant coefficients, signature (4,-3).

a:=[1,3,12];; for n in [4..30] do a[n]:=4*a[n-1]-3*a[n-2]; od; a; # G. C. Greubel, May 24 2019

I:=[1, 3, 12]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Jun 27 2012

LinearRecurrence[{4,-3}, {1,3,12}, 30] (* Georg Fischer, May 24 2019 *)
Join[{1},NestList[3#+3&,3,30]] (* Harvey P. Dale, Aug 16 2020 *)

my(x='x+O('x^30)); Vec((1-x+3*x^2)/(1-4*x+3*x^2)) \\ G. C. Greubel, May 24 2019

((1-x+3*x^2)/(1-4*x+3*x^2)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 24 2019

a(0) = 1 and a(n) = 3*A003462(n) for n > 0.
G.f.: (1-x+3*x^2)/(1-4*x+3*x^2). [Corrected by Georg Fischer, May 24 2019]
a(n) = Sum_{k=0..n} 3^k*A123110(n,k). - Philippe Deléham, Feb 09 2007
a(n) = A029858(n+1), n > 0. - R. J. Mathar, Jun 18 2008
a(n+1) - a(n) = 3^n, n >= 2. - R. J. Mathar, Aug 18 2011
E.g.f.: 1 + 3*(exp(3*x) - exp(x))/2. - G. C. Greubel, May 24 2019

A355172 The Fuss-Catalan triangle of order 2, read by rows. Related to ternary trees.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 1, 5, 12, 0, 1, 7, 25, 55, 0, 1, 9, 42, 130, 273, 0, 1, 11, 63, 245, 700, 1428, 0, 1, 13, 88, 408, 1428, 3876, 7752, 0, 1, 15, 117, 627, 2565, 8379, 21945, 43263, 0, 1, 17, 150, 910, 4235, 15939, 49588, 126500, 246675

Offset: 0

Peter Luschny, Jun 25 2022

The Fuss-Catalan triangle of order m is a regular, (0, 0)-based table recursively defined as follows: Set row(0) = [1] and row(1) = [0, 1]. Now assume row(n-1) already constructed and duplicate the last element of row(n-1). Next apply the cumulative sum m times to this list to get row(n). Here m = 2. (See the Python program for a reference implementation.)

This definition also includes the Fuss-Catalan numbers A001764(n) = T(n, n), or row 3 in A355262. For m = 1 see A355173 and for m = 3 A355174. More generally, for n >= 1 all Fuss-Catalan sequences (A355262(n, k), k >= 0) are the main diagonals of the Fuss-Catalan triangles of order n - 1.

			Table T(n, k) begins:
  [0] [1]
  [1] [0, 1]
  [2] [0, 1,  3]
  [3] [0, 1,  5, 12]
  [4] [0, 1,  7, 25,  55]
  [5] [0, 1,  9, 42, 130,  273]
  [6] [0, 1, 11, 63, 245,  700, 1428]
  [7] [0, 1, 13, 88, 408, 1428, 3876, 7752]
Seen as an array reading the diagonals starting from the main diagonal:
  [0] 1, 1,  3, 12,  55,  273,  1428,   7752,   43263,  246675, ...  A001764
  [1] 0, 1,  5, 25, 130,  700,  3876,  21945,  126500,  740025, ...  A102893
  [2] 0, 1,  7, 42, 245, 1428,  8379,  49588,  296010, 1781325, ...  A102594
  [3] 0, 1,  9, 63, 408, 2565, 15939,  98670,  610740, 3786588, ...  A230547
  [4] 0, 1, 11, 88, 627, 4235, 27830, 180180, 1157013, 7396972, ...

A001764 (main diagonal), A102893 (subdiagonal), A102594 (diagonal 2), A230547 (diagonal 3), A005408 (column 2), A071355 (column 3), A006629 (row sums), A143603 (variant).

Cf. A123110 (triangle of order 0), A355173 (triangle of order 1), A355174 (triangle of order 3), A355262 (Fuss-Catalan array).

from functools import cache
from itertools import accumulate
@cache
def Trow(n: int) -> list[int]:
    if n == 0: return [1]
    if n == 1: return [0, 1]
    row = Trow(n - 1) + [Trow(n - 1)[n - 1]]
    return list(accumulate(accumulate(row)))
for n in range(9): print(Trow(n))

The general formula for the Fuss-Catalan triangles is, for m >= 0 and 0 <= k <= n:
FCT(n, k, m) = (m*(n - k) + m + 1)*(m*n + k - 1)!/((m*n + 1)!*(k - 1)!) for k > 0 and FCT(n, 0, m) = 0^n. The case considered here is T(n, k) = FCT(n, k, 2).
T(n, k) = (2*n - 2*k + 3)*(2*n + k - 1)!/((2*n + 1)!*(k - 1)!) for k > 0; T(n, 0) = 0^n.
The g.f. of row n of the FC-triangle of order m is 0^n + (x - (m + 1)*x^2) / (1 - x)^(m*n + 2), thus:
T(n, k) = [x^k] (0^n + (x - 3*x^2)/(1 - x)^(2*n + 2)).

A355173 The Fuss-Catalan triangle of order 1, read by rows. Related to binary trees.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 3, 5, 0, 1, 4, 9, 14, 0, 1, 5, 14, 28, 42, 0, 1, 6, 20, 48, 90, 132, 0, 1, 7, 27, 75, 165, 297, 429, 0, 1, 8, 35, 110, 275, 572, 1001, 1430, 0, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 0, 1, 10, 54, 208, 637, 1638, 3640, 7072, 11934, 16796

Offset: 0

Peter Luschny, Jun 25 2022

The Fuss-Catalan triangle of order m is a regular, (0, 0)-based table recursively defined as follows: Set row(0) = [1] and row(1) = [0, 1]. Now assume row(n-1) already constructed and duplicate the last element of row(n-1). Next apply the cumulative sum m times to this list to get row(n). Here m = 1. (See the Python program for a reference implementation.)

This definition also includes the classical Fuss-Catalan numbers, since T(n, n) = A000108(n), or row 2 in A355262. For m = 2 see A355172 and for m = 3 A355174. More generally, for n >= 1 all Fuss-Catalan sequences (A355262(n, k), k >= 0) are the main diagonals of the Fuss-Catalan triangles of order n - 1.

			Table T(n, k) begins:
  [0] [1]
  [1] [0, 1]
  [2] [0, 1, 2]
  [3] [0, 1, 3,  5]
  [4] [0, 1, 4,  9,  14]
  [5] [0, 1, 5, 14,  28,  42]
  [6] [0, 1, 6, 20,  48,  90,  132]
  [7] [0, 1, 7, 27,  75, 165,  297, 429]
  [8] [0, 1, 8, 35, 110, 275,  572, 1001, 1430]
  [9] [0, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862]
Seen as an array reading the diagonals starting from the main diagonal:
  [0] 1, 1, 2,  5,  14,   42,  132,   429,  1430,   4862,   16796, ...  A000108
  [1] 0, 1, 3,  9,  28,   90,  297,  1001,  3432,  11934,   41990, ...  A000245
  [2] 0, 1, 4, 14,  48,  165,  572,  2002,  7072,  25194,   90440, ...  A099376
  [3] 0, 1, 5, 20,  75,  275, 1001,  3640, 13260,  48450,  177650, ...  A115144
  [4] 0, 1, 6, 27, 110,  429, 1638,  6188, 23256,  87210,  326876, ...  A115145
  [5] 0, 1, 7, 35, 154,  637, 2548,  9996, 38760, 149226,  572033, ...  A000588
  [6] 0, 1, 8, 44, 208,  910, 3808, 15504, 62016, 245157,  961400, ...  A115147
  [7] 0, 1, 9, 54, 273, 1260, 5508, 23256, 95931, 389367, 1562275, ...  A115148

A000108 (main diagonal), A000245 (subdiagonal), A002057 (diagonal 2), A000344 (diagonal 3), A000027 (column 2), A000096 (column 3), A071724 (row sums), A000958 (alternating row sums), A262394 (main diagonal of array).
Variants: A009766 (main variant), A030237, A130020.
Cf. A123110 (triangle of order 0), A355172 (triangle of order 2), A355174 (triangle of order 3), A355262 (Fuss-Catalan array).
Cf. A115144, A115145, A000588, A115147, A115148.

from functools import cache
from itertools import accumulate
@cache
def Trow(n: int) -> list[int]:
    if n == 0: return [1]
    if n == 1: return [0, 1]
    row = Trow(n - 1) + [Trow(n - 1)[n - 1]]
    return list(accumulate(row))
for n in range(11): print(Trow(n))

The general formula for the Fuss-Catalan triangles is, for m >= 0 and 0 <= k <= n:
FCT(n, k, m) = (m*(n - k) + m + 1)*(m*n + k - 1)!/((m*n + 1)!*(k - 1)!) for k > 0 and FCT(n, 0, m) = 0^n. The case considered here is T(n, k) = FCT(n, k, 1).
T(n, k) = (n - k + 2)*(n + k - 1)!/((n + 1)!*(k - 1)!) for k > 0; T(n, 0) = 0^n.
The g.f. of row n of the FC-triangle of order m is 0^n + (x - (m + 1)*x^2) / (1 - x)^(m*n + 2), thus:
T(n, k) = [x^k] (0^n + (x - 2*x^2)/(1 - x)^(n + 2)).

A355174 The Fuss-Catalan triangle of order 3, read by rows. Related to quartic trees.

Original entry on oeis.org

1, 0, 1, 0, 1, 4, 0, 1, 7, 22, 0, 1, 10, 49, 140, 0, 1, 13, 85, 357, 969, 0, 1, 16, 130, 700, 2695, 7084, 0, 1, 19, 184, 1196, 5750, 20930, 53820, 0, 1, 22, 247, 1872, 10647, 47502, 166257, 420732, 0, 1, 25, 319, 2755, 17980, 93496, 395560, 1344904, 3362260

Offset: 0

Peter Luschny, Jun 25 2022

The Fuss-Catalan triangle of order m is a regular, (0, 0)-based table recursively defined as follows: Set row(0) = [1] and row(1) = [0, 1]. Now assume row(n-1) already constructed and duplicate the last element of row(n-1). Next apply the cumulative sum m times to this list to get row(n). Here m = 3. (See the Python program for a reference implementation.)

This definition also includes the Fuss-Catalan numbers A002293(n) = T(n, n), row 4 in A355262. For m = 1 see A355173 and for m = 2 A355172. More generally, for n >= 1 all Fuss-Catalan sequences (A355262(n, k), k >= 0) are the main diagonals of the Fuss-Catalan triangles of order n - 1.

			Table T(n, k) begins:
  [0] [1]
  [1] [0, 1]
  [2] [0, 1,  4]
  [3] [0, 1,  7,  22]
  [4] [0, 1, 10,  49,  140]
  [5] [0, 1, 13,  85,  357,   969]
  [6] [0, 1, 16, 130,  700,  2695,  7084]
  [7] [0, 1, 19, 184, 1196,  5750, 20930,  53820]
  [8] [0, 1, 22, 247, 1872, 10647, 47502, 166257,  420732]
  [9] [0, 1, 25, 319, 2755, 17980, 93496, 395560, 1344904, 3362260]
Seen as an array reading the diagonals starting from the main diagonal:
  [0] 1, 1,  4,  22,  140,   969,   7084,   53820,   420732, ...  A002293
  [1] 0, 1,  7,  49,  357,  2695,  20930,  166257,  1344904, ...  A233658
  [2] 0, 1, 10,  85,  700,  5750,  47502,  395560,  3321120, ...  A233667
  [3] 0, 1, 13, 130, 1196, 10647,  93496,  816816,  7128420, ...
  [4] 0, 1, 16, 184, 1872, 17980, 167552, 1535352, 13934752, ...

A002293 (main diagonal), A233658 (subdiagonal), A233667 (diagonal 2), A016777 (column 2), A196678 (row sums).

Cf. A123110 (triangle of order 0), A355173 (triangle of order 1), A355172 (triangle of order 2), A355262 (Fuss-Catalan array).

from functools import cache
from itertools import accumulate
@cache
def Trow(n: int) -> list[int]:
    if n == 0: return [1]
    if n == 1: return [0, 1]
    row = Trow(n - 1) + [Trow(n - 1)[n - 1]]
    return list(accumulate(accumulate(accumulate(row))))
for n in range(11): print(Trow(n))

The general formula for the Fuss-Catalan triangles is, for m >= 0 and 0 <= k <= n:
FCT(n, k, m) = (m*(n - k) + m + 1)*(m*n + k - 1)!/((m*n + 1)!*(k - 1)!) for k > 0 and FCT(n, 0, m) = 0^n. The case considered here is T(n, k) = FCT(n, k, 3).
T(n, k) = (3*(n - k) + 4)*(3*n + k - 1)!/((3*n + 1)!*(k - 1)!) for k > 0; T(n, 0) = n^0.
The g.f. of row n of the FC-triangle of order m is 0^n + (x - (m + 1)*x^2) / (1 - x)^(m*n + 2), thus:
T(n, k) = [x^k] (0^n + (x - 4*x^2)/(1 - x)^(3*n + 2)).

cp's OEIS Frontend

A028310 Expansion of (1 - x + x^2) / (1 - x)^2 in powers of x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

A023532 a(n) = 0 if n is of the form m*(m+3)/2, otherwise 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A355262 Array of Fuss-Catalan numbers read by ascending antidiagonals, A(n, k) = binomial(k*n + 1, k)/(k*n + 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A153861 Triangle read by rows, binomial transform of triangle A153860.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A123108 a(n) = a(n-1) + a(n-2) - a(n-3), for n > 3, with a(0)=1, a(1)=0, a(2)=1, a(3)=1.

Views

Author

A355262 Array of Fuss-Catalan numbers read by ascending antidiagonals, A(n, k) = binomial(kn + 1, k)/(kn + 1).