A106356 -id:A106356 - cp's OEIS frontend

A066099 Triangle read by rows, in which row n lists the compositions of n in reverse lexicographic order.

1, 2, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 1, 2, 2, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 5, 4, 1, 3, 2, 3, 1, 1, 2, 3, 2, 2, 1, 2, 1, 2, 2, 1, 1, 1, 1, 4, 1, 3, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 6, 5, 1, 4, 2, 4, 1, 1, 3, 3, 3, 2, 1, 3, 1, 2, 3, 1, 1, 1, 2, 4, 2, 3

Offset: 1

Alford Arnold, Dec 30 2001

The representation of the compositions (for fixed n) is as lists of parts, the order between individual compositions (for the same n) is (list-)reversed lexicographic; see the example by Omar E. Pol. - Joerg Arndt, Sep 03 2013
This is the standard ordering for compositions in this database; it is similar to the Mathematica ordering for partitions (A080577). Other composition orderings include A124734 (similar to the Abramowitz & Stegun ordering for partitions, A036036), A108244 (similar to the Maple partition ordering, A080576), etc (see crossrefs).
Factorize each term in A057335; sequence records the values of the resulting exponents. It also runs through all possible permutations of multiset digits.
This can be regarded as a table in two ways: with each composition as a row, or with the compositions of each integer as a row. The first way has A000120 as row lengths and A070939 as row sums; the second has A001792 as row lengths and A001788 as row sums. - Franklin T. Adams-Watters, Nov 06 2006
This sequence includes every finite sequence of positive integers. - Franklin T. Adams-Watters, Nov 06 2006
Compositions (or ordered partitions) are also generated in sequence A101211. - Alford Arnold, Dec 12 2006
The equivalent sequence for partitions is A228531. - Omar E. Pol, Sep 03 2013
The sole partition of zero has no components, not a single component of length one. Hence the first nonempty row is row 1. - Franklin T. Adams-Watters, Apr 02 2014 [Edited by Andrey Zabolotskiy, May 19 2018]
See sequence A261300 for another version where the terms of each composition are concatenated to form one single integer: (0, 1, 2, 11, 3, 21, 12, 111,...). This also shows how the terms can be obtained from the binary numbers A007088, cf. Arnold's first Example. - M. F. Hasler, Aug 29 2015
The k-th composition in the list is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This is described as the standard ordering used in the OEIS, although the sister sequence A228351 is also sometimes considered to be canonical. Both sequences define a bijective correspondence between nonnegative integers and integer compositions. - Gus Wiseman, May 19 2020
First differences of A030303 = positions of bits 1 in the concatenation A030190 (= A030302) of numbers written in binary (A007088). - Indices of record values (= first occurrence of n) are given by A005183: a(A005183(n)) = n, cf. FORMULA for more. - M. F. Hasler, Oct 12 2020
The geometric mean approaches the Somos constant (A112302). - Jwalin Bhatt, Feb 10 2025

			A057335 begins 1 2 4 6 8 12 18 30 16 24 36 ... so we can write
  1 2 1 3 2 1 1 4 3 2 2 1 1 1 1 ...
  . . 1 . 1 2 1 . 1 2 1 3 2 1 1 ...
  . . . . . . 1 . . . 1 . 1 2 1 ...
  . . . . . . . . . . . . . . 1 ...
and the columns here gives the rows of the triangle, which begins
  1
  2; 1 1
  3; 2 1; 1 2; 1 1 1
  4; 3 1; 2 2; 2 1 1; 1 3; 1 2 1; 1 1 2; 1 1 1 1
  ...
From _Omar E. Pol_, Sep 03 2013: (Start)
Illustration of initial terms:
  -----------------------------------
  n  j       Diagram   Composition j
  -----------------------------------
  .               _
  1  1           |_|   1;
  .             _ _
  2  1         |  _|   2,
  2  2         |_|_|   1, 1;
  .           _ _ _
  3  1       |    _|   3,
  3  2       |  _|_|   2, 1,
  3  3       | |  _|   1, 2,
  3  4       |_|_|_|   1, 1, 1;
  .         _ _ _ _
  4  1     |      _|   4,
  4  2     |    _|_|   3, 1,
  4  3     |   |  _|   2, 2,
  4  4     |  _|_|_|   2, 1, 1,
  4  5     | |    _|   1, 3,
  4  6     | |  _|_|   1, 2, 1,
  4  7     | | |  _|   1, 1, 2,
  4  8     |_|_|_|_|   1, 1, 1, 1;
(End)

Franklin T. Adams-Watters, Table of n, a(n) for n = 1..5120 (through compositions of 10)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Gus Wiseman, Statistics, classes, and transformations of standard compositions

Lists of compositions of integers: this sequence (reverse lexicographic order; minus one gives A108730), A228351 (reverse colexicographic order - every composition is reversed; minus one gives A163510), A228369 (lexicographic), A228525 (colexicographic), A124734 (length, then lexicographic; minus one gives A124735), A296774 (length, then reverse lexicographic), A337243 (length, then colexicographic), A337259 (length, then reverse colexicographic), A296773 (decreasing length, then lexicographic), A296772 (decreasing length, then reverse lexicographic), A337260 (decreasing length, then colexicographic), A108244 (decreasing length, then reverse colexicographic), also A101211 and A227736 (run lengths of bits).
Cf. row length and row sums for different splittings into rows: A000120, A070939, A001792, A001788.
Cf. A228531, A096903, A065120, A057335, A055932, A005811, A261300, A007088.
Cf. lists of partitions of integers, or multisets of integers: A026791 and crosserfs therein, A112798 and crossrefs therein.
See link for additional crossrefs pertaining to standard compositions.
A related ranking of finite sets is A048793/A272020.
Cf. A005183, A030190, A030302, A030303, A035327, A036036, A080576, A080577, A106356, A112302, A238279, A333219.

a066099 = (!!) a066099_list
a066099_list = concat a066099_tabf
a066099_tabf = map a066099_row [1..]
a066099_row n = reverse $ a228351_row n
-- (each composition as a row)
-- Peter Kagey, Aug 25 2016

