A256161 -id:A256161 - cp's OEIS frontend

A007476 Shifts 2 places left under binomial transform.

1, 1, 1, 2, 4, 9, 23, 65, 199, 654, 2296, 8569, 33825, 140581, 612933, 2795182, 13298464, 65852873, 338694479, 1805812309, 9963840219, 56807228074, 334192384460, 2026044619017, 12642938684817, 81118550133657, 534598577947465, 3615474317688778, 25070063421597484

Offset: 0

N. J. A. Sloane

Starting (1, 2, 4, 9, 23, ...) = row sums of triangle A153859. - Gary W. Adamson, Jan 02 2009
Binomial transform of the sequence starting (1, 1, 2, 4, 9, ...) = first differences of (1, 2, 4, 9, 23, ...); that is, (1, 2, 5, 14, 42, 134, 455, 1642, ...). - Gary W. Adamson, May 20 2013
Row sums of triangle A256161. - Margaret A. Readdy, Mar 16 2015
RG-words corresponding to set partitions of {1, ..., n} with every even entry appearing exactly once. - Margaret A. Readdy, Mar 16 2015
a(n) is the number of partitions of [n] whose blocks can be written such that the smallest elements form an increasing sequence and the largest elements form a decreasing sequence. a(5) = 9: 12345, 1235|4, 1245|3, 125|34, 1345|2, 135|24, 145|23, 15|234, 15|24|3. - Alois P. Heinz, Apr 24 2023

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..650 (first 101 terms from T. D. Noe)
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Yue Cai and Margaret Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015.
A. Claesson and T. Mansour, Permutations avoiding a pair of Babson-Steingrimsson patterns, arXiv:math/0107044 [math.CO], 2001-2010.
Rigoberto Flórez, José L. Ramírez, Fabio A. Velandia, and Diego Villamizar, Some Connections Between Restricted Dyck Paths, Polyominoes, and Non-Crossing Partitions, arXiv:2308.02059 [math.CO], 2023. See Table 1 p. 13.
N. J. A. Sloane, Transforms
L. Sze, OEIS conjecture 70

Cf. A000994, A000995, A092920, A153859.

Row sums of A246118.

a:= proc(n) option remember; `if`(n<2, 1,
      add(a(j)*binomial(n-2, j), j=0..n-2))
    end:
seq(a(n), n=0..31);  # Alois P. Heinz, Jul 29 2019

a[0] = a[1] = 1; a[n_] := a[n] = Sum[Binomial[n-2, k] a[k], {k, 0, n-2}]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Aug 08 2012, after Ralf Stephan *)

a(n)=if(n<2, 1, sum(k=0, n-2, binomial(n-2, k)*a(k))) /* Ralf Stephan; corrected by Manuel Blum, May 22 2010 */

G.f.: Sum_{k>=0} x^(2k)/(Product_{m=0..k-1} (1-mx) * Product_{m=0..k+1} (1-mx)).
G.f. A(x) satisfies A(x) = 1 + x + (x^2/(1-x))*A(x/(1-x)). - Vladimir Kruchinin, Nov 28 2011
a(n) = A000994(n) + A000995(n). - Peter Bala, Jan 27 2015

Spelling correction by Jason G. Wurtzel, Aug 22 2010

A246118 T(n,k), for n,k >= 1, is the number of partitions of the set [n] into k blocks, where, if the blocks are arranged in order of their minimal element, the odd-indexed blocks are all singletons.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 11, 6, 1, 0, 1, 5, 26, 23, 9, 1, 0, 1, 6, 57, 72, 50, 12, 1, 0, 1, 7, 120, 201, 222, 86, 16, 1, 0, 1, 8, 247, 522, 867, 480, 150, 20, 1, 0, 1, 9, 502, 1291, 3123, 2307, 1080, 230, 25, 1, 0, 1, 10, 1013, 3084, 10660, 10044, 6627, 2000, 355, 30, 1

Offset: 1

Peter Bala, Aug 14 2014

