login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A095149 Triangle read by rows: Aitken's array (A011971) but with a leading diagonal before it given by the Bell numbers (A000110), 1, 1, 2, 5, 15, 52, ... 10
1, 1, 1, 2, 1, 2, 5, 2, 3, 5, 15, 5, 7, 10, 15, 52, 15, 20, 27, 37, 52, 203, 52, 67, 87, 114, 151, 203, 877, 203, 255, 322, 409, 523, 674, 877, 4140, 877, 1080, 1335, 1657, 2066, 2589, 3263, 4140, 21147, 4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Or, prefix Aitken's array (A011971) with a leading diagonal of 0's and take the differences of each row to get the new triangle.

With offset 1, triangle read by rows: T(n,k) is the number of partitions of the set {1,2,...,n} in which k is the largest entry in the block containing 1 (1 <= k <= n). - Emeric Deutsch, Oct 29 2006

Row term sums = the Bell numbers starting with A000110(1): 1, 2, 5, 15, ...

The k-th term in the n-th row is the number of permutations of length n starting with k and avoiding the dashed pattern 23-1. Equivalently, the number of permutations of length n ending with k and avoiding 1-32. - Andrew Baxter, Jun 13 2011

From Gus Wiseman, Aug 11 2020: (Start)

Conjecture: Also the number of divisors d with distinct prime multiplicities of the superprimorial A006939(n) that are of the form d = m * 2^k where m is odd. For example, row n = 4 counts the following divisors:

  1     2     4    8     16

  3     18    12   24    48

  5     50    20   40    80

  7     54    28   56    112

  9     1350  108  72    144

  25          540  200   400

  27          756  360   432

  45               504   720

  63               600   1008

  75               1400  1200

  135                    2160

  175                    2800

  189                    3024

  675                    10800

  4725                   75600

Equivalently, T(n,k) is the number of length-n vectors 0 <= v_i <= i whose nonzero values are distinct and such that v_n = k.

Crossrefs:

A008278 is the version counted by omega A001221.

A336420 is the version counted by Omega A001222.

A006939 lists superprimorials or Chernoff numbers.

A008302 counts divisors of superprimorials by Omega.

A022915 counts permutations of prime indices of superprimorials.

A098859 counts partitions with distinct multiplicities.

A130091 lists numbers with distinct prime multiplicities.

A181796 counts divisors with distinct prime multiplicities.

Cf. A000005, A000142, A027423, A076954, A124010, A146291, A181818, A336417, A336419, A336421, A336499, A336942.

(End)

LINKS

Alois P. Heinz, Rows n = 0..150, flattened (first 51 rows from Chai Wah Wu)

Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv:1108.2642 [math.CO], 2011.

Anders Claesson, Generalized pattern avoidance, Europ. J. Combin., 22 7 (2001), 961-971.  See Proposition 3.

A. Bernini, M. Bouvel and L. Ferrari, Some statistics on permutations avoiding generalized patterns, PU.M.A. Vol. 18 (2007), No. 3-4, pp. 223-237 (see transposed array p. 227).

FORMULA

With offset 1, T(n,1) = T(n,n) = T(n+1,2) = B(n-1) = A000110(n-1) (the Bell numbers). T(n,k) = T(n,k-1) + T(n-1,k-1) for n >= k >= 3. T(n,n-1) = B(n-1) - B(n-2) = A005493(n-3) for n>=3 (B(q) are the Bell numbers A000110). T(n,k) = A011971(n-2,k-2) for n >= k >= 2. In other words, deleting first row and first column we obtain Aitken's array A011971 (also called Bell or Pierce triangle; offset in A011971 is 0). - Emeric Deutsch, Oct 29 2006

T(n,1) = B(n-1); T(n,2) = B(n-2) for n>=2; T(n,k) = Sum_{i=0..k-2} binomial(k-2,i)*B(n-2-i) for 3 <= k <= n, where B(q) are the Bell numbers (A000110). Generating polynomial of row n is P[n](t) = Q[n](t,1), where Q[n](t,s) = t^n*Q[n-1](1,s) + s*dQ[n-1](t,s)/ds + (s-1) Q[n-1](t,s); Q[1](t,s) = ts. - Emeric Deutsch, Oct 29 2006

EXAMPLE

Triangle starts:

   1;

   1,  1;

   2,  1,  2;

   5,  2,  3,  5;

  15,  5,  7, 10, 15;

  52, 15, 20, 27, 37, 52;

From Gus Wiseman, Aug 11 2020: (Start)

Row n = 3 counts the following set partitions (described in Emeric Deutsch's comment above):

  {1}{234}      {12}{34}    {123}{4}    {1234}

  {1}{2}{34}    {12}{3}{4}  {13}{24}    {124}{3}

  {1}{23}{4}                {13}{2}{4}  {134}{2}

  {1}{24}{3}                            {14}{23}

  {1}{2}{3}{4}                          {14}{2}{3}

(End)

MAPLE

with(combinat): T:=proc(n, k) if k=1 then bell(n-1) elif k=2 and n>=2 then bell(n-2) elif k<=n then add(binomial(k-2, i)*bell(n-2-i), i=0..k-2) else 0 fi end: matrix(8, 8, T): for n from 1 to 11 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form

Q[1]:=t*s: for n from 2 to 11 do Q[n]:=expand(t^n*subs(t=1, Q[n-1])+s*diff(Q[n-1], s)-Q[n-1]+s*Q[n-1]) od: for n from 1 to 11 do P[n]:=sort(subs(s=1, Q[n])) od: for n from 1 to 11 do seq(coeff(P[n], t, k), k=1..n) od; # yields sequence in triangular form - Emeric Deutsch, Oct 29 2006

A011971 := proc(n, k) option remember ; if k = 0 then if n=0 then 1; else A011971(n-1, n-1) ; fi ; else A011971(n, k-1)+A011971(n-1, k-1) ; fi ; end: A000110 := proc(n) option remember; if n<=1 then 1 ; else add( binomial(n-1, i)*A000110(n-1-i), i=0..n-1) ; fi ; end: A095149 := proc(n, k) option remember ; if k = 0 then A000110(n) ; else A011971(n-1, k-1) ; fi ; end: for n from 0 to 11 do for k from 0 to n do printf("%d, ", A095149(n, k)) ; od ; od ; # R. J. Mathar, Feb 05 2007

# alternative Maple program:

b:= proc(n, m, k) option remember; `if`(n=0, 1, add(

      b(n-1, max(j, m), max(k-1, -1)), j=`if`(k=0, m+1, 1..m+1)))

    end:

T:= (n, k)-> b(n, 0, n-k):

seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Dec 20 2018

MATHEMATICA

nmax = 10; t[n_, 1] = t[n_, n_] = BellB[n-1]; t[n_, 2] = BellB[n-2]; t[n_, k_] /; n >= k >= 3 := t[n, k] = t[n, k-1] + t[n-1, k-1]; Flatten[ Table[ t[n, k], {n, 1, nmax}, {k, 1, n}]] (* Jean-Fran├žois Alcover, Nov 15 2011, from formula with offset 1 *)

PROG

(Python)

# requires Python 3.2 or higher.

from itertools import accumulate

A095149_list, blist = [1, 1, 1], [1]

for _ in range(2*10**2):

....b = blist[-1]

....blist = list(accumulate([b]+blist))

....A095149_list += [blist[-1]]+ blist

# Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 20 2014

CROSSREFS

Cf. A000110, A005493, A008278, A011971, A188919, A271466.

T(2n,n) gives A020556.

Sequence in context: A144155 A109631 A337222 * A218579 A329198 A182436

Adjacent sequences:  A095146 A095147 A095148 * A095150 A095151 A095152

KEYWORD

nonn,tabl,easy,nice

AUTHOR

Gary W. Adamson, May 30 2004

EXTENSIONS

Corrected and extended by R. J. Mathar, Feb 05 2007

Entry revised by N. J. A. Sloane, Jun 01 2005, Jun 16 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 5 22:41 EDT 2021. Contains 346488 sequences. (Running on oeis4.)