Table[FactorInteger[Apply[Times, Map[Prime, Accumulate @ IntegerDigits[n, 2]]]][[All, -1]], {n, 41}] // Flatten (* Michael De Vlieger, Jul 11 2017 *)
stc[n_] := Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]] // Reverse;
Table[stc[n], {n, 0, 20}] // Flatten (* Gus Wiseman, May 19 2020 *)
Table[Reverse @ LexicographicSort @ Flatten[Permutations /@ Partitions[n], 1], {n, 10}] // Flatten (* Eric W. Weisstein, Jun 26 2023 *)

arow(n) = {local(v=vector(n),j=0,k=0);
   while(n>0,k++; if(n%2==1,v[j++]=k;k=0);n\=2);
   vector(j,i,v[j-i+1])} \\ returns empty for n=0. - Franklin T. Adams-Watters, Apr 02 2014

from itertools import islice
from itertools import accumulate, count, groupby, islice
def A066099_gen():
    for i in count(1):
        yield [len(list(g)) for _,g in groupby(accumulate(int(b) for b in bin(i)[2:]))]
A066099 = list(islice(A066099_gen(), 120))  # Jwalin Bhatt, Feb 28 2025

def a_row(n): return list(reversed(Compositions(n)))
flatten([a_row(n) for n in range(1,6)]) # Peter Luschny, May 19 2018

From M. F. Hasler, Oct 12 2020: (Start)
a(n) = A030303(n+1) - A030303(n).
a(A005183(n)) = n; a(A005183(n)+1) = n-1 (n>1); a(A005183(n)+2) = 1. (End)

Edited with additional terms by Franklin T. Adams-Watters, Nov 06 2006

0th row removed by Andrey Zabolotskiy, May 19 2018

A238279 Triangle read by rows: T(n,k) is the number of compositions of n into nonzero parts with k parts directly followed by a different part, n>=0, 0<=k<=A004523(n-1).

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 4, 1, 2, 10, 4, 4, 12, 14, 2, 2, 22, 29, 10, 1, 4, 26, 56, 36, 6, 3, 34, 100, 86, 31, 2, 4, 44, 148, 200, 99, 16, 1, 2, 54, 230, 374, 278, 78, 8, 6, 58, 322, 680, 654, 274, 52, 2, 2, 74, 446, 1122, 1390, 814, 225, 22, 1, 4, 88, 573, 1796, 2714, 2058, 813, 136, 10, 4, 88, 778, 2694, 4927

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 22 2014

Same as A238130, with zeros omitted.
Last elements in rows are 1, 1, 2, 2, 1, 4, 2, 1, 6, 2, 1, 8, ... with g.f. -(x^6+x^4-2*x^2-x-1)/(x^6-2*x^3+1).
For n > 0, also the number of compositions of n with k + 1 runs. - Gus Wiseman, Apr 10 2020

			Triangle starts:
  00:  1;
  01:  1;
  02:  2;
  03:  2,   2;
  04:  3,   4,   1;
  05:  2,  10,   4;
  06:  4,  12,  14,    2;
  07:  2,  22,  29,   10,    1;
  08:  4,  26,  56,   36,    6;
  09:  3,  34, 100,   86,   31,    2;
  10:  4,  44, 148,  200,   99,   16,    1;
  11:  2,  54, 230,  374,  278,   78,    8;
  12:  6,  58, 322,  680,  654,  274,   52,    2;
  13:  2,  74, 446, 1122, 1390,  814,  225,   22,   1;
  14:  4,  88, 573, 1796, 2714, 2058,  813,  136,  10;
  15:  4,  88, 778, 2694, 4927, 4752, 2444,  618,  77,  2;
  16:  5, 110, 953, 3954, 8531, 9930, 6563, 2278, 415, 28, 1;
  ...
Row n=5 is 2, 10, 4 because in the 16 compositions of 5
  ##:  [composition]  no. of changes
  01:  [ 1 1 1 1 1 ]   0
  02:  [ 1 1 1 2 ]   1
  03:  [ 1 1 2 1 ]   2
  04:  [ 1 1 3 ]   1
  05:  [ 1 2 1 1 ]   2
  06:  [ 1 2 2 ]   1
  07:  [ 1 3 1 ]   2
  08:  [ 1 4 ]   1
  09:  [ 2 1 1 1 ]   1
  10:  [ 2 1 2 ]   2
  11:  [ 2 2 1 ]   1
  12:  [ 2 3 ]   1
  13:  [ 3 1 1 ]   1
  14:  [ 3 2 ]   1
  15:  [ 4 1 ]   1
  16:  [ 5 ]   0
there are 2 with no changes, 10 with one change, and 4 with two changes.

Joerg Arndt and Alois P. Heinz, Rows n = 0..180, flattened

Columns k=0-10 give: A000005 (for n>0), 2*A002133, A244714, A244715, A244716, A244717, A244718, A244719, A244720, A244721, A244722.
Row lengths are A004523.
Row sums are A011782.
The version counting adjacent equal parts is A106356.
The version for ascents/descents is A238343.
The version for weak ascents/descents is A333213.
The k-th composition in standard-order has A124762(k) adjacent equal parts, A124767(k) maximal runs, A333382(k) adjacent unequal parts, and A333381(k) maximal anti-runs.
Cf. A064113, A333214, A333216.

b:= proc(n, v) option remember; `if`(n=0, 1, expand(
      add(b(n-i, i)*`if`(v=0 or v=i, 1, x), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..14);

b[n_, v_] := b[n, v] = If[n == 0, 1, Expand[Sum[b[n-i, i]*If[v == 0 || v == i, 1, x], {i, 1, n}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Feb 11 2015, after Maple *)
Table[If[n==0,1,Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]==k+1&]]],{n,0,12},{k,0,If[n==0,0,Floor[2*(n-1)/3]]}] (* Gus Wiseman, Apr 10 2020 *)

T_xy(max_row) = {my(N=max_row+1, x='x+O('x^N),h=(1+ sum(i=1,N,(x^i-y*x^i)/(1+y*x^i-x^i)))/(1-sum(i=1,N, y*x^i/(1+y*x^i-x^i)))); for(n=0,N-1, print(Vecrev(polcoeff(h,n))))}
T_xy(16) \\ John Tyler Rascoe, Jul 10 2024

G.f.: A(x,y) = ( 1 + Sum_{i>0} ((x^i)*(1 - y)/(1 + y*x^i - x^i)) )/( 1 - Sum_{i>0} ((y*x^i)/(1 + y*x^i - x^i)) ). - John Tyler Rascoe, Jul 10 2024

A333489 Numbers k such that the k-th composition in standard order is an anti-run (no adjacent equal parts).

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 16, 17, 18, 20, 22, 24, 25, 32, 33, 34, 37, 38, 40, 41, 44, 45, 48, 49, 50, 52, 54, 64, 65, 66, 68, 69, 70, 72, 76, 77, 80, 81, 82, 88, 89, 96, 97, 98, 101, 102, 104, 105, 108, 109, 128, 129, 130, 132, 133, 134, 137, 140, 141

Offset: 1

Gus Wiseman, Mar 28 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The sequence together with the corresponding compositions begins:
    0: ()          33: (5,1)         70: (4,1,2)
    1: (1)         34: (4,2)         72: (3,4)
    2: (2)         37: (3,2,1)       76: (3,1,3)
    4: (3)         38: (3,1,2)       77: (3,1,2,1)
    5: (2,1)       40: (2,4)         80: (2,5)
    6: (1,2)       41: (2,3,1)       81: (2,4,1)
    8: (4)         44: (2,1,3)       82: (2,3,2)
    9: (3,1)       45: (2,1,2,1)     88: (2,1,4)
   12: (1,3)       48: (1,5)         89: (2,1,3,1)
   13: (1,2,1)     49: (1,4,1)       96: (1,6)
   16: (5)         50: (1,3,2)       97: (1,5,1)
   17: (4,1)       52: (1,2,3)       98: (1,4,2)
   18: (3,2)       54: (1,2,1,2)    101: (1,3,2,1)
   20: (2,3)       64: (7)          102: (1,3,1,2)
   22: (2,1,2)     65: (6,1)        104: (1,2,4)
   24: (1,4)       66: (5,2)        105: (1,2,3,1)
   25: (1,3,1)     68: (4,3)        108: (1,2,1,3)
   32: (6)         69: (4,2,1)      109: (1,2,1,2,1)

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000

Anti-runs summing to n are counted by A003242(n).
A triangle counting maximal anti-runs of compositions is A106356.
A triangle counting maximal runs of compositions is A238279 or A238130.
Partitions whose first differences are an anti-run are A238424.
All of the following pertain to compositions in standard order (A066099):
- Adjacent equal pairs are counted by A124762.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769.
- Strict compositions are ranked by A233564.
- Constant compositions are ranked by A272919.
- Normal compositions are ranked by A333217.
- Anti-runs are counted by A333381.
- Adjacent unequal pairs are counted by A333382.
Cf. A000120, A029931, A048793, A066099, A070939, A228351.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!MatchQ[stc[#],{_,x_,x_,_}]&]

A088218 Total number of leaves in all rooted ordered trees with n edges.

Original entry on oeis.org

1, 1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078, 5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650, 17672631900, 68923264410, 269128937220, 1052049481860, 4116715363800, 16123801841550, 63205303218876, 247959266474052

Offset: 0

Michael Somos, Sep 24 2003

Essentially the same as A001700, which has more information.
Note that the unique rooted tree with no edges has no leaves, so a(0)=1 is by convention. - Michael Somos, Jul 30 2011
Number of ordered partitions of n into n parts, allowing zeros (cf. A097070) is binomial(2*n-1,n) = a(n) = essentially A001700. - Vladeta Jovovic, Sep 15 2004
Hankel transform is A000027; example: Det([1,1,3,10;1,3,10,35;3,10,35,126; 10,35,126,462]) = 4. - Philippe Deléham, Apr 13 2007
a(n) is the number of functions f:[n]->[n] such that for all x,y in [n] if xA045992(n). - Geoffrey Critzer, Apr 02 2009
Hankel transform of the aeration of this sequence is A000027 doubled: 1,1,2,2,3,3,... - Paul Barry, Sep 26 2009
The Fi1 and Fi2 triangle sums of A039599 are given by the terms of this sequence. For the definitions of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011
Alternating row sums of Riordan triangle A094527. See the Philippe Deléham formula. - Wolfdieter Lang, Nov 22 2012
(-2)*a(n) is the Z-sequence for the Riordan triangle A110162. For the notion of Z- and A-sequences for Riordan arrays see the W. Lang link under A006232 with details and references. - Wolfdieter Lang, Nov 22 2012
From Gus Wiseman, Jun 27 2021: (Start)
Also the number of integer compositions of 2n with alternating (or reverse-alternating) sum 0 (ranked by A344619). This is equivalent to Ran Pan's comment at A001700. For example, the a(0) = 1 through a(3) = 10 compositions are:
  ()  (11)  (22)    (33)
            (121)   (132)
            (1111)  (231)
                    (1122)
                    (1221)
                    (2112)
                    (2211)
                    (11121)
                    (12111)
                    (111111)
For n > 0, a(n) is also the number of integer compositions of 2n with alternating sum 2.
(End)
Number of terms in the expansion of (x_1+x_2+...+x_n)^n. - César Eliud Lozada, Jan 08 2022

			G.f. = 1 + x + 3*x^2 + 10*x^3 + 35*x^4 + 126*x^5 + 462*x^6 + 1716*x^7 + ...
The five rooted ordered trees with 3 edges have 10 leaves.
..x........................
..o..x.x..x......x.........
..o...o...o.x..x.o..x.x.x..
..r...r....r....r.....r....

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
B. Dasarathy and C. Yang, A transformation on ordered trees, Comput. J. 23 (1980) 161-164. - _Nachum Dershowitz_, Sep 01 2016
Toufik Mansour and Mark Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
Anthony Mansuy, Preordered forests, packed words and contraction algebras, J. Algebra 411 (2014) 259-311.
Mircea Merca, A Note on Cosine Power Sums, J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, arXiv preprint arXiv:1108.2993 [hep-ph], 2011.

Same as A001700 modulo initial term and offset.
First differences are A024718.
Main diagonal of A071919 and of A305161.
A signed version is A110556.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A003242 counts anti-run compositions.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A106356 counts compositions by number of maximal anti-runs.
A124754 gives the alternating sum of standard compositions.
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218 (this sequence), 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 (this sequence), 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. A000027, A000070, A000097, A000108, A001622, A006232, A008965, A039599, A045992, A058696, A094527, A097070, A110162, A110555, A180662, A238279, A239830, A325534, A325535, A333213, A344607, A344611, A344617.

[Binomial(2*n-1, n): n in [0..30]]; // Vincenzo Librandi, Aug 07 2014

seq(binomial(2*n-1, n),n=0..24); # Peter Luschny, Sep 22 2014

a[ n_] := SeriesCoefficient[(1 - x)^-n, {x, 0, n}];
c = (1 - (1 - 4 x)^(1/2))/(2 x);CoefficientList[Series[1/(1-(c-1)),{x,0,20}],x] (* Geoffrey Critzer, Dec 02 2010 *)
Table[Binomial[2 n - 1, n], {n, 0, 20}] (* Vincenzo Librandi, Aug 07 2014 *)
a[ n_] := If[ n < 0, 0, With[ {m = 2 n}, m! SeriesCoefficient[ (1 + BesselI[0, 2 x]) / 2, {x, 0, m}]]]; (* Michael Somos, Nov 22 2014 *)

{a(n) = sum( i=0, n, binomial(n+i-2,i))};

{a(n) = if( n<0, 0, polcoeff( (1 + 1 / sqrt(1 - 4*x + x * O(x^n))) / 2, n))};

{a(n) = if( n<0, 0, polcoeff( 1 / (1 - x + x * O(x^n))^n, n))};

{a(n) = if( n<0, 0, binomial( 2*n - 1, n))};

{a(n) = if( n<1, n==0, polcoeff( subst((1 - x) / (1 - 2*x), x, serreverse( x - x^2 + x * O(x^n))), n))};

def A088218(n):
    return rising_factorial(n,n)/falling_factorial(n,n)
[A088218(n) for n in (0..24)]  # Peter Luschny, Nov 21 2012

G.f.: (1 + 1 / sqrt(1 - 4*x)) / 2.
a(n) = binomial(2*n - 1, n).
a(n) = (n+1)*A000108(n)/2, n>=1. - B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Feb 05 2002 (in A060150)
a(n) = (0^n + C(2n, n))/2. - Paul Barry, May 21 2004
a(n) is the coefficient of x^n in 1 / (1 - x)^n and also the sum of the first n coefficients of 1 / (1 - x)^n. Given B(x) with the property that the coefficient of x^n in B(x)^n equals the sum of the first n coefficients of B(x)^n, then B(x) = B(0) / (1 - x).
G.f.: 1 / (2 - C(x)) = (1 - x*C(x))/sqrt(1-4*x) where C(x) is g.f. for Catalan numbers A000108. Second equation added by Wolfdieter Lang, Nov 22 2012.
From Paul Barry, Nov 02 2004: (Start)
a(n) = Sum_{k=0..n} binomial(2*n, k)*cos((n-k)*Pi);
a(n) = Sum_{k=0..n} binomial(n, (n-k)/2)*(1+(-1)^(n-k))*cos(k*Pi/2)/2 (with interpolated zeros);
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*cos((n-2*k)*Pi/2) (with interpolated zeros); (End)
a(n) = A110556(n)*(-1)^n, central terms in triangle A110555. - Reinhard Zumkeller, Jul 27 2005
a(n) = Sum_{0<=k<=n} A094527(n,k)*(-1)^k. - Philippe Deléham, Mar 14 2007
From Paul Barry, Mar 29 2010: (Start)
G.f.: 1/(1-x/(1-2x/(1-(1/2)x/(1-(3/2)x/(1-(2/3)x/(1-(4/3)x/(1-(3/4)x/(1-(5/4)x/(1-... (continued fraction);
E.g.f.: (of aerated sequence) (1 + Bessel_I(0, 2*x))/2. (End)
a(n + 1) = A001700(n). a(n) = A024718(n) - A024718(n - 1).
E.g.f.: E(x) = 1+x/(G(0)-2*x) ; G(k) = (k+1)^2+2*x*(2*k+1)-2*x*(2*k+3)*((k+1)^2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 21 2011
a(n) = Sum_{k=0..n}(-1)^k*binomial(2*n,n+k). - Mircea Merca, Jan 28 2012
a(n) = rf(n,n)/ff(n,n), where rf is the rising factorial and ff the falling factorial. - Peter Luschny, Nov 21 2012
D-finite with recurrence: n*a(n) +2*(-2*n+1)*a(n-1) = 0. - R. J. Mathar, Dec 04 2012
a(n) = hypergeom([1-n,-n],[1],1). - Peter Luschny, Sep 22 2014
G.f.: 1 + x/W(0), where W(k) = 4*k+1 - (4*k+3)*x/(1 - (4*k+1)*x/(4*k+3 - (4*k+5)*x/(1 - (4*k+3)*x/W(k+1)  ))) ; (continued fraction). - Sergei N. Gladkovskii, Nov 13 2014
a(n) = A000984(n) + A001791(n). - Gus Wiseman, Jun 28 2021
E.g.f.: (1 + exp(2*x) * BesselI(0,2*x)) / 2. - Ilya Gutkovskiy, Nov 03 2021
From Amiram Eldar, Mar 12 2023: (Start)
Sum_{n>=0} 1/a(n) = 5/3 + 4*Pi/(9*sqrt(3)).
Sum_{n>=0} (-1)^n/a(n) = 3/5 - 8*log(phi)/(5*sqrt(5)), where phi is the golden ratio (A001622). (End)
a(n) ~ 2^(2*n-1)/sqrt(n*Pi). - Stefano Spezia, Apr 17 2024

A097805 Number of compositions of n with k parts, T(n, k) = binomial(n-1, k-1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Aug 25 2004

Previous name was: Riordan array (1, 1/(1-x)) read by rows.
Note this Riordan array would be denoted (1, x/(1-x)) by some authors.
Columns have g.f. (x/(1-x))^k. Reverse of A071919. Row sums are A011782. Antidiagonal sums are Fibonacci(n-1). Inverse as Riordan array is (1, 1/(1+x)). A097805=B*A059260*B^(-1), where B is the binomial matrix.
(0,1)-Pascal triangle. - Philippe Deléham, Nov 21 2006
(n+1) * each term of row n generates triangle A127952: (1; 0, 2; 0, 3, 3; 0, 4, 8, 4; ...). - Gary W. Adamson, Feb 09 2007
Triangle T(n,k), 0<=k<=n, read by rows, given by [0,1,0,0,0,0,0,...] DELTA [1,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 12 2008
From Paul Weisenhorn, Feb 09 2011: (Start)
Triangle read by rows: T(r,c) is the number of unordered partitions of n=r*(r+1)/2+c into (r+1) parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2.
Triangle read by rows: T(r,c) is the number of unordered partitions of the number n=r*(r+1)/2+(c-1) into r parts < (r+1) and at most pairs of equal parts and parts in neighboring pairs have difference 2. (End)
Triangle read by rows: T(r,c) is the number of ordered partitions (compositions) of r into c parts. - Juergen Will, Jan 04 2016
From Tom Copeland, Oct 25 2012: (Start)
Given a basis composed of a sequence of polynomials p_n(x) characterized by ladder (creation / annihilation, or raising / lowering) operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x) with p_0(x)=1, giving the number operator # p_n(x) = RL p_n(x) = n p_n(x), the lower triangular padded Pascal matrix Pd (A097805) serves as a matrix representation of the operator exp(R^2*L) = exp(R#) =
  1) exp(x^2D) for the set x^n  and
  2) D^(-1) exp(t*x)D for the set x^n/n! (see A218234).
  (End)
From James East, Apr 11 2014: (Start)
Square array a(m,n) with m,n=0,1,2,... read by off-diagonals.
a(m,n) gives the number of order-preserving functions f:{1,...,m}->{1,...,n}. Order-preserving means that xa(n,n)=A088218(n) is the size of the semigroup O_n of all order-preserving transformations of {1,...,n}.
Read as a triangle, this sequence may be obtained by augmenting Pascal's triangle by appending the column 1,0,0,0,... on the left.
(End)
A formula based on the partitions of n with largest part k is given as a Sage program below. The 'conjugate' formula leads to A048004. - Peter Luschny, Jul 13 2015
From Wolfdieter Lang, Feb 17 2017: (Start)
The transposed of this lower triangular Riordan matrix of the associated type T provides the transition matrix between the monomial basis {x^n}, n >= 0, and the basis {y^n}, n >= 0, with y = x/(1-x): x^0 = 1 = y^0, x^n = Sum_{m >= n} Ttrans(n,m) y^m, for n >= 1, with Ttrans(n,m) = binomial(m-1,n-1).
Therefore, if a transformation with this Riordan matrix from a sequence {a} to the sequence {b} is given by b(n) = Sum_{m=0..n} T(n, m)*a(m), with T(n, m) = binomial(n-1, m-1), for n >= 1, then Sum_{n >= 0} a(n)*x^n = Sum_{n >= 0} b(n)*y^n, with y = x/(1-x) and vice versa. This is a modified binomial transformation; the usual one belongs to the Pascal Riordan matrix A007318. (End)
From Gus Wiseman, Jan 23 2022: (Start)
Also the number of compositions of n with alternating sum k, with k ranging from -n to n in steps of 2. For example, row n = 6 counts the following compositions (empty column indicated by dot):
  .  (15)  (24)    (33)      (42)     (51)   (6)
           (141)   (132)     (123)    (114)
           (1113)  (231)     (222)    (213)
           (1212)  (1122)    (321)    (312)
           (1311)  (1221)    (1131)   (411)
                   (2112)    (2121)
                   (2211)    (3111)
                   (11121)   (11112)
                   (12111)   (11211)
                   (111111)  (21111)
The reverse-alternating version is the same. Counting compositions by all three parameters (sum, length, alternating sum) gives A345197. Compositions of 2n with alternating sum 2k with k ranging from -n + 1 to n are A034871. (End)
Also the convolution triangle of A000012. - Peter Luschny, Oct 07 2022
From Sergey Kitaev, Nov 18 2023: (Start)
Number of permutations of length n avoiding simultaneously the patterns 123 and 132 with k right-to-left maxima. A right-to-left maximum in a permutation a(1)a(2)...a(n) is position i such that a(j) < a(i) for all i < j.
Number of permutations of length n avoiding simultaneously the patterns 231 and 312 with k right-to-left minima (resp., left-to-right maxima). A right-to-left minimum (resp., left-to-right maximum) in a permutation a(1)a(2)...a(n) is position i such that a(j) > a(i) for all j > i (resp., a(j) < a(i) for all j < i).
Number of permutations of length n avoiding simultaneously the patterns 213 and 312 with k right-to-left maxima (resp., left-to-right maxima).
Number of permutations of length n avoiding simultaneously the patterns 213 and 231 with k right-to-left maxima (resp., right-to-left minima). (End)

			G.f. = 1 + x * (x + x^3 * (1 + x) + x^6 * (1 + x)^2 + x^10 * (1 + x)^3 + ...). - _Michael Somos_, Aug 20 2006
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 1 1
3:   0 1 2  1
4:   0 1 3  3  1
5:   0 1 4  6  4   1
6:   0 1 5 10 10   5   1
7:   0 1 6 15 20  15   6  1
8:   0 1 7 21 35  35  21  7  1
9:   0 1 8 28 56  70  56 28  8 1
10:  0 1 9 36 84 126 126 84 36 9  1
... reformatted _Wolfdieter Lang_, Jul 31 2017
From _Paul Weisenhorn_, Feb 09 2011: (Start)
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+c = 18 with (r+1)=6 summands: (5+5+4+2+1+1), (5+5+3+3+1+1), (5+4+4+3+1+1), (5+5+3+2+2+1), (5+4+4+2+2+1), (5+4+3+3+2+1).
T(r=5,c=3) = binomial(4,2) = 6 unordered partitions of the number n = r*(r+1)/2+(c-1) = 17 with r=5 summands: (5+5+4+2+1), (5+5+3+3+1), (5+5+3+2+2), (5+4+4+3+1), (5+4+4+2+2), (5+4+3+3+2).  (End)
From _James East_, Apr 11 2014: (Start)
a(0,0)=1 since there is a unique (order-preserving) function {}->{}.
a(m,0)=0 for m>0 since there is no function from a nonempty set to the empty set.
a(3,2)=4 because there are four order-preserving functions {1,2,3}->{1,2}: these are [1,1,1], [2,2,2], [1,1,2], [1,2,2]. Here f=[a,b,c] denotes the function defined by f(1)=a, f(2)=b, f(3)=c.
a(2,3)=6 because there are six order-preserving functions {1,2}->{1,2,3}: these are [1,1], [1,2], [1,3], [2,2], [2,3], [3,3].
(End)

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Section 7.2.1.3, 2011.

Alois P. Heinz, Rows n = 0..140, flattened
Tom Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
James East and Peter J. McNamara, On the work performed by a transformation semigroup, Australas. J. Combin. 49 (2011), 95-109.
Tian Han and Sergey Kitaev, Joint distributions of statistics over permutations avoiding two patterns of length 3, arXiv:2311.02974 [math.CO], 2023.
Wolfdieter Lang, On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles, arXiv:1708.01421 [math.NT], August 2017.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 8.
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901. - _Juergen Will_, Jan 02 2016
Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.

Case m=0 of the polynomials defined in A278073.
Cf. A000012 (diagonal), A011782 (row sums), A088218 (central terms).
Cf. A007318, A048004, A127952, A118800, A200139, A130595, A167374.
The terms just left of center in odd-indexed rows are A001791, even A002054.
The odd-indexed rows are A034871.
Row sums without the center are A058622.
The unordered version is A072233, without zeros A008284.
Right half without center has row sums A027306(n-1).
Right half with center has row sums A116406(n).
Left half without center has row sums A294175(n-1).
Left half with center has row sums A058622(n-1).
A025047 counts alternating compositions.
A098124 counts balanced compositions, unordered A047993.
A106356 counts compositions by number of maximal anti-runs.
A344651 counts partitions by sum and alternating sum.
A345197 counts compositions by sum, length, and alternating sum.
Cf. A000346, A000984, A001700, A008549, A008965, A114121, A124754, A238279, A345907, A345908, A346632.

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
      expand(add(b(n-i*j, i-1, p+j)/j!*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, May 25 2014
# Alternatively:
T := proc(k,n) option remember;
if k=n then 1 elif k=0 then 0 else
add(T(k-1,n-i), i=1..n-k+1) fi end:
A097805 := (n,k) -> T(k,n):
for n from 0 to 12 do seq(A097805(n,k), k=0..n) od; # Peter Luschny, Mar 12 2016
# Uses function PMatrix from A357368.
PMatrix(10, n -> 1);  # Peter Luschny, Oct 07 2022

T[0, 0] = 1; T[n_, k_] := Binomial[n-1, k-1]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 03 2014, after Paul Weisenhorn *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==k&]],{n,0,10},{k,0,n}] (* Gus Wiseman, Jan 23 2022 *)

{a(n) = my(m); if( n<2, n==0, n--; m = (sqrtint(8*n + 1) - 1)\2; binomial(m-1, n - m*(m + 1)/2))}; /* Michael Somos, Aug 20 2006 */

T(n,k) = if (k==0, 0^n, binomial(n-1, k-1)); \\ Michel Marcus, May 06 2022

row(n) = vector(n+1, k, k--; if (k==0, 0^n, binomial(n-1, k-1))); \\ Michel Marcus, May 06 2022

from math import comb
def T(n, k): return comb(n-1, k-1) if k != 0 else k**n  # Peter Luschny, May 06 2022

# Illustrates a basic partition formula, is not efficient as a program for large n.
def A097805_row(n):
    r = []
    for k in (0..n):
        s = 0
        for q in Partitions(n, max_part=k, inner=[k]):
            s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))
        r.append(s)
    return r
[A097805_row(n) for n in (0..9)] # Peter Luschny, Jul 13 2015

Number triangle T(n, k) defined by T(n,k) = Sum_{j=0..n} binomial(n, j)*if(k<=j, (-1)^(j-k), 0).
T(r,c) = binomial(r-1,c-1), 0 <= c <= r. - Paul Weisenhorn, Feb 09 2011
G.f.: (-1+x)/(-1+x+x*y). - R. J. Mathar, Aug 11 2015
a(0,0) = 1, a(n,k) = binomial(n-1,n-k) = binomial(n-1,k-1) Juergen Will, Jan 04 2016
G.f.: (x^1 + x^2 + x^3 + ...)^k = (x/(1-x))^k. - Juergen Will, Jan 04 2016
From Tom Copeland, Nov 15 2016: (Start)
E.g.f.: 1 + x*[e^((x+1)t)-1]/(x+1).
This padded Pascal matrix with the odd columns negated is NpdP = M*S = S^(-1)*M^(-1) = S^(-1)*M, where M(n,k) = (-1)^n A130595(n,k), the inverse Pascal matrix with the odd rows negated, S is the summation matrix A000012, the lower triangular matrix with all elements unity, and S^(-1) = A167374, a finite difference matrix. NpdP is self-inverse, i.e., (M*S)^2 = the identity matrix, and has the e.g.f. 1 - x*[e^((1-x)t)-1]/(1-x).
M = NpdP*S^(-1) follows from the well-known recursion property of the Pascal matrix, implying NpdP = M*S.
The self-inverse property of -NpdP is implied by the self-inverse relation of its embedded signed Pascal submatrix M (cf. A130595). Also see A118800 for another proof.
Let P^(-1) be A130595, the inverse Pascal matrix. Then T = A200139*P^(-1) and T^(-1) = padded P^(-1) = P*A097808*P^(-1). (End)
The center (n>0) is T(2n+1,n+1) = A000984(n) = 2*A001700(n-1) = 2*A088218(n) = A126869(2n) = 2*A138364(2n-1). - Gus Wiseman, Jan 25 2022

Corrected by Philippe Deléham, Oct 05 2005

New name using classical terminology by Peter Luschny, Feb 05 2019

A124767 Number of level runs for compositions in standard order.

Original entry on oeis.org

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

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

For n > 0, a(n) is one more than the number of adjacent unequal terms in the n-th composition in standard order. Also the number of runs in the same composition. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; the level runs are 2; 1,1; so a(11) = 2.
The table starts:
  0
  1
  1 1
  1 2 2 1
  1 2 1 2 2 3 2 1
  1 2 2 2 2 2 3 2 2 3 2 3 2 3 2 1
  1 2 2 2 1 3 3 2 2 3 1 2 3 4 3 2 2 3 3 3 3 3 4 3 2 3 2 3 2 3 2 1
The 1234567th composition in standard order is (3,2,1,2,2,1,2,5,1,1,1) with runs ((3),(2),(1),(2,2),(1),(2),(5),(1,1,1)), so a(1234567) = 8. - _Gus Wiseman_, Apr 08 2020

Row-lengths are A011782.
Compositions counted by number of runs are A238279 or A333755.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Weakly decreasing compositions are A114994.
- Adjacent equal pairs are counted by A124762.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767 (this sequence).
- Weakly increasing compositions are A225620.
- Strict compositions A233564.
- Constant compositions are A272919.
- Anti-runs are counted by A333381.
- Adjacent unequal pairs are counted by A333382.
- Anti-run compositions are A333489.
- Runs-resistance is A333628.
- Run-lengths are A333769 (triangle).
Cf. A029931, A048793, A066099, A106356, A228351, A318928, A329744, A333217, A333219, A333627.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Split[stc[n]]],{n,0,100}] (* Gus Wiseman, Apr 17 2020 *)

a(0) = 0, a(n) = 1 + Sum_{1<=i=1 0.

For n > 0, a(n) = A333382(n) + 1. - Gus Wiseman, Apr 08 2020

A333755 Triangle read by rows where T(n,k) is the number of compositions of n with k runs, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 4, 1, 0, 0, 2, 10, 4, 0, 0, 0, 4, 12, 14, 2, 0, 0, 0, 2, 22, 29, 10, 1, 0, 0, 0, 4, 26, 56, 36, 6, 0, 0, 0, 0, 3, 34, 100, 86, 31, 2, 0, 0, 0, 0, 4, 44, 148, 200, 99, 16, 1, 0, 0, 0, 0, 2, 54, 230, 374, 278, 78, 8, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Apr 10 2020

Except for a(1) = 0, the data is identical to A238130 shifted right once. However, in A238130, each row after the first ends with a zero, while here each row after the first starts with a zero.

			Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   3   4   1   0
   0   2  10   4   0   0
   0   4  12  14   2   0   0
   0   2  22  29  10   1   0   0
   0   4  26  56  36   6   0   0   0
   0   3  34 100  86  31   2   0   0   0
   0   4  44 148 200  99  16   1   0   0   0
   0   2  54 230 374 278  78   8   0   0   0   0
Row n = 6 counts the following compositions (empty column indicated by dot):
  .  (6)       (15)     (123)    (1212)
     (33)      (24)     (132)    (2121)
     (222)     (42)     (141)
     (111111)  (51)     (213)
               (114)    (231)
               (411)    (312)
               (1113)   (321)
               (1122)   (1131)
               (2211)   (1221)
               (3111)   (1311)
               (11112)  (2112)
               (21111)  (11121)
                        (11211)
                        (12111)

Removing all zeros gives A238279.
The version for anti-runs is A106356.
The k-th composition in standard-order has A124767(k) runs.
The version counting descents is A238343.
The version counting weak ascents is A333213.
Cf. A066099, A124762, A238130, A272919, A333381, A333382, A333489.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]==k&]],{n,0,10},{k,0,n}]

A025047 Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 12, 19, 29, 48, 75, 118, 186, 293, 460, 725, 1139, 1789, 2814, 4422, 6949, 10924, 17168, 26979, 42404, 66644, 104737, 164610, 258707, 406588, 639009, 1004287, 1578363, 2480606, 3898599, 6127152, 9629623, 15134213, 23785388, 37381849, 58750468

Offset: 0

David W. Wilson

nonn

Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(7)=19 such compositions of 7:
[ 1] +  [ 1 2 1 2 1 ]
[ 2] +  [ 1 2 1 3 ]
[ 3] +  [ 1 3 1 2 ]
[ 4] +  [ 1 4 2 ]
[ 5] +  [ 1 5 1 ]
[ 6] +  [ 1 6 ]
[ 7] -  [ 2 1 3 1 ]
[ 8] -  [ 2 1 4 ]
[ 9] +  [ 2 3 2 ]
[10] +  [ 2 4 1 ]
[11] +  [ 2 5 ]
[12] -  [ 3 1 2 1 ]
[13] -  [ 3 1 3 ]
[14] +  [ 3 4 ]
[15] -  [ 4 1 2 ]
[16] -  [ 4 3 ]
[17] -  [ 5 2 ]
[18] -  [ 6 1 ]
[19] 0  [ 7 ]
For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'),
and for A025049(7)-1=8 the first two parts are decreasing (marked by '-').
The composition into one part is counted by both A025048 and A025049.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3333
Edward A. Bender and E. Rodney Canfield, Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities, Electronic Journal of Combinatorics 17 (2010), #R145.

Dominated by A003242 (anti-run compositions), complement A261983.
The ascending case is A025048.
The descending case is A025049.
The version allowing pairs (x,x) is A344604.
These compositions are ranked by A345167, permutations A349051.
The complement is counted by A345192, ranked by A345168.
The version for patterns is A345194 (with twins: A344605).
A001250 counts alternating permutations, complement A348615.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.

b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
      b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
    end:
a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 31 2024

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],wigQ]],{n,0,15}] (* Gus Wiseman, Jun 17 2021 *)

D(n,f)={my(M=matrix(n,n,j,k,k>=j), s=M[,n]); for(b=1, n, f=!f; M=matrix(n,n,j,k,if(k1, M[j-k,k-1]), M[j-k,n]-M[j-k,k] ))); for(k=2, n, M[,k]+=M[,k-1]); s+=M[,n]); s~}
seq(n) = concat([1], D(n,0) + D(n,1) - vector(n,j,1)) \\ Andrew Howroyd, Jan 31 2024

a(n) = A025048(n) + A025049(n) - 1 = sum_k[A059881(n, k)] = sum_k[S(n, k) + T(n, k)] - 1 where if n>k>0 S(n, k) = sum_j[T(n - k, j)] over j>k and T(n, k) = sum_j[S(n - k, j)] over k>j (note reversal) and if n>0 S(n, n) = T(n, n) = 1; S(n, k) = A059882(n, k), T(n, k) = A059883(n, k). - Henry Bottomley, Feb 05 2001
a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - Vaclav Kotesovec, Sep 12 2014
a(n) = A344604(n) + 1 - n mod 2. - Gus Wiseman, Jun 17 2021

Better name using a comment of Franklin T. Adams-Watters by Peter Luschny, Oct 31 2021

A325535 Number of inseparable partitions of n; see Comments.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 5, 5, 8, 11, 16, 19, 28, 35, 48, 60, 79, 99, 131, 161, 205, 256, 324, 397, 498, 609, 755, 921, 1131, 1372, 1677, 2022, 2452, 2952, 3561, 4260, 5116, 6102, 7291, 8667, 10309, 12210, 14477, 17087, 20177, 23752, 27957, 32804, 38496, 45049, 52704

Offset: 0

Clark Kimberling, May 08 2019

Definition: a partition is separable if there is an ordering of its parts in which no consecutive parts are identical; otherwise the partition is inseparable.

A partition with k parts is inseparable if and only if there is a part whose multiplicity is greater than ceiling(k/2). - Andrew Howroyd, Jan 17 2024

			For n=5, the partition 1+2+2 is separable as 2+1+2, and 2+1+1+1 is inseparable.
From _Gus Wiseman_, Jun 27 2020: (Start)
The a(2) = 2 through a(9) = 11 inseparable partitions:
  11   111   22     2111    33       2221      44         333
             1111   11111   222      4111      2222       3222
                            3111     31111     5111       6111
                            21111    211111    41111      22221
                            111111   1111111   221111     51111
                                               311111     321111
                                               2111111    411111
                                               11111111   2211111
                                                          3111111
                                                          21111111
                                                          111111111
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The Heinz numbers of these partitions are given by A335448.
Strict partitions are counted by A000009 and are all separable.
Anti-run compositions are counted by A003242.
Anti-run patterns are counted by A005649.
Partitions whose differences are an anti-run are A238424.
Separable partitions are counted by A325534.
Anti-run compositions are ranked by A333489.
Anti-run permutations of prime indices are counted by A335452.
Cf. A000041, A106356, A238594, A261962, A292884, A332668, A333175.

