A208738 -id:A208738 - cp's OEIS frontend

A208739 2^n minus the number of partitions of n.

0, 1, 2, 5, 11, 25, 53, 113, 234, 482, 982, 1992, 4019, 8091, 16249, 32592, 65305, 130775, 261759, 523798, 1047949, 2096360, 4193302, 8387353, 16775641, 33552474, 67106428, 134214718, 268431738, 536866347, 1073736220, 2147476806, 4294958947, 8589924449

Offset: 0

David Nacin, Mar 01 2012

nonn

Gives the number of multisets that occurring as the peak heights multiset of a Dyck (n+1)-path minus the number of multisets occurring as the peak heights multiset of a Dyck n-path. We use the definition given by Callan and Deutsch (see reference). A Dyck n-path is a lattice path of n upsteps U (changing by (1,1)) and n downsteps D (changing by (1,-1)) that starts at the origin and never goes below the x-axis. A peak is an occurrence of U D and the peak height is the y-coordinate of the vertex between its U and D.

			For n=2 the possibilities are UDUD, UUDD giving us multisets of {1,1} and {2} respectively.  For n=1 there is only the one possibility UD giving us {1}.  Thus a(1) = 2 - 1 = 1.

D. Callan and E. Deutsch, Problems and Solutions: 11624, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.

Cf. A000041, A000079, A208738, A208740.

a:= n-> 2^n-combinat[numbpart](n):
seq(a(n), n=0..35);  # Alois P. Heinz, Feb 14 2024

Mathematica
```
Table[2^n - PartitionsP[n], {n, 0, 40}]
```

a(n) = 2^n - numbpart(n); \\ Michel Marcus, Jul 05 2018

a(n) = A208738(n+1) - A208738(n).
G.f.: 1/(1-2x) - Product_{k>0} 1/(1-x^k).
a(n) = A000079(n) - A000041(n). - Alois P. Heinz, Feb 14 2024

Missing a(0)=0 inserted by Alois P. Heinz, Feb 14 2024

A208740 Number of multisets that occurring as the peak heights multiset of a Dyck n-path that are the also the peak heights multiset of a smaller Dyck path.

Original entry on oeis.org

0, 0, 0, 1, 4, 13, 34, 83, 189, 415, 885, 1853, 3824, 7819, 15876, 32084, 64621, 129860, 260547, 522201, 1045862, 2093646, 4189796, 8382845, 16769878, 33545136, 67097132, 134202986, 268416996, 536847887, 1073713195, 2147448177, 4294923476, 8589880629

Offset: 1

David Nacin, Mar 01 2012

nonn

We use the definition given by Callan and Deutsch (see reference). A Dyck n-path is a lattice path of n upsteps U (changing by (1,1)) and n downsteps D (changing by (1,-1)) that starts at the origin and never goes below the x-axis. A peak is an occurrence of U D and the peak height is the y-coordinate of the vertex between its U and D.

Also the number of nonempty multisets S of positive integers satisfying max(S) + |S| <= n <= sum(S).

			For a Dyck 4-path there is only one peak heights multiset occurring also for a Dyck 3-path. This is {2,2} and occurs for both UUDDUUDD when n=4 and UUDUDD when n=3.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
D. Callan and E. Deutsch, Problems and Solutions: 11624, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.

Cf. A000070, A208738, A208739.

Table[2^(n - 1) - Sum[PartitionsP[k], {k, 0, n - 1}], {n, 1, 40}]

a(n) = 2^(n-1) - sum(k=0, n-1, numbpart(k)); \\ Michel Marcus, Jul 07 2018

a(n) = 2^(n-1) - A000070(n-1).
a(n) = A208738(n) - 2^(n-1).
G.f.: x/(1-2*x)-(x/(1-x))*product(m>=1, 1/(1-x^m)).

cp's OEIS Frontend

A208739 2^n minus the number of partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions