Forum Stats

  • 3,750,551 Users
  • 2,250,192 Discussions
  • 7,867,005 Comments

Discussions

Categories

Pascal's triangle or binomial coefficients

2

Comments

  • APC
    APC Member Posts: 11,316 Bronze Crown
    edited Nov 14, 2005 11:20AM
    Should this work for all values of :n?
    interesting. Padders version works for me (allowing for the fatc that the CONNECT BY trick doesn't work propperly in 9.2)... 
    SQL> EXEC :n := 10

    
PL/SQL procedure successfully completed.

    
SQL> SELECT * FROM
    
  2  (
    
  3   SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
    
  4              EXP (SUM (LN (GREATEST (LEVEL - 1, 1)))
    
  5                 OVER (ORDER BY LEVEL)) *
    
  6              EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1)))
    
  7                 OVER (ORDER BY LEVEL DESC))) n
    
  8    FROM   dual
    
  9    CONNECT BY LEVEL <= CEIL (:n + 1))
    
 10  /
    
         N
    
----------
    
         1
    
        10
    
        45
    
       120
    
       210
    
       252
    
       210
    
       120
    
        45
    
        10
    
         1

    
11 rows selected.

    
SQL>
    Cheers, APC
    · Share on TwitterShare on Facebook
  • 49084
    49084 Member Posts: 340
    interesting. Padders version works for me (allowing for the fatc that the CONNECT BY trick doesn't work propperly in 9.2)...
    There's an easy workaround for that (I'm sure you're well aware, but just for those who don't know yet):
    SELECT EXP (SUM (LN (L)) OVER ()) / (:n + 1) / (
      EXP (SUM (LN (GREATEST (L - 1, 1))) 
                 OVER (ORDER BY L)) *
             EXP (SUM (LN (GREATEST (:n - (L - 1), 1))) 
               OVER (ORDER BY L DESC))) n
  FROM   ( SELECT LEVEL L 
             FROM DUAL 
          CONNECT BY LEVEL <= CEIL (:n + 1)
         )
/
    It works perfect on my 9.2 box.

    MHE
    · Share on TwitterShare on Facebook
  • 452095
    452095 Member Posts: 332
    I'm using 9.2.0.6.0... so there's a flaw with connect by in this version thats affecting the output of the query sometimes? When I use values 0 through 9 and 11 it appears to return the correct values, but for whatever reason it doesn't work when :n equals 10.

    Can anyone explain how the query works, not what each function does individually, but why when you put them together they return pascal's triangle?
    · Share on TwitterShare on Facebook
  • APC
    APC Member Posts: 11,316 Bronze Crown
    I'm using 9.2.0.6.0
    Me likewise
    Can anyone explain how the query works
    basically the query is calculating the value of each element in the row; it implements the nCr method using analytic functions to generate factorials.

    Cheers, APC
    · Share on TwitterShare on Facebook
  • 452095
    452095 Member Posts: 332
    Thanks for your reply APC. I understand the formula (I accept that it works although I have no idea why it works). But how do the functions that padders uses perform the same functionality that a factorial (!) does?
    · Share on TwitterShare on Facebook
  • 245482
    245482 Member Posts: 1,254
    The following are all the same. This is a (sort of) common trick for implementing factorial.
    select exp(sum(ln(level)))
  from dual
connect by level <= N

exp(ln(1) + ln(2) + ... ln(N))

exp(ln(1)) * exp(ln(2)) * ... exp(ln(N))

1*2*...N

N!
    · Share on TwitterShare on Facebook
  • Vadim Tropashko-Oracle
    Vadim Tropashko-Oracle Posts: 1,237 Employee
    select x,y,count(1) from (
    select x,y,sys_connect_by_path('['||x||','||y||'>',' ') path
    from (
    select level x from dual
    connect by level < 5
    ), (
    select level y from dual
    connect by level < 5
    ) connect by prior x+1 = x and prior y = y
    or prior x = x and prior y+1 = y
    start with x = 1 and y = 1
    ) group by x,y;

    Nice exercise to include into a book.
    · Share on TwitterShare on Facebook
  • 452095
    452095 Member Posts: 332
    Thanks Scott, I must have missed that day in my SQL class.
    · Share on TwitterShare on Facebook
  • 146850
    146850 Member Posts: 116
    edited May 28, 2007 7:44AM
    good job, padders.

    and my solution is
    SELECT       EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) OVER ())
           / EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) OVER (ORDER BY LEVEL))
           / EXP (SUM (LN (GREATEST (:n - LEVEL, 1))) OVER (ORDER BY LEVEL DESC)
                 ) bin_coef
      FROM DUAL
CONNECT BY LEVEL <= :n
    Query Your Dream & Future at
    http://www.soqool.com
    · Share on TwitterShare on Facebook
  • 94799
    94799 Member Posts: 2,208
    Just a couple of variations on the theme using a table function as a row source and a user-defined product aggregate (source available on request).
    Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Production
With the Partitioning, OLAP and Data Mining options

SQL> VARIABLE r NUMBER;
SQL> EXEC :r := 5;

PL/SQL procedure successfully completed.

SQL> SELECT product (GREATEST (n, 1)) OVER () / 
  2         product (GREATEST (n, 1)) OVER (ORDER BY n) /
  3         product (GREATEST (:r - n, 1)) OVER (ORDER BY n DESC) n
  4  FROM   TABLE (many (0, :r));

         N
----------
         1
         5
        10
        10
         5
         1

6 rows selected.

SQL> SELECT SUBSTR (SYS_CONNECT_BY_PATH (
  2            r, ','), 2) pascals_triangle
  3  FROM  (SELECT a.n an, b.n bn, 
  4                product (GREATEST (b.n, 1)) OVER (
  5                   PARTITION BY a.n) /
  6                product (GREATEST (b.n, 1)) OVER (
  7                   PARTITION BY a.n ORDER BY b.n) /
  8                product (GREATEST (a.n - b.n, 1)) OVER (
  9                   PARTITION BY a.n ORDER BY b.n DESC) r
 10         FROM   TABLE (many (0, :r)) a, 
 11                TABLE (many (0, a.n)) b) 
 12  WHERE  CONNECT_BY_ISLEAF = 1
 13  START WITH bn = 0
 14  CONNECT BY an = PRIOR an AND bn = PRIOR bn + 1;

PASCALS_TRIANGLE
--------------------------------------------------------------------------------
1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
1,5,10,10,5,1

6 rows selected.

SQL>
    · Share on TwitterShare on Facebook
This discussion has been closed.