u=Table[Length[Select[Map[Quotient[(1 + Length[#]), Max[Map[Length, Split[#]]]] &,
IntegerPartitions[nn]], # > 1 &]], {nn, 50}]
Table[PartitionsP[n] - u[[n]], {n, 1, Length[u]}]
(* Peter J. C. Moses, May 07 2019 *)
Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!MatchQ[#,{_,x_,x_,_}]&]=={}&]],{n,10}] (* Gus Wiseman, Jun 27 2020 *)

seq(n) = {Vec(sum(k=1, (n+1)\2, x^(2*k-1)*(1 + x - x^(k-1))/((1-x^(k+1))*prod(j=1, k-1, 1 - x^j, 1 + O(x^(n-2*k+2)))), O(x*x^n)), -(n+1))} \\ Andrew Howroyd, Jan 17 2024

a(n) = A000041(n) - A325534(n).

a(n) = Sum_{k>=1} x^(2*k-1)*(1 + x - x^(k-1))/((1-x^(k+1))*Product_{j=1..k-1} (1 - x^j)). - Andrew Howroyd, Jan 17 2024

a(0)=0 prepended by Andrew Howroyd, Jan 31 2024

Showing 1-10 of 185 results. Next

cp's OEIS Frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A066099 Triangle read by rows, in which row n lists the compositions of n in reverse lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Sage

Formula

Extensions

A238279 Triangle read by rows: T(n,k) is the number of compositions of n into nonzero parts with k parts directly followed by a different part, n>=0, 0<=k<=A004523(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A333489 Numbers k such that the k-th composition in standard order is an anti-run (no adjacent equal parts).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A088218 Total number of leaves in all rooted ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Sage

Formula

A097805 Number of compositions of n with k parts, T(n, k) = binomial(n-1, k-1) for n, k >= 1 and T(n, 0) = 0^n, triangle read by rows for n >= 0 and 0 <= k <= n.

Views

Author

Keywords

Comments