notebook.community

Edit and run

Massimo Nocentini

September 27, 2016: refactoring and sync


Abstract
In this notebook we study the *Pascal triangle*, locking at it recursively: using it's $A$-sequence, we perform a series of unfolding using the main recurrence relation, where subscripts dependends on *two* dimensions, as rewriting rule. This is a natural enhancement to the case of recurrences where subscripts have *one* dimension only, as the *Fibonacci* sequence; on the other hand, Pascal array is a deeply studied and well know triangle, yet simple, toy we can play with. 





In [1]:



    


%run "../src/start_session.py"
%run "../src/recurrences.py"



    











In [1]:



    


import oeis

Pascal array $\mathcal{P}$

This notebook studies the Riordan array $\mathcal{P}$, aka the Pascal triangle, defined according to the following definition:

$$\mathcal{P}=\left(\frac{1}{1-t}, \frac{t}{1-t}\right)$$

with $A$-sequence $A(t)=1+t$ and $Z$-sequence $Z(t)=1$.





In [3]:



    


d = IndexedBase('d')
n, k = symbols('n k')

pascal_recurrence_spec = recurrence_spec(recurrence_eq=Eq(d[n+1, k+1], d[n, k] + d[n, k+1]), 
                                         recurrence_symbol=d, 
                                         variables=[n,k])



    











In [4]:



    


pascal_recurrence_spec



    


















    
Out[4]:






$\left(\Theta, \Gamma\right)_{n,k}^{d}$ where: 
  • $\Theta = \left\{ d_{n + 1,k + 1} = d_{n,k} + d_{n,k + 1} \right\}$
  • $\Gamma = \left\{\begin{array}{c}\end{array}\right\}$

















In [5]:



    


unfolded = pascal_recurrence_spec.unfold(depth=2)



    











In [6]:



    


unfolded



    


















    
Out[6]:






$\left(\Theta, \Gamma\right)_{n,k}^{d}$ where: 
  • $\Theta = \left\{ d_{n + 1,k + 1} = 3 d_{n - 2,k} + d_{n - 2,k - 2} + 3 d_{n - 2,k - 1} + d_{n - 2,k + 1} \right\}$
  • $\Gamma = \left\{\begin{array}{c}d_{n - 1,k - 1} = d_{n - 2,k - 2} + d_{n - 2,k - 1}\\d_{n - 1,k} = d_{n - 2,k} + d_{n - 2,k - 1}\\d_{n - 1,k + 1} = d_{n - 2,k} + d_{n - 2,k + 1}\\d_{n,k} = d_{n - 1,k} + d_{n - 1,k - 1}\\d_{n,k + 1} = d_{n - 1,k} + d_{n - 1,k + 1}\end{array}\right\}$

















In [7]:



    


instantiated = unfolded.instantiate(strategy=raw(substitutions={n:9,k:4}))
instantiated



    


















    
Out[7]:






$\left(\Theta, \Gamma\right)_{n,k}^{d}$ where: 
  • $\Theta = \left\{ d_{10,5} = d_{7,2} + 3 d_{7,3} + 3 d_{7,4} + d_{7,5} \right\}$
  • $\Gamma = \left\{\begin{array}{c}d_{8,3} = d_{7,2} + d_{7,3}\\d_{8,4} = d_{7,3} + d_{7,4}\\d_{8,5} = d_{7,4} + d_{7,5}\\d_{9,4} = d_{8,3} + d_{8,4}\\d_{9,5} = d_{8,4} + d_{8,5}\end{array}\right\}$

















In [8]:



    


known_binomials = {d[n,k]:binomial(n,k) for n in [7] for k in range(2,6)}

checked = instantiated.instantiate(strategy=raw(substitutions=known_binomials))
checked



    


















    
Out[8]:






$\left(\Theta, \Gamma\right)_{n,k}^{d}$ where: 
  • $\Theta = \left\{ d_{10,5} = 252 \right\}$
  • $\Gamma = \left\{\begin{array}{c}d_{8,3} = 56\\d_{8,4} = 70\\d_{8,5} = 56\\d_{9,4} = d_{8,3} + d_{8,4}\\d_{9,5} = d_{8,4} + d_{8,5}\end{array}\right\}$

















In [9]:



    


checked.subsume()



    


















    
Out[9]:






$\left(\Theta, \Gamma\right)_{n,k}^{d}$ where: 
  • $\Theta = \left\{ d_{10,5} = 252 \right\}$
  • $\Gamma = \left\{\begin{array}{c}d_{8,3} = 56\\d_{8,4} = 70\\d_{8,5} = 56\\d_{9,4} = 126\\d_{9,5} = 126\end{array}\right\}$

















In [10]:



    


based_recurrence_spec = unfolded.instantiate(strategy=based(arity=doubly_indexed()))
based_recurrence_spec



    


















    
Out[10]:






$\left(\Theta, \Gamma\right)_{n,k}^{d}$ where: 
  • $\Theta = \left\{ d_{6,3} = d_{3,0} + 3 d_{3,1} + 3 d_{3,2} + d_{3,3} \right\}$
  • $\Gamma = \left\{\begin{array}{c}d_{4,1} = d_{3,0} + d_{3,1}\\d_{4,2} = d_{3,1} + d_{3,2}\\d_{4,3} = d_{3,2} + d_{3,3}\\d_{5,2} = d_{4,1} + d_{4,2}\\d_{5,3} = d_{4,2} + d_{4,3}\end{array}\right\}$

















In [11]:



    


based_recurrence_spec.subsume()



    


















    
Out[11]:






$\left(\Theta, \Gamma\right)_{n,k}^{d}$ where: 
  • $\Theta = \left\{ d_{6,3} = d_{3,0} + 3 d_{3,1} + 3 d_{3,2} + d_{3,3} \right\}$
  • $\Gamma = \left\{\begin{array}{c}d_{4,1} = d_{3,0} + d_{3,1}\\d_{4,2} = d_{3,1} + d_{3,2}\\d_{4,3} = d_{3,2} + d_{3,3}\\d_{5,2} = d_{3,0} + 2 d_{3,1} + d_{3,2}\\d_{5,3} = d_{3,1} + 2 d_{3,2} + d_{3,3}\\d_{8,3} = 56\\d_{8,4} = 70\\d_{8,5} = 56\\d_{9,4} = 126\\d_{9,5} = 126\end{array}\right\}$

















In [12]:



    


ipython_latex_description(rec_spec=pascal_recurrence_spec, depths=range(6), arity=doubly_indexed())



    


















    
Out[12]:







\begin{array}{c}d_{2,1} = d_{1,0} + d_{1,1}\\
d_{4,2} = d_{2,0} + 2 d_{2,1} + d_{2,2}\\
d_{6,3} = d_{3,0} + 3 d_{3,1} + 3 d_{3,2} + d_{3,3}\\
d_{8,4} = d_{4,0} + 4 d_{4,1} + 6 d_{4,2} + 4 d_{4,3} + d_{4,4}\\
d_{10,5} = d_{5,0} + 5 d_{5,1} + 10 d_{5,2} + 10 d_{5,3} + 5 d_{5,4} + d_{5,5}\\
d_{12,6} = d_{6,0} + 6 d_{6,1} + 15 d_{6,2} + 20 d_{6,3} + 15 d_{6,4} + 6 d_{6,5} + d_{6,6}\\\end{array}

OEIS content about $\mathcal{P}$





In [2]:



    


s = oeis.oeis_search(id=7318)



    


















    






*
















In [3]:



    


s()



    


















    
Out[3]:







Results for query: https://oeis.org/search?q=id%3AA007318&start=0&fmt=json
A007318: Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0 <= k <= n.


by N. J. A. Sloane and Mira Bernstein, Apr 28 1994


Keywords: nonn,tabl,nice,easy,core,look,hear


Data:

$$
\begin{array}{c|ccccccccccc}
n, k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
0 & 1 &  &  &  &  &  &  &  &  & \\1 & 1 & 1 &  &  &  &  &  &  &  & \\2 & 1 & 2 & 1 &  &  &  &  &  &  & \\3 & 1 & 3 & 3 & 1 &  &  &  &  &  & \\4 & 1 & 4 & 6 & 4 & 1 &  &  &  &  & \\5 & 1 & 5 & 10 & 10 & 5 & 1 &  &  &  & \\6 & 1 & 6 & 15 & 20 & 15 & 6 & 1 &  &  & \\7 & 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 &  & \\8 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & \\9 & 1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1
\end{array}
$$
Comments:


    

  • C(n,k) = number of k-element subsets of an n-element set.
    • 

  • Row n gives coefficients in expansion of (1+x)^n.
    • 

  • Binomial(n+k-1,n-1) is the number of ways of placing k indistinguishable balls into n boxes (the "bars and stars" argument - see Feller).
    • 

  • Binomial(n-1,k-1) is the number of compositions (ordered partitions) of n with k summands.
    • 

  • Binomial(n+k-1,k-1) is the number of weak compositions (ordered weak partitions) of n into exactly k summands.- Juergen Will, Jan 23 2016
    • 

  • Binomial(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0) and (1,1). - Joerg Arndt, Jul 01 2011
    • 

  • If thought of as an infinite lower triangular matrix, inverse begins:
    • 

  • +1
    • 

  • -1 +1
    • 

  • +1 -2 +1
    • 

  • -1 +3 -3 +1
    • 

  • +1 -4 +6 -4 +1
    • 

  • All 2^n palindromic binomial coefficients starting after the A006516(n)-th entry are odd. - Lekraj Beedassy, May 20 2003
    • 

  • Binomial(n+k-1,n-1) is the number of standard tableaux of shape (n,1^k). - Emeric Deutsch, May 13 2004
    • 

  • Can be viewed as an array, read by antidiagonals, where the entries in the first row and column are all 1's and A(i,j) = A(i-1,j) + A(i,j-1) for all other entries. The determinant of each of its n X n subarrays starting at (0,0) is 1. - Gerald McGarvey, Aug 17 2004
    • 

  • Also the lower triangular readout of the exponential of a matrix whose entry {j+1,j} equals j+1 (and all other entries are zero). - Joseph Biberstine (jrbibers(AT)indiana.edu), May 26 2006
    • 

  • Binomial(n-3,k-1) counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 132 and k descents. Binomial(n-3,k-1) also counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 213 and k descents. - David Hoek (david.hok(AT)telia.com), Feb 28 2007
    • 

  • Inverse of A130595 (as an infinite lower triangular matrix). - Philippe Deléham, Aug 21 2007
    • 

  • Consider integer lists LL of lists L of the form LL = [m#L] = [m#[k#2]] (where '#' means 'times') like LL(m=3,k=3) = [[2,2,2],[2,2,2],[2,2,2]]. The number of the integer list partitions of LL(m,k) is equal to binomial(m+k,k) if multiple partitions like [[1,1],[2],[2]] and [[2],[2],[1,1]] and [[2],[1,1],[2]] are counted only once. For the example, we find 456/3! = 20 = binomial(6,3). - Thomas Wieder, Oct 03 2007
    • 

  • The infinitesimal generator for Pascal's triangle and its inverse is A132440. - Tom Copeland, Nov 15 2007
    • 

  • Row n>=2 gives the number of k-digit (k>0) base n numbers with strictly decreasing digits; e.g., row 10 for A009995. Similarly, row n-1>=2 gives the number of k-digit (k>1) base n numbers with strictly increasing digits; see A009993 and compare A118629. - Rick L. Shepherd, Nov 25 2007
    • 

  • From Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008: 
      

    • Binomial(n+k-1, k) is the number of ways a sequence of length k can be partitioned into n subsequences (see the Naish link).
      • 

    • Binomial(n+k-1, k) is also the number of n- (or fewer) digit numbers written in radix at least k whose digits sum to k. For example, in decimal, there are binomial(3+3-1,3)=10 3-digit numbers whose digits sum to 3 (see A052217) and also binomial(4+2-1,2)=10 4-digit numbers whose digits sum to 2 (see A052216). This relationship can be used to generate the numbers of sequences A052216 to A052224 (and further sequences using radix greater than 10). 
      • 

    

    • 

  • From Milan Janjic, May 07 2008: 
      

    • Denote by sigma_k(x_1,x_2,...,x_n) the elementary symmetric polynomials. Then:
      • 

    • Binomial(2n+1,2k+1) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2(i*Pi/(2n+1)), (i=1,2,...,n).
      • 

    • Binomial(2n,2k+1) = 2nsigma_{n-1-k}(x_1,x2,...,x{n-1}), where x_i = tan^2(iPi/(2n)), (i=1,2,...,n-1).
      • 

    • Binomial(2n,2k) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n)), (i=1,2,...,n).
      • 

    • Binomial(2n+1,2k) = (2n+1)sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n+2)), (i=1,2,...,n). 
      • 

    

    • 

  • Given matrices R and S with R(n,k) = binomial(n,k)r(n-k) and S(n,k) = binomial(n,k)s(n-k), then RS = T where T(n,k) = binomial(n,k)[r(.)+s(.)]^(n-k), umbrally. And, the e.g.f.s for the row polynomials of R, S and T are, respectively, exp(xt)exp[r(.)x], exp(xt)exp[s(.)x] and exp(xt)exp[r(.)x]exp[s(.)x] = exp{[t+r(.)+s(.)]x}. The row polynomials are essentially Appell polynomials. See A132382 for an example. - Tom Copeland, Aug 21 2008
    • 

  • As the rectangle R(m,n) = binomial(m+n-2,m-1), the weight array W (defined generally at A114112) of R is essentially R itself, in the sense that if row 1 and column 1 of W=A144225 are deleted, the remaining array is R. - Clark Kimberling, Sep 15 2008
    • 

  • If A007318 = M as an infinite lower triangular matrix, M^n gives A130595, A023531, A007318, A038207, A027465, A038231, A038243, A038255, A027466, A038279, A038291, A038303, A038315, A038327, A133371, A147716, A027467 for n=-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 11 2008
    • 

  • The coefficients of the polynomials with e.g.f. exp(xt)(cosh(t)+sinh(t)). - Peter Luschny, Jul 09 2009
    • 

  • The triangle or chess sums, see A180662 for their definitions, link Pascal's triangle with twenty different sequences, see the crossrefs. All sums come in pairs due to the symmetrical nature of this triangle. The knight sums Kn14 - Kn110 have been added. It is remarkable that all knight sums are related to the Fibonacci numbers, i.e., A000045, but none of the others. - Johannes W. Meijer, Sep 22 2010
    • 

  • Binomial(n,k) is also the number of ways to distribute n+1 balls into k+1 urns so that each urn gets at least one ball. See example in the example section below. - Dennis P. Walsh, Jan 29 2011
    • 

  • Binomial(n,k) is the number of increasing functions from {1,...,k} to {1,...,n} since there are binomial(n,k) ways to choose the k distinct, ordered elements of the range from the codomain {1,...,n}. See example in the example section below. - Dennis P. Walsh, Apr 07 2011
    • 

  • Central binomial coefficients: T(2*n,n) = A000984(n), T(n, floor(n/2)) = A001405(n). - Reinhard Zumkeller, Nov 09 2011
    • 

  • Binomial(n,k) is the number of subsets of {1,...,n+1} with k+1 as median element. To see this, note that Sum_{j=0..min(k,n-k)}binomial(k,j)*binomial(n-k,j) = binomial(n,k). See example in Example section below. - Dennis P. Walsh, Dec 15 2011
    • 

  • This is the coordinator triangle for the lattice Z^n, see Conway-Sloane, 1997. - N. J. A. Sloane, Jan 17 2012
    • 

  • One of three infinite families of integral factorial ratio sequences of height 1 (see Bober, Theorem 1.2). The other two are A046521 and A068555. For real r >= 0, C_r(n,k) := floor(rn)!/(floor(rk)!floor(r(n-k))!) is integral. See A211226 for the case r = 1/2. - Peter Bala, Apr 10 2012
    • 

  • For n > 0: T(n,k) = A029600(n,k) - A029635(n,k), 0 <= k <= n. - Reinhard Zumkeller, Apr 16 2012
    • 

  • Define a finite triangle T(m,k) with n rows such that T(m,0) = 1 is the left column, T(m,m) = binomial(n-1,m) is the right column, and the other entries are T(m,k) = T(m-1,k-1) + T(m-1,k) as in Pascal's triangle. The sum of all entries in T (there are A000217(n) elements) is 3^(n-1). - J. M. Bergot, Oct 01 2012
    • 

  • The lower triangular Pascal matrix serves as a representation of the operator exp(RLR) in a basis composed of a sequence of polynomials p_n(x) characterized by ladder operators defined by R pn(x) = p(n+1)(x) and L pn(x) = n p(n-1)(x). See A132440, A218272, A218234, A097805, and A038207. The transposed and padded Pascal matrices can be associated to the special linear group SL2. - Tom Copeland, Oct 25 2012
    • 

  • See A193242. - Alexander R. Povolotsky, Feb 05 2013
    • 

  • A permutation p_1...p_n of the set {1,...,n} has a descent at position i if pi > p(i+1). Let S(n) denote the subset of permutations p_1...pn of {1,...,n} such that p(i+1) - p_i <= 1 for i = 1,...,n-1. Then binomial(n,k) counts the number of permutations in S(n+1) with k descents. Alternatively, binomial(n,k) counts the number of permutations in S(n+1) with k+1 increasing runs. - Peter Bala, Mar 24 2013
    • 

  • Sum{n=>0} binomial(n,k)/n!) = e/k!, where e = exp(1), while allowing n < k where binomial(n,k) = 0. Also Sum{n>=0} binomial(n+k-1,k)/n! = e  A000262(k)/k!, and for k>=1 equals e  A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
    • 

  • The square n X n submatrix (first n rows and n columns) of the Pascal matrix P(x) defined in the formulas below when multiplying on the left the Vandermonde matrix V(x_1,...,x_n) (with ones in the first row) translates the matrix to V(x_1+x,...,x_n+x) while leaving the determinant invariant. - Tom Copeland, May 19 2014
    • 

  • For k>=2, n>=k,  k/((k/(k-1) - Sum_{n=k..m} 1/binomial(n,k))) = m!/((m-k+1)!*(k-2)!). Note: k/(k-1) is the infinite sum. See A000217, A000292, A000332 for examples. - Richard R. Forberg, Aug 12 2014
    • 

  • Let G(2n) be the subgroup of the symmetric group S(2n) defined by G(2n) = {p in S(2n) | p(i) = i (mod n) for i = 1,2,...,2n}. G(2n) has order 2^n. Binomial(n,k) counts the number of permutations in G(2n) having n + k cycles. Cf. A130534 and A246117. - Peter Bala, Aug 15 2014
    • 

  • T(n,k) = A245334(n,k) / A137948(n,k), 0 <= k <= n. - Reinhard Zumkeller, Aug 31 2014
    • 

  • C(n,k) = the number of Dyck paths of semilength n, with k "u"'s in odd numbered positions and k returns to the x axis. Example: {U = u in odd position and  = return to x axis} binomial(4,1)=1 (Uudududd); binomial(4,2)=3 [(UududdUd), (UdUududd), (UuddUudd)]; binomial(4,3)=3 [(Ud_UdUudd), (Uudd_UdUd), (Ud_UuddUd)]; binomial(4,4)=1 (Ud_Ud_UdUd). - Roger Ford, Nov 05 2014
    • 

  • From Daniel Forgues, Mar 12 2015: 
      

    • The binomial coefficients binomial(n,k) give the number of individuals of the k-th generation after n population doublings. For each doubling of population, each individual's clone has its generation index incremented by 1, and thus goes to the next row. Just tally up each row from 0 to 2^n - 1 to get the binomial coefficients.
      • 

    • 0   1       3               7                              15
      • 

    • 0: O | . | .   . | .   .   .   . | .   .   .   .   .   .   .   . |
      • 

    • 1:   | O | O   . | O   .   .   . | O   .   .   .   .   .   .   . |
      • 

    • 2:   |   |     O |     O   O   . |     O   O   .   O   .   .   . |
      • 

    • 3:   |   |       |             O |             O       O   O   . |
      • 

    • 4:   |   |       |               |                             O |
      • 

    • This is a fractal process: to get the pattern from 0 to 2^n - 1, append a shifted down (by one row) copy of the pattern from 0 to 2^(n-1) - 1 to the right of the pattern from 0 to 2^(n-1) - 1. (Inspired by the "binomial heap" data structure.)
      • 

    • Sequence of generation indices: 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n) (see A000120):
      • 

    • {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ...}
      • 

    • Binary expansion of 0 to 15:
      • 

    • 0   1   10   11  100  101  110  111 1000 1001 1010 1011 1100 1101 1111
      • 

    

    • 

  • A258993(n,k) = T(n+k,n-k), n > 0. - Reinhard Zumkeller, Jun 22 2015
    • 

  • T(n,k) is the number of set partitions w of [n+1] that avoid 1/2/3 with rb(w)=k. The same holds for ls(w)=k, where avoidance is in the sense of Klazar and ls,rb defined by Wachs and White.
    • 



Formulae:


    

  • a(n, k) = C(n,k) = binomial(n, k).
    • 

  • C(n, k) = C(n-1, k) + C(n-1, k-1).
    • 

  • a(n+1, m) = a(n, m) + a(n, m-1), a(n, -1) := 0, a(n, m) := 0, n<m; a(0, 0)=1.
    • 

  • C(n, k)=n!/(k!(n-k)!) if 0<=k<=n, otherwise 0.
    • 

  • G.f.: 1/(1-y-xy) = Sum(C(n, k)x^k*y^n, n, k>=0)
    • 

  • G.f.: 1/(1-x-y) = Sum(C(n+k, k)x^ky^n, n, k>=0).
    • 

  • G.f. for row n: (1+x)^n = Sum_{k=0..n} C(n, k)x^k.
    • 

  • G.f. for column n: x^n/(1-x)^n.
    • 

  • E.g.f.: A(x, y) = exp(x+x*y).
    • 

  • E.g.f. for column n: x^n*exp(x)/n!.
    • 

  • In general the m-th power of A007318 is given by: T(0, 0) = 1, T(n, k) = T(n-1, k-1) + m*T(n-1, k), where n is the row-index and k is the column; also T(n, k) = m^(n-k) C(n, k).
    • 

  • Triangle T(n, k) read by rows; given by A000007 DELTA A000007, where DELTA is Deléham's operator defined in A084938.
    • 

  • Let P(n+1) = the number of integer partitions of (n+1); let p(i) = the number of parts of the i-th partition of (n+1); let d(i) = the number of different parts of the i-th partition of (n+1); let m(i, j) = multiplicity of the j-th part of the i-th partition of (n+1). Define the operator Sum{i=1..P(n+1), p(i)=k+1} as the sum running from i=1 to i=P(n+1) but taking only partitions with p(i)=(k+1) parts into account. Define the operator Product{j=1..d(i)} = product running from j=1 to j=d(i). Then C(n, k) = Sum{p(i)=(k+1), i=1..P(n+1)} p(i)! / [Product{j=1..d(i)} m(i, j)!]. E.g., C(5, 3) = 10 because n=6 has the following partitions with m=3 parts: (114), (123), (222). For their multiplicities one has: (114): 3!/(2!1!) = 3; (123): 3!/(1!1!*1!) = 6; (222): 3!/3! = 1. The sum is 3 + 6 + 1 = 10 = C(5, 3). - Thomas Wieder, Jun 03 2005
    • 

  • C(n, k) = Sum_{j=0..k} = (-1)^jC(n+1+j, k-j)A000108(j). - Philippe Deléham, Oct 10 2005
    • 

  • G.f.: 1 + x(1 + x) + x^3(1 + x)^2 + x^6(1 + x)^3 + ... . - Michael Somos, Sep 16 2006
    • 

  • Sum{k=0..floor(n/2)} x^(n-k)*T(n-k,k) = A000007(n), A000045(n+1), A002605(n), A030195(n+1), A057087(n), A057088(n), A057089(n), A057090(n), A057091(n), A057092(n), A057093(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, respectively. Sum{k=0..floor(n/2)} (-1)^kx^(n-k)T(n-k,k) = A000007(n), A010892(n), A009545(n+1), A057083(n), A001787(n+1), A030191(n), A030192(n), A030240(n), A057084(n), A057085(n+1), A057086(n), A084329(n+1) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, respectively. - Philippe Deléham, Sep 16 2006
    • 

  • C(n,k) <= A062758(n) for n > 1. - Reinhard Zumkeller, Mar 04 2008
    • 

  • C(t+p-1, t) = Sum{i=0..t} C(i+p-2, i) = Sum{i=1..p} C(i+t-2, t-1). A binomial number is the sum of its left parent and all its right ancestors, which equals the sum of its right parent and all its left ancestors. - Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008
    • 

  • From Paul D. Hanna, Mar 24 2011: 
      

    • Let A(x) = Sum_{n>=0} x^(n(n+1)/2)*(1+x)^n be the g.f. of the flattened triangle:
      • 

    • A(x) = 1 + (x + x^2) + (x^3 + 2x^4 + x^5) + (x^6 + 3x^7 + 3*x^8 + x^9) +...
      • 

    • then A(x) equals the series Sum{n>=0} (1+x)^nx^nProduct{k=1..n} (1-(1+x)x^(2k-1))/(1-(1+x)x^(2k));
      • 

    • also, A(x) equals the continued fraction 1/(1- x(1+x)/(1+ x(1-x)(1+x)/(1- x^3(1+x)/(1+ x^2(1-x^2)(1+x)/(1- x^5(1+x)/(1+ x^3(1-x^3)(1+x)/(1- x^7(1+x)/(1+ x^4(1-x^4)(1+x)/(1- ...))))))))).
      • 

    • These formulas are due to (1) a q-series identity and (2) a partial elliptic theta function expression. 
      • 

    

    • 

  • Row n of the triangle is the result of applying the ConvOffs transform to the first n terms of the natural numbers (1, 2, 3, ..., n). See A001263 or A214281 for a definition of this transformation. - Gary W. Adamson, Jul 12 2012
    • 

  • From L. Edson Jeffery, Aug 02 2012: 
      

    • Row n (n >= 0) of the triangle is given by the n-th antidiagonal of the infinite matrix P^n, where P = (p_{i,j}), i,j >= 0, is the production matrix
      • 

    • 0, 1,
      • 

    • 1, 0, 1,
      • 

    • 0, 1, 0, 1,
      • 

    • 0, 0, 1, 0, 1,
      • 

    • 0, 0, 0, 1, 0, 1,
      • 

    • 0, 0, 0, 0, 1, 0, 1,
      • 

    • 0, 0, 0, 0, 0, 1, 0, 1,
      • 

    • 0, 0, 0, 0, 0, 0, 1, 0, 1,
      • 

    • ... 
      • 

    

    • 

  • Row n of the triangle is also given by the n+1 coefficients of the polynomial P_n(x) defined by the recurrence P_0(x) = 1, P_1(x) = x + 1, Pn(x) = x*P{n-1}(x) + P_{n-2}(x), n > 1. - L. Edson Jeffery, Aug 12 2013
    • 

  • For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 18 2013
    • 

  • For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 04 2013
    • 

  • (1+x)^n = Sum{k=0..n} (-1)^(n-k)binomial(n,k)Sum{i=0..k} k^(n-i)binomial(k,i)x^(n-i)/(n-i)!. - Vladimir Kruchinin, Oct 21 2013
    • 

  • E.g.f.: A(x,y) = exp(x+xy) = 1 + (x+yx)/( E(0)-(x+yx)), where E(k) = 1 + (x+yx)/(1 + (k+1)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 08 2013
    • 

  • E.g.f.:  E(0) -1, where E(k) = 2 + x(1+y)/(2k+1 - x*(1+y)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
    • 

  • G.f.: 1 + x(1+x)(1+x^2(1+x)/(W(0)-x^2-x^3)), where W(k) = 1 + (1+x)x^(k+2) - (1+x)*x^(k+3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
    • 

  • Sum{n>=0} C(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where C(n,k) = 0. Also Sum{n>=0} C(n+k-1,k)/n! = e  A000262(k)/k!, and for k>=1 equals e  A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
    • 

  • Sum_{n>=k} 1/C(n,k) = k/(k-1) for k>=1. - Richard R. Forberg, Feb 10 2014
    • 

  • From Tom Copeland, Apr 17 and 26 2014: 
      

    • Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result by A007318(x) = P(x). Then with :xD:^n = x^n*(d/dx)^n and B(n,x), the Bell polynomials (A008277),
      • 

    • A) P(x)= exp(xdP) = exp[x(e^M-I)] = exp[M*B(.,x)] = (I+dP)^B(.,x)
      • 

    • with dP = A132440, M = A238385-I, and I = identity matrix, and
      • 

    • B) P(:xD:) = exp(dP:xD:) = exp[(e^M-I):xD:] = exp[MB(.,:xD:)] = exp[MxD] = (I+dP)^(xD) with action P(:xD:)g(x) = exp(dP:xD:)g(x) = g[(I+dP)*x] (cf. also A238363).
      • 

    • C) P(x)^y = P(yx). P(2x) = A038207(x) = exp[MB(.,2x)], the face vectors of the n-dim hypercubes.
      • 

    • D) P(x) = [St2]exp(xM)[St1] = [St2](I+dP)^x*[St1]
      • 

    • E) = [St1]^(-1)(I+dP)^x[St1] = [St2](I+dP)^x[St2]^(-1)
      • 

    • where [St1]=padded A008275 just as [St2]=A048993=padded A008277 and exp(x*M) = (I+dP)^x = sum(k=0,..,infinity, C(x,k) dP^k). 
      • 

    

    • 

  • From Peter Bala, Dec 21 2014: 
      

    • Recurrence equation: T(n,k) = T(n-1,k)*(n + k)/(n - k) - T(n-1,k-1) for n >= 2 and 1 <= k < n, with boundary conditions T(n,0) = T(n,n) = 1. Note, changing the minus sign in the recurrence to a plus sign gives a recurrence for the square of the binomial coefficients - see A008459.
      • 

    • There is a relation between the e.g.f.'s of the rows and the diagonals of the triangle, namely, exp(x)  e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)(1 + 3x + 3x^2/2! + x^3/3!) = 1 + 4x + 10x^2/2! + 20x^3/3! + 35x^4/4! + .... This property holds more generally for the Riordan arrays of the form ( f(x), x/(1 - x) ), where f(x) is an o.g.f. of the form 1 + f_1x + f_2x^2 + .... See, for example, A055248 and A106516.
      • 

    • Let P denote the present triangle. For k = 0,1,2,... define P(k) to be the lower unit triangular block array
      • 

    • /I_k 0\
      • 

    • \ 0  P/ having the k X k identity matrix I_k as the upper left block; in particular, P(0) = P. The infinite product P(0)P(1)P(2)..., which is clearly well-defined, is equal to the triangle of Stirling numbers of the second kind A008277. The infinite product in the reverse order, that is, ...P(2)P(1)P(0), is equal to the triangle of Stirling cycle numbers A130534. 
      • 

    

    • 

  • C(a+b,c) = Sum{k=0..a} C(a,k)*C(b,b-c+k). This is a generalization of equation 1 from section 4.2.5 of the Prudnikov et al. reference, for a=b=c=n: C(2n,n) = Sum{k=0..n} C(n,k)^2. See Links section for animation of new formula. - Hermann Stamm-Wilbrandt, Aug 26 2015
    • 

  • The row polynomials of the Pascal matrix P(n,x) = (1+x)^n are related to the Bernoulli polynomials Br(n,x) and their umbral compositional inverses Bv(n,x) by the umbral relation P(n,x) = (-Br(.,-Bv(.,x)))^n = (-1)^n Br(n,-Bv(.,x)), which translates into the matrix relation P = M  Br  M * Bv, where P is the Pascal matrix, M is the diagonal matrix diag(1,-1,1,-1,...), Br is the matrix for the coefficients of the Bernoulli polynomials, and Bv that for the umbral inverse polynomials defined umbrally by Br(n,Bv(.,x)) = x^n = Bv(n,Br(.,x)). Note M = M^(-1). - Tom Copeland, Sep 05 2015
    • 



Cross references:



Links:



References:


    

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
    • 

  • P Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
    • 

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 63ff.
    • 

  • B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
    • 

  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 306.
    • 

  • P. Curtz, Intégration numérique des systèmes différentiels à conditions initiales, Centre de Calcul Scientifique de l'Armement, Arcueil, 1969.
    • 

  • W. Feller, An Introduction to Probability Theory and Its Application, Vol. 1, 2nd ed. New York: Wiley, p. 36, 1968.
    • 

  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 155.
    • 

  • D. Hök, Parvisa mönster i permutationer [Swedish], 2007.
    • 

  • D. E. Knuth, The Art of Computer Programming, Vol. 1, 2nd ed., p. 52.
    • 

  • S. K. Lando, Lecture on Generating Functions, Amer. Math. Soc., Providence, R.I., 2003, pp. 60-61.
    • 

  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
    • 

  • A. P. Prudnikov, Yu. A. Brychkov and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
    • 

  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 6.
    • 

  • J. Riordan, Combinatorial Identities, Wiley, 1968, p. 2.
    • 

  • R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996, p. 143.
    • 

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

  • D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 115-8, Penguin Books 1987.
    •


This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Content source: massimo-nocentini/recurrences-unfolding

Similar notebooks:

notebook.community | gallery | about