A097805 -id:A097805 - cp's OEIS frontend

A170764 Expansion of g.f.: (1+x)/(1-44*x).

1, 45, 1980, 87120, 3833280, 168664320, 7421230080, 326534123520, 14367501434880, 632170063134720, 27815482777927680, 1223881242228817920, 53850774658067988480, 2369434084954991493120, 104255099738019625697280, 4587224388472863530680320

Offset: 0

N. J. A. Sloane, Dec 04 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..600
Index entries for linear recurrences with constant coefficients, signature (44).

Cf. A003945.

k:=45;; Concatenation([1], List([1..25], n-> k*(k-1)^(n-1) )); # G. C. Greubel, Oct 10 2019

k:=45; [1] cat [k*(k-1)^(n-1): n in [1..25]]; // G. C. Greubel, Oct 10 2019

k:=45; seq(`if`(n=0, 1, k*(k-1)^(n-1)), n = 0..25); # G. C. Greubel, Oct 10 2019

CoefficientList[Series[(1+x)/(1-44*x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 09 2012 *)
With[{k = 45}, Table[If[n==0, 1, k*(k-1)^(n-1)], {n, 0, 25}]] (* G. C. Greubel, Oct 10 2019 *)
Join[{1},NestList[44#&,45,20]] (* Harvey P. Dale, Aug 22 2021 *)

vector(26, n, k=45; if(n==1, 1, k*(k-1)^(n-2))) \\ G. C. Greubel, Oct 10 2019

k=45; [1]+[k*(k-1)^(n-1) for n in (1..25)] # G. C. Greubel, Oct 10 2019

a(n) = Sum_{k=0..n} A097805(n,k)*(-1)^(n-k)*45^k. - Philippe Deléham, Dec 04 2009
a(0) = 1; for n>0, a(n) = 45*44^(n-1). - Vincenzo Librandi, Dec 05 2009
E.g.f.: (45*exp(44*x) - 1)/44. - G. C. Greubel, Oct 10 2019

A170765 Expansion of g.f.: (1+x)/(1-45*x).

Original entry on oeis.org

1, 46, 2070, 93150, 4191750, 188628750, 8488293750, 381973218750, 17188794843750, 773495767968750, 34807309558593750, 1566328930136718750, 70484801856152343750, 3171816083526855468750, 142731723758708496093750, 6422927569141882324218750

Offset: 0

N. J. A. Sloane, Dec 04 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..600
Index entries for linear recurrences with constant coefficients, signature (45).

Cf. A003945.

k:=46;; Concatenation([1], List([1..25], n-> k*(k-1)^(n-1) )); # G. C. Greubel, Oct 10 2019

k:=46; [1] cat [k*(k-1)^(n-1): n in [1..25]]; // G. C. Greubel, Oct 10 2019

k:=46; seq(`if`(n=0, 1, k*(k-1)^(n-1)), n = 0..25); # G. C. Greubel, Oct 10 2019

CoefficientList[Series[(1+x)/(1-45x),{x,0,15}],x]  (* Harvey P. Dale, Mar 26 2011 *)
With[{k = 46}, Table[If[n==0, 1, k*(k-1)^(n-1)], {n, 0, 25}]] (* G. C. Greubel, Oct 10 2019 *)

a(n)=46*45^n\45 \\ Charles R Greathouse IV, Jun 16 2011

vector(26, n, k=46; if(n==1, 1, k*(k-1)^(n-2))) \\ G. C. Greubel, Oct 10 2019

k=46; [1]+[k*(k-1)^(n-1) for n in (1..25)] # G. C. Greubel, Oct 10 2019

a(n) = Sum_{k=0..n} A097805(n,k)*(-1)^(n-k)*46^k. - Philippe Deléham, Dec 04 2009
a(0) = 1; for n>0, a(n) = 46*45^(n-1). - Vincenzo Librandi, Dec 05 2009
E.g.f.: (46*exp(45*x) - 1)/45. - G. C. Greubel, Oct 10 2019

A170766 Expansion of g.f.: (1+x)/(1-46*x).

Original entry on oeis.org

1, 47, 2162, 99452, 4574792, 210440432, 9680259872, 445291954112, 20483429889152, 942237774900992, 43342937645445632, 1993775131690499072, 91713656057762957312, 4218828178657096036352, 194066096218226417672192, 8927040426038415212920832

Offset: 0

N. J. A. Sloane, Dec 04 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..600
Index entries for linear recurrences with constant coefficients, signature (46).

Cf. A003945.

k:=47;; Concatenation([1], List([1..25], n-> k*(k-1)^(n-1) )); # G. C. Greubel, Oct 10 2019

k:=47; [1] cat [k*(k-1)^(n-1): n in [1..25]]; // G. C. Greubel, Oct 10 2019

k:=47; seq(`if`(n=0, 1, k*(k-1)^(n-1)), n = 0..25); # G. C. Greubel, Oct 10 2019

CoefficientList[Series[(1+x)/(1-46*x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 09 2012 *)
With[{k = 47}, Table[If[n==0, 1, k*(k-1)^(n-1)], {n, 0, 25}]] (* G. C. Greubel, Oct 10 2019 *)

vector(26, n, k=47; if(n==1, 1, k*(k-1)^(n-2))) \\ G. C. Greubel, Oct 10 2019

k=47; [1]+[k*(k-1)^(n-1) for n in (1..25)] # G. C. Greubel, Oct 10 2019

a(n) = Sum_{k=0..n} A097805(n,k)*(-1)^(n-k)*47^k. - Philippe Deléham, Dec 04 2009
a(0) = 1; for n>0, a(n) = 47*46^(n-1). - Vincenzo Librandi, Dec 05 2009
E.g.f.: (47*exp(46*x) - 1)/46. - G. C. Greubel, Oct 11 2019

A170767 Expansion of g.f.: (1+x)/(1-47*x).

Original entry on oeis.org

1, 48, 2256, 106032, 4983504, 234224688, 11008560336, 517402335792, 24317909782224, 1142941759764528, 53718262708932816, 2524758347319842352, 118663642324032590544, 5577191189229531755568, 262127985893787992511696, 12320015337008035648049712

Offset: 0

N. J. A. Sloane, Dec 04 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..600
Index entries for linear recurrences with constant coefficients, signature (47).

Cf. A003945.

k:=48;; Concatenation([1], List([1..25], n-> k*(k-1)^(n-1) )); # G. C. Greubel, Oct 10 2019

k:=48; [1] cat [k*(k-1)^(n-1): n in [1..25]]; // G. C. Greubel, Oct 10 2019

k:=48; seq(`if`(n=0, 1, k*(k-1)^(n-1)), n = 0..25); # G. C. Greubel, Oct 10 2019

CoefficientList[Series[(1+x)/(1-47*x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 09 2012 *)
With[{k = 48}, Table[If[n==0, 1, k*(k-1)^(n-1)], {n, 0, 25}]] (* G. C. Greubel, Oct 10 2019 *)
Join[{1},NestList[47#&,48,20]] (* Harvey P. Dale, Nov 07 2021 *)

vector(26, n, k=48; if(n==1, 1, k*(k-1)^(n-2))) \\ G. C. Greubel, Oct 10 2019

k=48; [1]+[k*(k-1)^(n-1) for n in (1..25)] # G. C. Greubel, Oct 10 2019

a(n) = Sum_{k=0..n} A097805(n,k)*(-1)^(n-k)*48^k. - Philippe Deléham, Dec 04 2009
a(0) = 1; for n>0, a(n) = 48*47^(n-1). - Vincenzo Librandi, Dec 05 2009
E.g.f.: (48*exp(47*x) - 1)/47. - G. C. Greubel, Oct 11 2019

A170768 Expansion of g.f.: (1+x)/(1-48*x).

Original entry on oeis.org

1, 49, 2352, 112896, 5419008, 260112384, 12485394432, 599298932736, 28766348771328, 1380784741023744, 66277667569139712, 3181328043318706176, 152703746079297896448, 7329779811806299029504, 351829430966702353416192, 16887812686401712963977216

Offset: 0

N. J. A. Sloane, Dec 04 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..600
Index entries for linear recurrences with constant coefficients, signature (48).

Cf. A003945.

k:=49;; Concatenation([1], List([1..25], n-> k*(k-1)^(n-1) )); # G. C. Greubel, Oct 10 2019

k:=49; [1] cat [k*(k-1)^(n-1): n in [1..25]]; // G. C. Greubel, Oct 10 2019

k:=49; seq(`if`(n=0, 1, k*(k-1)^(n-1)), n = 0..25); # G. C. Greubel, Oct 10 2019

CoefficientList[Series[(1+x)/(1-48*x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 09 2012 *)
With[{k = 49}, Table[If[n==0, 1, k*(k-1)^(n-1)], {n, 0, 25}]] (* G. C. Greubel, Oct 10 2019 *)

vector(26, n, k=49; if(n==1, 1, k*(k-1)^(n-2))) \\ G. C. Greubel, Oct 10 2019

k=49; [1]+[k*(k-1)^(n-1) for n in (1..25)] # G. C. Greubel, Oct 10 2019

a(n) = Sum_{k=0..n} A097805(n,k)*(-1)^(n-k)*49^k. - Philippe Deléham, Dec 04 2009
a(0) = 1; for n>0, a(n) = 49*48^(n-1). - Vincenzo Librandi, Dec 05 2009
E.g.f.: (49*exp(48*x) - 1)/48. - G. C. Greubel, Oct 11 2019

A345197 Concatenation of square matrices A(n), each read by rows, where A(n)(k,i) is the number of compositions of n of length k with alternating sum i, where 1 <= k <= n, and i ranges from -n + 2 to n in steps of 2.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 2, 3, 0, 0, 2, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 2, 3, 4, 0, 0, 3, 4, 3, 0, 0, 0, 0, 2, 3, 0, 0, 0, 0, 1, 0, 0, 0

Offset: 0

Gus Wiseman, Jul 03 2021

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

			The matrices for n = 1..7:
  1   0 1   0 0 1   0 0 0 1   0 0 0 0 1   0 0 0 0 0 1   0 0 0 0 0 0 1
      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
            0 1 0   0 1 2 0   0 1 2 3 0   0 1 2 3 4 0   0 1 2 3 4 5 0
                    0 1 0 0   0 2 2 0 0   0 3 4 3 0 0   0 4 6 6 4 0 0
                              0 0 1 0 0   0 0 2 3 0 0   0 0 3 6 6 0 0
                                          0 0 1 0 0 0   0 0 3 3 0 0 0
                                                        0 0 0 1 0 0 0
Matrix n = 5 counts the following compositions:
           i=-3:        i=-1:          i=1:            i=3:        i=5:
        -----------------------------------------------------------------
   k=1: |    0            0             0               0          (5)
   k=2: |   (14)         (23)          (32)            (41)         0
   k=3: |    0          (131)       (221)(122)   (311)(113)(212)    0
   k=4: |    0       (1211)(1112)  (2111)(1121)         0           0
   k=5: |    0            0          (11111)            0           0

Gus Wiseman, A raster plot of the zeros in A(16).

The number of nonzero terms in each matrix appears to be A000096.
The number of zeros in each matrix appears to be A000124.
Row sums and column sums both appear to be A007318 (Pascal's triangle).
The matrix sums are A131577.
Antidiagonal sums appear to be A163493.
The reverse-alternating version is also A345197 (this sequence).
Antidiagonals are A345907.
Traces are A345908.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
Other tetrangles: A318393, A318816, A320808, A321912.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000097, A000346, A007318, A008549, A025047, A032443, A034871, A114121, A120452, A238279, A239830, A344604.

ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==k&&ats[#]==i&]],{n,0,6},{k,1,n},{i,-n+2,n,2}]

A294175 a(n) = 2^(n-1) + ((1+(-1)^n)/4)*binomial(n, n/2) - binomial(n, floor(n/2)).

Original entry on oeis.org

0, 0, 1, 1, 5, 6, 22, 29, 93, 130, 386, 562, 1586, 2380, 6476, 9949, 26333, 41226, 106762, 169766, 431910, 695860, 1744436, 2842226, 7036530, 11576916, 28354132, 47050564, 114159428, 190876696, 459312152, 773201629, 1846943453, 3128164186, 7423131482

Offset: 0

Enrique Navarrete, Feb 10 2018

nonn

Number of subsets of {1,2,...,n} that contain more even than odd numbers.
Note that A058622 counts the nonempty subsets of {1,2,...,n} that contain more odd than even numbers.
From Gus Wiseman, Jul 22 2021: (Start)
Also the number of integer compositions of n + 1 with alternating sum < 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 0 through a(6) = 6 compositions (empty columns indicated by dots) are:
  .  .  (12)  (13)  (14)    (15)
                    (23)    (24)
                    (131)   (141)
                    (1112)  (1113)
                    (1211)  (1212)
                            (1311)
Also the number of integer compositions of n + 1 with reverse-alternating sum < 0. For a bijection, keep the odd-length compositions and reverse the even-length ones.
Also the number of (n+1)-digit binary numbers with more 0's than 1's. For example, the a(0) = 0 through a(5) = 6 binary numbers are:
  .  .  100  1000  10000  100000
                   10001  100001
                   10010  100010
                   10100  100100
                   11000  101000
                          110000
(End)
2*a(n) is the number of all-positive pinnacle sets that are admissible in the group S_{n+1}^B of signed permutations, but not admissible in S_{n+1}. - Bridget Tenner, Jan 06 2023

			For example, for n=5, a(5)=6 and the 6 subsets are {2}, {4}, {2,4}, {1,2,4}, {2,3,4}, {2,4,5}.

Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO] (2023).

The even bisection is A000346.
The odd bisection is A008549.
The following relate to compositions of n + 1 with alternating sum k < 0.
- The k = 1 version is A000984, ranked by A345909/A345911.
- The opposite (k > 0) version is A027306, ranked by A345917/A345918.
- The weak (k <= 0) version A058622, ranked by A345915/A345916.
- The k != 0 version is also A058622, ranked by A345921.
- The complement (k >= 0) is counted by A116406, ranked by A345913/A345914.
- The k = 0 version is A138364, ranked by A344619.
- The unordered version is A344608, ranked by A119899.
- Ranked by A345919 (reverse: A345920).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A101211 lists run-lengths in binary expansion (reverse: A227736).
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001700, A007318, A025047, A032443, A034871, A106356, A114121, A126869, A163493, A344743, A345908, A289871, A359066, A359067.

f:= gfun:-rectoproc({(8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4), a(0) = 0, a(1) = 0, a(2) = 1, a(3) = 1}, a(n), remember):
map(f, [$0..40]); # Robert Israel, Feb 12 2018

f[n_] := 2^(n - 1) + ((1 + (-1)^n)/4) Binomial[n, n/2] - Binomial[n, Floor[n/2]]; Array[f, 38, 0] (* Robert G. Wilson v, Feb 10 2018 *)
Table[Length[Select[Tuples[{0,1},{n+1}],First[#]==1&&Count[#,0]>Count[#,1]&]],{n,0,10}] (* Gus Wiseman, Jul 22 2021 *)

From Robert Israel, Feb 12 2018: (Start)
G.f.: (x+1)*sqrt(1-4*x^2)/(2*x*(4*x^2-1))+(x-1)/(2*(2*x-1)*x).
D-finite with recurrence: (8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4) = 0. (End)

A271703 Triangle read by rows: the unsigned Lah numbers T(n, k) = binomial(n-1, k-1)*n!/k! if n > 0 and k > 0, T(n, 0) = 0^n and otherwise 0, for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 6, 6, 1, 0, 24, 36, 12, 1, 0, 120, 240, 120, 20, 1, 0, 720, 1800, 1200, 300, 30, 1, 0, 5040, 15120, 12600, 4200, 630, 42, 1, 0, 40320, 141120, 141120, 58800, 11760, 1176, 56, 1, 0, 362880, 1451520, 1693440, 846720, 211680, 28224, 2016, 72, 1

Offset: 0

Peter Luschny, Apr 14 2016

The Lah numbers can be seen as the case m=1 of the family of triangles T_{m}(n,k) = T_{m}(n-1,k-1)+(k^m+(n-1)^m)*T_{m}(n-1,k) (see the link 'Partition transform').

This is the Sheffer triangle (lower triangular infinite matrix) (1, x/(1-x)), an element of the Jabotinsky subgroup of the Sheffer group. - Wolfdieter Lang, Jun 12 2017

			As a rectangular array (diagonals of the triangle):
  1,      1,       1,       1,       1,       1,       ... A000012
  0,      2,       6,       12,      20,      30,      ... A002378
  0,      6,       36,      120,     300,     630,     ... A083374
  0,      24,      240,     1200,    4200,    11760,   ... A253285
  0,      120,     1800,    12600,   58800,   211680,  ...
  0,      720,     15120,   141120,  846720,  3810240, ...
A000007, A000142, A001286, A001754, A001755,  A001777.
The triangle T(n,k) begins:
n\k 0       1        2        3        4       5      6     7    8  9 10 ...
0:  1
1:  0       1
2:  0       2        1
3:  0       6        6        1
4:  0      24       36       12        1
5:  0     120      240      120       20       1
6:  0     720     1800     1200      300      30      1
7:  0    5040    15120    12600     4200     630     42     1
8:  0   40320   141120   141120    58800   11760   1176    56    1
9:  0  362880  1451520  1693440   846720  211680  28224  2016   72  1
10: 0 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90  1
...  - _Wolfdieter Lang_, Jun 12 2017

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., pp. 312, 552.
I. Lah, Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik, Mitt.-Bl. Math. Statistik, 7:203-213, 1955.
T. Mansour, M. Schork, Commutation Relations, Normal Ordering, and Stirling Numbers, CRC Press, 2016

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150, flattened)
Richell O. Celeste, Roberto B. Corcino, and Ken Joffaniel M. Gonzales, Two Approaches to Normal Order Coefficients, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.5.
M. F. Hasler and Peter Luschny, Formulas for A271703, OEIS Wiki, Aug. 2017.
S. A. Joni, G.-C. Rota, and B. Sagan, From sets to functions: Three elementary examples, Discrete Mathematics, Volume 37, Issues 2-3, 1981, 193-202.
Marin Knežević, Vedran Krčadinac, and Lucija Relić, Matrix products of binomial coefficients and unsigned Stirling numbers, arXiv:2012.15307 [math.CO], 2020.
D. E. Knuth, Convolution polynomials, Mathematica J. 2.1 (1992), no. 4, 67-78.
Peter Luschny, Lah numbers
Peter Luschny, Partition transform
Robert S. Maier, Boson Operator Ordering Identities from Generalized Stirling and Eulerian Numbers, arXiv:2308.10332 [math.CO], 2023. See. p. 18.
Piotr Miska and Maciej Ulas, On some properties of the number of permutations being products of pairwise disjoint d-cycles, arXiv:1904.03395 [math.NT], 2019.
Emanuele Munarini, Combinatorial identities involving the central coefficients of a Sheffer matrix, Applicable Analysis and Discrete Mathematics (2019) Vol. 13, 495-517.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See p. 12.

Variants: A008297 the main entry for these numbers, A105278, A111596 (signed).
A000262 (row sums). Largest number of the n-th row in A002868.
Cf. A097805, A354795, A360177.

T := (n, k) -> `if`(n=k, 1, binomial(n-1,k-1)*n!/k!):
seq(seq(T(n, k), k=0..n), n=0..9);

T[n_, k_] := Binomial[n, k]*FactorialPower[n-1, n-k];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 20 2017 *)

@cached_function
def T(n,k):
    if k<0 : return 0
    if k==n: return 1
    return T(n-1,k-1) + (k+n-1)*T(n-1,k)
for n in (0..8): print([T(n,k) for k in (0..n)])

For a collection of formulas see the 'Lah numbers' link.
T(n, k) = A097805(n, k)*n!/k! = (-1)^k*P_{n, k}(1,1,1,...) where P_{n, k}(s) is the partition transform of s.
T(n, k) = coeff(n! * P(n), x, k) with P(n) = (1/n)*(Sum_{k=0..n-1}(x(n-k)*P(k))), for n >= 1 and P(n=0) = 1, with x(n) = n*x. See A036039. - Johannes W. Meijer, Jul 08 2016
From Wolfdieter Lang, Jun 12 2017: (Start)
E.g.f. of row polynomials R(n, x) = Sum_{k=0..n} T(n, k)*x^k (that is egf of the triangle) is exp(x*t/(1-t)) (a Sheffer triangle of the Jabotinsky type).
E.g.f. column k: (t/(1-t))^k/k!.
Three term recurrence: T(n, k) = T(n-1, k-1) + (n-1+k)*T(n, k-1), n >= 1, k = 0..n, with T(0, 0) =1, T(n, -1) = 0, T(n, k) = 0 if n < k.
T(n, k) = binomial(n, k)*fallfac(x=n-1, n-k), with fallfac(x, n) = Product_{j=0..(n-1)} (x - j), for n >= 1, and 0 for n = 0.
risefac(x, n) = Sum_{k=0..n} T(n, k)*fallfac(k), with risefac(x, n) = Product_{j=0..(n-1)} (x + j), for n >= 1, and 0 for n = 0.
See Graham et al., exercise 31, p. 312, solution p. 552. (End)
Formally, let f_n(x) = Sum_{k>n} (k-1)!*x^k; then f_n(x) = Sum_{k=0..n} T(n, k)* x^(n+k)*f_0^((k))(x), where ^((k)) stands for the k-th derivative. - Luc Rousseau, Dec 27 2020
T(n, k) = Sum_{j=k..n} A354795(n, j)*A360177(j, k). - Mélika Tebni, Feb 02 2023
T(n, k) = binomial(n, k)*(n-1)!/(k-1)! for n, k > 0. - Chai Wah Wu, Nov 30 2023

A163493 Number of binary strings of length n which have the same number of 00 and 01 substrings.

Original entry on oeis.org

1, 2, 2, 3, 6, 9, 15, 30, 54, 97, 189, 360, 675, 1304, 2522, 4835, 9358, 18193, 35269, 68568, 133737, 260802, 509132, 995801, 1948931, 3816904, 7483636, 14683721, 28827798, 56637969, 111347879, 219019294, 431043814, 848764585, 1672056525, 3295390800, 6497536449

Offset: 0

Christopher Carl Heckman, Jul 29 2009

nonn

A variation of problem 11424 in the American Mathematical Monthly. Terms were brute-force calculated using Maple 10.
Proposed Problem 11610 in the Dec 2011 A.M.M.
From Gus Wiseman, Jul 27 2021: (Start)
Also the antidiagonal sums of the matrices counting integer compositions by length and alternating sum (A345197). So a(n) is the number of integer compositions of n + 1 of length (n - s + 3)/2, where s is the alternating sum of the composition. For example, the a(0) = 1 through a(6) = 7 compositions are:
  (1)  (2)   (3)   (4)    (5)     (6)     (7)
       (11)  (21)  (31)   (41)    (51)    (61)
                   (121)  (122)   (123)   (124)
                          (221)   (222)   (223)
                          (1112)  (321)   (322)
                          (1211)  (1122)  (421)
                                  (1221)  (1132)
                                  (2112)  (1231)
                                  (2211)  (2122)
                                          (2221)
                                          (3112)
                                          (3211)
                                          (11131)
                                          (12121)
                                          (13111)
For a bijection with the main (binary string) interpretation, take the run-lengths of each binary string of length n + 1 that satisfies the condition and starts with 1.
(End)

			1 + 2*x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 15*x^6 + 30*x^7 + 54*x^8 + 97*x^9 + ...
From _Gus Wiseman_, Jul 27 2021: (Start)
The a(0) = 1 though a(6) = 15 binary strings:
  ()  (0)  (1,0)  (0,0,1)  (0,0,1,0)  (0,0,1,1,0)  (0,0,0,1,0,1)
      (1)  (1,1)  (1,1,0)  (0,0,1,1)  (0,0,1,1,1)  (0,0,1,0,0,1)
                  (1,1,1)  (0,1,0,0)  (0,1,1,0,0)  (0,0,1,1,1,0)
                           (1,0,0,1)  (1,0,0,1,0)  (0,0,1,1,1,1)
                           (1,1,1,0)  (1,0,0,1,1)  (0,1,0,0,0,1)
                           (1,1,1,1)  (1,0,1,0,0)  (0,1,1,1,0,0)
                                      (1,1,0,0,1)  (1,0,0,1,1,0)
                                      (1,1,1,1,0)  (1,0,0,1,1,1)
                                      (1,1,1,1,1)  (1,0,1,1,0,0)
                                                   (1,1,0,0,1,0)
                                                   (1,1,0,0,1,1)
                                                   (1,1,0,1,0,0)
                                                   (1,1,1,0,0,1)
                                                   (1,1,1,1,1,0)
                                                   (1,1,1,1,1,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3328 (first 501 terms from R. H. Hardin)
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv preprint arXiv:1112.6207 [math.CO], 2011. See subpages for rigorous derivations of g.f., recurrence, asymptotics for this sequence. [From _N. J. A. Sloane_, Apr 07 2012]
R. Stanley, Problem 11610, Amer. Math. Monthly, 118 (2011), 937; 120 (2013), 943-944.

Antidiagonal sums of the matrices A345197.
Row sums of A345907.
Taking diagonal instead of antidiagonal sums gives A345908.
A011782 counts compositions (or binary strings).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000041, A000070, A000096, A000097, A000124, A000346, A007318, A008549, A025047, A131577, A238279.

with(combinat): count := proc(n) local S, matches, A, k, i; S := subsets(\{seq(i, i=1..n)\}): matches := 0: while not S[finished] do A := S[nextvalue](): k := 0: for i from 1 to n-1 do: if not (i in A) and not (i+1 in A) then k := k + 1: fi: if not (i in A) and (i+1 in A) then k := k - 1: fi: od: if (k = 0) then matches := matches + 1: fi: end do; return(matches); end proc:
# second Maple program:
b:= proc(n, l, t) option remember; `if`(n-abs(t)<0, 0, `if`(n=0, 1,
      add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..36);  # Alois P. Heinz, Mar 20 2024

a[0] = 1; a[n_] := Sum[Binomial[2*k - 1, k]*Binomial[n - 2*k, k] + Binomial[2*k, k]*Binomial[n - 2*k - 1, k], {k, 0, n/3}];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 28 2017, after Joel B. Lewis *)
Table[Length[Select[Tuples[{0,1},n],Count[Partition[#,2,1],{0,0}]==Count[Partition[#,2,1],{0,1}]&]],{n,0,10}] (* Gus Wiseman, Jul 27 2021 *)
a[0]:=1; a[n_]:=(1 + 3*HypergeometricPFQ[{1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3},{1, (1-n)/2, 1-n/2, -3*n/8}, -27])/2; Array[a,37,0] (* Stefano Spezia, Apr 26 2024 *)

from math import comb
def A163493(n): return 2+sum((x:=comb((k:=m<<1)-1,m)*comb(n-k,m))+(x*(n-3*m)<<1)//(n-k) for m in range(1,n//3+1)) if n else 1 # Chai Wah Wu, May 01 2024

G.f.: 1/2/(1-x) + (1+2*x)/2/sqrt((1-x)*(1-2*x)*(1+x+2*x^2)). - Richard Stanley, corrected Apr 29 2011
G.f.: (1 + sqrt( 1 + 4*x / ((1 - x) * (1 - 2*x) * (1 + x + 2*x^2)))) / (2*(1 - x)). - Michael Somos, Jan 30 2012
a(n) = sum( binomial(2*k-1, k)*binomial(n-2*k,k) + binomial(2*k, k)*binomial(n-2*k-1, k), k=0..floor(n/3)). - Joel B. Lewis, May 21 2011
Conjecture: -n*a(n) +(2+n)*a(n-1) +(3n-12)*a(n-2) +(12-n)*a(n-3) +(2n-18)*a(n-4)+(56-12n)*a(n-5) +(8n-40)*a(n-6)=0. - R. J. Mathar, Nov 28 2011
G.f. y = A(x) satisfies x = (1 - x) * (1 - 2*x) * (1 + x + 2*x^2) * y * (y * (1 - x) - 1). - Michael Somos, Jan 30 2012
Sequence a(n) satisfies 0 = a(n) * (n^2-2*n) + a(n-1) * (-3*n^2+8*n-2) + a(n-2) * (3*n^2-10*n+2) + a(n-3) * (-5*n^2+18*n-6) + a(n-4) * (8*n^2-34*n+22) + a(n-5) * (-4*n^2+20*n-16) except if n=1 or n=2. - Michael Somos, Jan 30 2012
a(n) = (1 + 3*hypergeom([1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3],[1, (1-n)/2, 1-n/2, -3*n/8],-27))/2 for n > 0. - Stefano Spezia, Apr 26 2024
a(n) ~ 2^n / sqrt(Pi*n). - Vaclav Kotesovec, Apr 26 2024

A262977 a(n) = binomial(4*n-1,n).

Original entry on oeis.org

1, 3, 21, 165, 1365, 11628, 100947, 888030, 7888725, 70607460, 635745396, 5752004349, 52251400851, 476260169700, 4353548972850, 39895566894540, 366395202809685, 3371363686069236, 31074067324187580, 286845713747883300, 2651487106659130740, 24539426037817994160

Offset: 0

Vladimir Kruchinin, Oct 06 2015

From Gus Wiseman, Sep 28 2022: (Start)
Also the number of integer compositions of 4n with alternating sum 2n, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A348614. The a(12) = 21 compositions are:
  (6,2)  (1,2,5)  (1,1,5,1)  (1,1,1,1,4)
         (2,2,4)  (2,1,4,1)  (1,1,2,1,3)
         (3,2,3)  (3,1,3,1)  (1,1,3,1,2)
         (4,2,2)  (4,1,2,1)  (1,1,4,1,1)
         (5,2,1)  (5,1,1,1)  (2,1,1,1,3)
                             (2,1,2,1,2)
                             (2,1,3,1,1)
                             (3,1,1,1,2)
                             (3,1,2,1,1)
                             (4,1,1,1,1)
The following pertain to this interpretation:
- The case of partitions is A000712, reverse A006330.
- Allowing any alternating sum gives A013777 (compositions of 4n).
- A011782 counts compositions of n.
- A034871 counts compositions of 2n with alternating sum 2k.
- A097805 counts compositions by alternating (or reverse-alternating) sum.
- A103919 counts partitions by sum and alternating sum (reverse: A344612).
- A345197 counts compositions by length and alternating sum.
(End)

V. V. Kruchinin and D. V. Kruchinin, A Generating Function for the Diagonal T_{2n,n} in Triangles, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.6.

Cf. A006632, A002293, A004331, A005810, A052203, A224274, A257633.
Cf. A000346, A000984, A001700, A002458, A025047, A058622, A081294, A294175.
Cf. A088218, A163455, A165817.

[Binomial(4*n-1,n): n in [0..20]]; // Vincenzo Librandi, Oct 06 2015

Table[Binomial[4 n - 1, n], {n, 0, 40}] (* Vincenzo Librandi, Oct 06 2015 *)

B(x):=sum(binomial(4*n-1,n-1)*3/(4*n-1)*x^n,n,1,30);
taylor(x*diff(B(x),x,1)/B(x),x,0,20);

a(n) = binomial(4*n-1,n); \\ Michel Marcus, Oct 06 2015

G.f.: A(x)=x*B'(x)/B(x), where B(x) if g.f. of A006632.
a(n) = Sum_{k=0..n}(binomial(n-1,n-k)*binomial(3*n,k)).
a(n) = 3*A224274(n), for n > 0. - Michel Marcus, Oct 12 2015
From Peter Bala, Nov 04 2015: (Start)
The o.g.f. equals f(x)/g(x), where f(x) is the o.g.f. for A005810 and g(x) is the o.g.f. for A002293. More generally, f(x)*g(x)^k is the o.g.f. for the sequence binomial(4*n + k,n). Cf. A005810 (k = 0), A052203 (k = 1), A257633 (k = 2), A224274 (k = 3) and A004331 (k = 4). (End)
a(n) = [x^n] 1/(1 - x)^(3*n). - Ilya Gutkovskiy, Oct 03 2017
a(n) = A071919(3n-1,n+1) = A097805(4n,n+1). - Gus Wiseman, Sep 28 2022
From Peter Bala, Feb 14 2024: (Start)
a(n) = (-1)^n * binomial(-3*n, n).
a(n) = hypergeom([1 - 3*n, -n], [1], 1).
The g.f. A(x) satisfies A(x/(1 + x)^4) = 1/(1 - 3*x). (End)
a(n) = Sum_{k = 0..n} binomial(2*n+k-1, k)*binomial(2*n-k-1, n-k). - Peter Bala, Sep 16 2024
G.f.: 1/(4-3*g) where g = 1+x*g^4 is the g.f. of A002293. - Seiichi Manyama, Aug 17 2025

cp's OEIS Frontend

A170764 Expansion of g.f.: (1+x)/(1-44*x).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A170765 Expansion of g.f.: (1+x)/(1-45*x).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A170766 Expansion of g.f.: (1+x)/(1-46*x).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A170767 Expansion of g.f.: (1+x)/(1-47*x).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A170768 Expansion of g.f.: (1+x)/(1-48*x).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A345197 Concatenation of square matrices A(n), each read by rows, where A(n)(k,i) is the number of compositions of n of length k with alternating sum i, where 1 <= k <= n, and i ranges from -n + 2 to n in steps of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs