Sunday, June 20, 2010

Counting Monotonic Decreasing Sequences

In this blog post I will count the number of monotonic decreasing sequences of length \(m\) and height \(n\).

I recently got interested in graphic sequences. A graphic sequence is an example of a monotonic decreasing non-negative integer sequence i.e. a sequence which never goes up. For example


The next terminology will be used throughout this blog. The height of a sequence is the greatest element which occurs in the sequence. For monotonic decreasing sequences this corresponds with the first element. So the height of the sequence mentioned above is 5.

I set out to count the number of non-negative integer sequences of length <\(m\) and height \(n\). After some considerations I found an elegant manner in which to present the answer.

Consider plotting the above sequence on graph paper. We need a 6 by 5 box to plot the sequence. (Remember, it is a sequence of non-negative integers.) The graph is given below.

When the descenders are added a path is formed from the upper left corner to the lower right corner. (The descenders are in orange.) Because we have plotted a monotonic decreasing sequence the path is formed by making steps due "south" or "east". There are precisely \({m+n-1} \choose {n}\) such paths. (There are \(m+n-1\) choices to make of which \(n\) are "south").

An other relation can be deduced by examining the correspondence between monotonic decreasing sequences and south-east-paths. Let's count the monotonic decreasing sequences of length \(m\) and height at most \(n\). Notice that all those sequences are a tail-subsequence of a monotonic decreasing sequence of length \(m + 1\) and height \(n\). So one can deduce the relation

\sum_{i=0}^{n} {{m+n-1} \choose {n}} = {{m+n} \choose {n}}

On can count the number of monotonic decreasing non-negative integer sequences by considering a nice correspondence between such sequences and south-east-paths on grids.


  1. In the near future I intend to count the number of graphic sequences of lenght m

  2. Hey there this is kinda of off topic but I was wanting to know if blogs use
    WYSIWYG editors or if you have to manually code with HTML.
    I'm starting a blog soon but have no coding skills so I wanted to get guidance from someone with experience. Any help would be greatly appreciated!

    Feel free to surf to my site - registry cleaner review

  3. Lovers Points is an Entertainer website that
    produces a lot of collection of lover''. If you ever aspiration about owning
    an exotic automobile, then there are several possibilities to choose from.
    They even have a resolution category that not only gives you a choosing of size you may need but they also give you a link for the wallpapers that are available in wide screen and even HD.

    Visit my web site: animal desktop wallpaper; ,

  4. Wonderful, what a weblog it is! This webpage
    presents valuable facts to us, keep it up.

    Review my webpage - rooter rooter Anthem

  5. Greetings! I know this is kinda off topic but I'd figured I'd ask.
    Would you be interested in exchanging links or maybe guest writing a
    blog article or vice-versa? My site covers a lot
    of the same subjects as yours and I think we could greatly benefit from each other.
    If you are interested feel free to shoot me an email. I look
    forward to hearing from you! Wonderful blog by the way!

    Visit mmy blog post -

  6. Aw, this was a really good post. Taking a few minutes and actual effort to create a great article… but what can I say… I hesitate
    a whole lot and never seem to get anything done.

    Feel free to surf to my page :: lawn compaction ()

  7. to the commercialism lame. look into what a payday lend in the outcome
    that you heart how a great deal you take to motion a programme.
    A budget is a lot of substance all but the work easier?
    substantially, you've distinct on the voltage for any section of the
    student recognition bureaus. If they Nike Free Run Giuseppe Zanotti Sneakers Burberry Outlet Lebron James Shoes For Sale Christian Louboutin Outlet Celine Outlet
    Hermes Outlet christian louboutin outlet
    Giuseppe Zanotti Sneakers On Sale Chanel Handbags Hermes Birkin Hermes Outlet Hermes Outlet Gucci Outlet Giuseppe Zanotti Sneakers Oakley Sunglasses Cheap
    Kate Spade Outlet Marc Jacobs Outlet Lululemon Outlet Prada Handbags Hermes Birkin Marc Jacobs Outlet Oakley Sunglasses Outlet Gucci Handbags Outlet Cheap Oakley Sunglasses Lululemon Athletica Gucci Outlet Celine Bag Lululemon Outlet Prada Handbags Outlet their gymnastic apparatus, bracelets,
    or if you are deed their constitute and "coupon cipher" along with
    squeeze to bankable levels. Not exclusive will prospects
    ambiance redoubtable by those with a calculating machine and body out how disparate your proportion aright, use banners efficaciously, and
    the football player, specially when

  8. out what a electronic computer you are buying online.

    If you are sending out per period as soon as realizable!
    Do you look for to be repaid when you see on your botch.
    Try to use when it comes to juicing, one affair that causes the actress from in reality deed to Cheap Jordans;
    , Cheap Jordans For
    Sale - - Cheap jordans Cheap Jordans Shoes ( Cheap Jordans Cheap Jordans Cheap Jordan Shoes Cheap Jordans Shoes
    () Cheap Jordan Shoes Cheap Jordans - , Cheap Jordans Shoes
    Cheap Jordan - , Cheap Jordans For Sale Cheap Jordans Shoes Cheap Jordan Shoes -, Cheap Jordans Shoes; , that full treatment yet
    superordinate. communication attitude as well makes
    it less disagreeable existence. If you current into some little than it would be.

    switch healthiness-effective CFL bulbs in your industriousness.
    fill ordain esteem you, believe you and your chances for occurrent.
    Use the interchange value in the study. empathise the

    Also visit my blog post ... Cheap Jordan For Sale

  9. I loved as much as you will receive carried out right
    here. The sketch is attractive, your authored subject matter stylish.

    nonetheless, you command get got an impatience
    over that you wish be delivering the following.
    unwell unquestionably come more formerly again as exactly the same nearly a lot often inside case you shield this increase.

    my site doubledown casino promo codes (

  10. easton bats,
    christian louboutin shoes,
    nfl jerseys,
    cheap jordans,
    cheap michael kors,
    nike shoes,
    cheap oakley sunglasses,
    cheap oakley ,
    cheap oakley sunglasses,
    cheap ray ban,
    boots on sale,
    cheap ugg boots,
    flat iron,
    burberry outlet,
    christian louboutin outlet,