Unsigned matrix inverse of A246117. Analog of the Stirling numbers of the second kind, A048993.
This is the triangle of connection constants between the monomial polynomials x^n and the polynomial sequence [x, x^2, x^2*(x - 1), x^2*(x - 1)^2, x^2*(x - 1)^2*(x - 2), x^2*(x - 1)^2*(x - 2)^2, ...]. An example is given below.
Except for differences in offset, this triangle is the Galton array G(floor(k/2),1) in the notation of Neuwirth with inverse array G(-floor(n/2),1).
Essentially the same as A256161. - Peter Bala, Apr 14 2018
From Peter Bala, Feb 10 2020: (Start)
The sums S(n):= Sum_{k >= 0} k^n*(x^k/k!)^2, n = 2,3,4,..., can be expressed as a linear combination of the sums S(0) and S(1) with polynomial coefficients, namely, S(n) = E(n,x)*S(0) + (1/x)*O(n,x)* S(1,x), where E(n,x) = Sum_{k >= 1} T(n,2*k)*x^(2*k) and O(n,x) = Sum_{k >= 0} T(n,2*k+1)*x^(2*k+1) are the even and odd parts of the n-th row polynomial of this array. This result is the analog of the Dobinski formula Sum_{k >= 0} (k^n)*x^k/k! = exp(x)*Bell(n,x), where Bell(n,x) is the n-th row polynomial of A048993.
For example, for n = 6 we have S(6) = Sum_{k >= 1} k^6*(x^k/k!)^2 = (x^2 + 11*x^4 + x^6) * Sum_{k >= 0} (x^k/k!)^2 + (1/x)*(4*x^3 + 6*x^5) * Sum_{k >= 1} k*(x^k/k!)^2.
Setting x = 1 in the above result gives Sum_{k >= 0} k^n*/k!^2 = A000994(n)*Sum_{k >= 0} 1/k!^2 + A000995(n)*Sum_{k >= 1} k/k!^2. See A086880. (End)

			Triangle begins
n\k| 1    2    3    4    5    6    7    8
1  | 1
2  | 0    1
3  | 0    1    1
4  | 0    1    2    1
5  | 0    1    3    4    1
6  | 0    1    4   11    6    1
7  | 0    1    5   26   23    9    1
8  | 0    1    6   57   72   50   12    1
...
Connection constants: Row 6 = (0, 1, 4, 11, 6, 1) so
x^6 = x^2 + 4*x^2*(x - 1) + 11*x^2*(x - 1)^2 + 6*x^2*(x - 1)^2*(x - 2) + x^2*(x - 1)^2*(x - 2)^2.
Row 5 = [0, 1, 3, 4, 1]. There are 9 set partitions of {1,2,3,4,5} of the type described in the Name section:
= = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Number of      Set partitions                Count
blocks
= = = = = = = = = = = = = = = = = = = = = = = = = = = = =
2                {1}{2,3,4,5}                   1
3           {1}{2,4,5}{3}, {1}{2,3,5}{4},
            {1}{2,3,4}{5}                       3
4          {1}{2,3}{4}{5}, {1}{2,4}{3}{5},
           {1}{2,5}{3}{4}, {1}{2}{3}{4,5}       4
5          {1}{2}{3}{4}{5}                      1

Yue Cai and Margaret Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015.
Emrah Kiliç and Helmut Prodinger, Identities with Squares of Binomial Coefficients: an Elementary and Explicit Approach, Publications de l'Institut Mathématique (Beograd) (N.S.), Vol.99(113) (2016), 243-248. See p. 248.
Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Tech Report TR 99-05, 1999.
E. Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 (2001) 33-51.

Cf. A000295 (column 4), A007476 (row sums), A008277, A045618 (column 5), A048993, A246117 (unsigned matrix inverse), A256161, A000994, A000995, A086880.

Flatten[Table[Table[Sum[StirlingS2[j,Floor[k/2]] * StirlingS2[n-j-1,Floor[(k-1)/2]],{j,0,n-1}],{k,1,n}],{n,1,12}]] (* Vaclav Kotesovec, Feb 09 2015 *)

T(n,k) = Sum_{i = 0..n-1} Stirling2(i, floor(k/2))*Stirling2(n-i-1, floor((k - 1)/2)) for n,k >= 1.
Recurrence equation: T(1,1) = 1, T(n,1) = 0 for n >= 2; T(n,k) = 0 for k > n; otherwise T(n,k) = floor(k/2)*T(n-1,k) + T(n-1,k-1).
O.g.f. (with an extra 1): A(z) = 1 + Sum_{k >= 1} (x*z)^k/( ( Product_{i = 1..floor((k-1)/2)} (1 - i*z) ) * ( Product_{i = 1..floor(k/2)} (1 - i*z) ) ) = 1 + x*z + x^2*z^2 + (x^2 + x^3)*z^3 + (x^2 + 2*x^3 + x^4)*z^4 + .... satisfies A(z) = 1 + x*z + x^2*z^2/(1 - z)*A(z/(1 - z)).
k-th column generating function z^k/( ( Product_{i = 1..floor((k-1)/2)} (1 - i*z) ) * ( Product_{i = 1..floor(k/2)} (1 - i*z) ) ).
Recurrence for row polynomials: R(n,x) = x^2*Sum_{k = 0..n-2} binomial(n-2,k)*R(k,x) with initial conditions R(0,x) = 1 and R(1,x) = x. Compare with the recurrence satisfied by the Bell polynomials: Bell(n,x) = x*Sum_{k = 0..n-1} binomial(n-1,k) * Bell(k,x).
Row sums are A007476.

cp's OEIS Frontend

A007476 Shifts 2 places left under binomial transform.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions