1 2 Previous Next 29 Replies Latest reply on May 3, 2008 9:06 PM by 486393

    Pascal's triangle or binomial coefficients

    146850
      <font color="red">you know Pascal's triangle like below.</font>

      1
      11
      121
      1331
      14641
      ...
      ...

      my question is to find out a query giving nth sequence,
      that is to say,

      when n=1, that query yields
      1

      when n=2
      1
      1

      when n=3
      1
      2
      1

      when n=4
      1
      3
      3
      1

      ...
      ...

      (oh, but you have NOT to use any subqueries)


      for more SQL problems & questions, please visit
      http://cafe.daum.net/oraclesqltuning
        • 1. Re: Pascal's triangle or binomial coefficients
          Ghulam Mustafa Butt
          If you dont want subqueries, you can try in PL/SQL.

          Assuming your biggest length of the charector is 6, If the length is more you can copy and paste more ElsIf's:
          DECLARE
            lv_text   VARCHAR2(50);
            lv_len    NUMBER;
            CURSOR c1 IS
            SELECT text, length(text)
              FROM table;
          BEGIN
            OPEN c1;
            LOOP
              FETCH c1 INTO lv_text;
              EXIT WHEN c1%NOTFOUND;
              IF nvl(lv_length) = 1 THEN
                 dbms_output.put_line (lv_text);
              ELSIF
                 nvl(lv_length) = 2 THEN
                 FOR i IN 1..2 LOOP
                   dbms_output.put_line (substr(lv_text, i, i));
              ELSIF
                 nvl(lv_length) = 3 THEN
                 FOR i IN 1..3 LOOP
                   dbms_output.put_line (substr(lv_text, i, i));
              ELSIF
                 nvl(lv_length) = 4 THEN
                 FOR i IN 1..4 LOOP
                   dbms_output.put_line (substr(lv_text, i, i));
              ELSIF
                 nvl(lv_length) = 5 THEN
                 FOR i IN 1..5 LOOP
                   dbms_output.put_line (substr(lv_text, i, i));
              ELSIF
                 nvl(lv_length) = 6 THEN
                 FOR i IN 1..6 LOOP
                   dbms_output.put_line (substr(lv_text, i, i));
              END IF;
            END LOOP;
            CLOSE c1;
          END;
          /
          Not tested !

          HTH
          Ghulam
          • 2. Re: Pascal's triangle or binomial coefficients
            452095
            Are there restrictions on creating functions?
            • 3. Re: Pascal's triangle or binomial coefficients
              Ghulam Mustafa Butt
              FOR i IN 1..2 LOOP
              dbms_output.put_line (substr(lv_text, i, i));
              END LOOP;

              Sorry you have to add END LOOP; at the end of all For Loops.

              HTH
              Ghulam
              • 4. Re: Pascal's triangle or binomial coefficients
                146850
                sorry, but i want it in one SQL , not PL/SQL

                a variable n is given.
                no subqueries allowed.

                * this is not a sort of exam.
                • 5. Re: Pascal's triangle or binomial coefficients
                  146850
                  and the result is n rows....

                  when n=1
                  1 (one row)

                  when n=2
                  1
                  1 (two rows)

                  where n=3
                  1
                  2
                  1 (three rows)
                  ...
                  ...
                  • 6. Re: Pascal's triangle or binomial coefficients
                    APC
                    * this is not a sort of exam.
                    Do you have a solution and you're just testing us, or is this a kite flying exercise to see whether its possible?

                    I imagine it might be possible to do this with the Model clause but not having 10g to try it on I can't explore this theory at the moment.

                    Cheers, APC
                    • 7. Re: Pascal's triangle or binomial coefficients
                      94799
                      I recall the triangle starting at row 0 (perhaps that is a matter of choice)...
                      Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Production
                      With the Partitioning, OLAP and Data Mining options
                      
                      SQL> VARIABLE n NUMBER;
                      SQL> EXEC :n := 0;
                      
                      PL/SQL procedure successfully completed.
                      
                      SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
                        2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
                        3               OVER (ORDER BY LEVEL)) *
                        4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
                        5               OVER (ORDER BY LEVEL DESC))) n
                        6  FROM   dual
                        7  CONNECT BY LEVEL <= CEIL (:n + 1);
                      
                               N
                      ----------
                               1
                      
                      SQL> EXEC :n := 1;
                      
                      PL/SQL procedure successfully completed.
                      
                      SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
                        2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
                        3               OVER (ORDER BY LEVEL)) *
                        4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
                        5               OVER (ORDER BY LEVEL DESC))) n
                        6  FROM   dual
                        7  CONNECT BY LEVEL <= CEIL (:n + 1);
                      
                               N
                      ----------
                               1
                               1
                      
                      SQL> EXEC :n := 2;
                      
                      PL/SQL procedure successfully completed.
                      
                      SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
                        2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
                        3               OVER (ORDER BY LEVEL)) *
                        4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
                        5               OVER (ORDER BY LEVEL DESC))) n
                        6  FROM   dual
                        7  CONNECT BY LEVEL <= CEIL (:n + 1);
                      
                               N
                      ----------
                               1
                               2
                               1
                      
                      SQL> EXEC :n := 3;
                      
                      PL/SQL procedure successfully completed.
                      
                      SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
                        2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
                        3               OVER (ORDER BY LEVEL)) *
                        4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
                        5               OVER (ORDER BY LEVEL DESC))) n
                        6  FROM   dual
                        7  CONNECT BY LEVEL <= CEIL (:n + 1);
                      
                               N
                      ----------
                               1
                               3
                               3
                               1
                      
                      SQL> EXEC :n := 4;
                      
                      PL/SQL procedure successfully completed.
                      
                      SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
                        2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
                        3               OVER (ORDER BY LEVEL)) *
                        4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
                        5               OVER (ORDER BY LEVEL DESC))) n
                        6  FROM   dual
                        7  CONNECT BY LEVEL <= CEIL (:n + 1);
                      
                               N
                      ----------
                               1
                               4
                               6
                               4
                               1
                      
                      SQL> EXEC :n := 5;
                      
                      PL/SQL procedure successfully completed.
                      
                      SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
                        2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
                        3               OVER (ORDER BY LEVEL)) *
                        4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
                        5               OVER (ORDER BY LEVEL DESC))) n
                        6  FROM   dual
                        7  CONNECT BY LEVEL <= CEIL (:n + 1);
                      
                               N
                      ----------
                               1
                               5
                              10
                              10
                               5
                               1
                      
                      6 rows selected.
                      
                      SQL> EXEC :n := 6;
                      
                      PL/SQL procedure successfully completed.
                      
                      SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
                        2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
                        3               OVER (ORDER BY LEVEL)) *
                        4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
                        5               OVER (ORDER BY LEVEL DESC))) n
                        6  FROM   dual
                        7  CONNECT BY LEVEL <= CEIL (:n + 1);
                      
                               N
                      ----------
                               1
                               6
                              15
                              20
                              15
                               6
                               1
                      
                      7 rows selected.
                      
                      SQL> 
                      • 8. Re: Pascal's triangle or binomial coefficients
                        Laurent Schneider
                        by the way, how are you going to generate multiple rows in plain SQL?
                        def n=5
                        
                        with fac as (select rownum n,exp(sum(ln(rownum))over(order by rownum)) fac from all_objects where rownum<12)
                        select nvl(n.fac/r.fac/nr.fac,1)
                        from (select rownum-1 r from all_objects where rownum<=&n+1),
                            fac n, fac r, fac nr
                        where n.n (+)=&n and r.n (+)=r and nr.n(+)=(&n-r)
                        order by r
                        /
                        
                                                1
                                                5
                                               10
                                               10
                                                5
                                                1
                        Message was edited by:
                        Laurent Schneider
                        padders, your one is better ;-)
                        • 9. Re: Pascal's triangle or binomial coefficients
                          Laurent Schneider
                          note that I consider CONNECT BY without PRIOR to be disallowed... as specified in the doc, CONNECT BY must contain a PRIOR operator defining the parent-child relationship... but this is just a small note of mines and feel free to use CONNECT BY if you like / trust it ;-)

                          Message was edited by:
                          Laurent Schneider
                          still padders method with analytics rules, because it does not use subquery
                          • 10. Re: Pascal's triangle or binomial coefficients
                            452095
                            Should this work for all values of :n?

                            When :n = 10...

                            N
                            0
                            10
                            45
                            120
                            210
                            252
                            210
                            120
                            45
                            10
                            0
                            • 11. Re: Pascal's triangle or binomial coefficients
                              APC
                              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
                              • 12. Re: Pascal's triangle or binomial coefficients
                                49084
                                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
                                • 13. Re: Pascal's triangle or binomial coefficients
                                  452095
                                  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?
                                  • 14. Re: Pascal's triangle or binomial coefficients
                                    APC
                                    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
                                    1 2 Previous Next