Talk:Combinatorial number system

Values of combination numbers

I invented these algorithms by myself (about a year ago) and for a moment I thought that I've invented something new. Then I read this page. It was easier to invent the whole thing than to find this page. Maybe there should be a better link from the combination page to this one. Something like "generating combinations".

I think there is a problem on the page: the index in the examples don't actually equal the indexes which are calculated by McCaffrey's algorithm. For example, while i=54 works fine, i=56 does not, since that should be C(8,5)+C(3,4)+C(2,3)+C(1,2)+C(0,1)=60. Clearly there is some mismatch here. Mortoray (talk) 15:22, 4 November 2008 (UTC)

I stand corrected, looking closer it appears the nchoosek function in octaveforge returns incorrect results (returns 1 when it should return 0). Thus this page seems fine. Mortoray (talk) 15:34, 4 November 2008 (UTC)

Well, neither are truly wrong it appears, it's just that in C(n,k), C is only defined iff n >= k, so something like C(0,1) is undefined, but McCaffrey expects it to be 0. —Preceding unsigned comment added by Mortoray (talk • contribs) 15:44, 4 November 2008 (UTC)

In fact, C(n,k) is defined for all n,k ≥ 0 and, by the definition, = 0 when n < k. Thus, McCaffrey is correct. Zaslav (talk) 21:52, 19 December 2009 (UTC)

Combinadics, compositions, and partitions

This article appears to fall way short of encyclopedia standards. Here are two ways it's erroneous or misleading. 1. A "combinadic" is not an ordered partition of an integer. It is a (weak, since 0 is allowed) partition of an integer. I judge from reading the article that it is always (weakly) decreasing. That is not what a composition is. I will try to fix this. 2. "Combinadics" are not widely known. They appear to be a system for using weak partitions to index set combinations. It would be misleading to call them a synonym for (weak) partitions, since I think no one uses the name "combinadic" in that way. Zaslav (talk) 22:03, 19 December 2009 (UTC)

1. Fixed. Zaslav (talk) 02:33, 24 December 2009 (UTC)

van Leeuwen edits

I am disturbed by the recent edits to Combinadic by User:Marc van Leeuwen.

(1) You seem to have changed the meaning of "combinadic" entirely from what it was a few edits back. What is the justification? Can you cite sources?

(2) I cannot make sense of the new text. It needs a great deal more explanation. Example: Why is an apparently plural word "combinadics" said to be synonymous with a singular phrase "combinatorical number system"? Example: What does "when interpreted as k-combinations of the set N, run through all possibilities" mean? A k-combination is not a number. What set is N? (If you mean natural numbers, specify whether 0 is a "natural number". Authorities do not agree.)

I'm tempted to revert and ask for a better try next time. But I'm resisting the temptation! Zaslav (talk) 20:16, 21 March 2010 (UTC)

Indeed I changed quite a bit (and there is more work to do) because I found the old description quite incoherent. And to be honest, I could not deduce from it what "a combinadic" is precisely. The old introduction "combinadics are a simple system for indexing the k-element subsets of an n-element set by strictly decreasing sequences of k non-negative integers, all < n" does not give a clear clue. Worse, it seems to state a triviality, because just ordering those k-element subsets decreasingly one obtains such a decreasing sequence (maybe apply a shift of the values to get into the range $0\leq x<n$); while combinadics are not very deep mathematics, they are not as trivial as that. By the way my reference for combinatorial number system is Knuth TAOCP 4A, fasicle about generating all combinations; I'll put a proper reference in the article soon. Rapidly, what combinadics are about is a bijective correspondence between k-combinations (the mentioned subsets) and single numbers N; since one can view k-combinations as strings of symbols one can view this as a kind of numeral system for representing N (although the main utility is rather representing a k-combination by N than the other way around). There are several ways to view k-combinations as strings of values: the one most relevant here are as a decreasing sequence of k numbers less than n, the other is bit sequences of length n of which precisely k are set (their positions mark the elements of the k-combination). The number associated to a k-combination is its sequence number (starting at 0) in the lexicographically ordered list of such strings (either form). The formula now in the lede gives this correspondence; given a proof that it is indeed a bijection and procedures for converting from a number to k-combination (this is still to do, but easy), there is not much more to say about the subject. All this does not explain what "a combinadic" is; maybe the combinadic corresponding to N is the corresponding k-combination (so "combinadic" and k-combination would be more or less synoymous, maybe with a decreasing representation used for combinadics). But in any case, what an individual combinadic is is not very important (whence I avoid the term); it is the correspondence with the number N that is of interest. Marc van Leeuwen (talk) 07:34, 22 March 2010 (UTC)

Thanks for the explanation. I don't wish to defend the previous version!

If you put the early part of your remarks into the article, it will be a much better article. In my experience as a mathematician in combinatorics, the term "combinadic" has not once come to my attention except recently in this WP article. So, I'm skeptical that it's a truly accepted technical term. On the other hand, schemes for numbering combinations by natural numbers (which may include 0, according to your choice of definition) are certainly interesting. IMO, these would be most appropriate in an article on "combinations (combinatorics)". Schemes for representing natural numbers by combinations would seem to be without interest, unless there's some solid justification in the literature that I don't know about (very possible).

Perhaps the best thing is that you try to present in a simple way the idea that combinations can be enumerated by natural numbers, and how it's done. I'll try to help, but I won't be able to do anything for several weeks. I'm sorry! But thanks for your effort at straightening out this messy article. Zaslav (talk) 08:19, 23 March 2010 (UTC)

More info: See Microsoft on "combinadic". Their description is of a scheme for representing a natural number as a sum of binomial coefficients in a unique way. This is an important tool in various combinatorial problems. It has nothing to do with enumerating combinations by natural numbers. So, maybe there's a serious question about what the article is about. I wish I had time to look into it, but not for a few weeks. Zaslav (talk) 08:19, 23 March 2010 (UTC)

You are mistaken; the reference you give is in the article by McCaffrey cited in the Wikipedia article, and it is about the same "combinadic" correspondence, read in the direction of a map from integers to combinations. While the article is not entirely clear, it does not represent a natural number as a sum of binomial coefficients in a unique way (every natural number is a binomial coefficient, so that would make no sense), but rather as a particular kind of sum of k binomial coefficients: their lower indices are k,...,2,1, and their upper indices form a strictly decreasing sequence. That representation is unique (for fixed k), and it is precisely the statement in the lede of this article (only McCaffrey names the upper indices c_i with i increasing from 1 to k rather than decreasing from k to 1, as the lower indices do). So by traversing the initial ${\tbinom {n}{k}}$ natural numbers, the corresponding sequences of upper indices run through all k-combinations of {0,...,n−1}, written decreasingly, in lexicographic order. I agree with most other points you mention, as that the "combinadic" terminology is not very established and that an inclusion in the combination article would be in place; I prefer shaping up the current article first though. Marc van Leeuwen (talk) 17:47, 23 March 2010 (UTC)

'

Cleanup?

Do others find this article pretty unreadable? It is overly verbose, full of awkward wordings, and it seems a solid terminology is never decided upon as the article goes on. The section headings seem haphazard and somewhat vague. A concise mathematical description is lacking. --Loniousmonk (talk) 20:00, 15 March 2011 (UTC)

I have an hard time understanding the content of this page. --i⋅am⋅amz3 (talk) 23:13, 10 March 2019 (UTC)

I agree, it is unreadable. I think it wasn't written by a person with good English writing skills. It is indeed overly verbose, with an abundance of unnecessary subclauses that are difficult to follow. This sentence for example is definitely not English: "Choosing, for any n, {0, 1, ..., n − 1} as such a set, it can be arranged that the representation of a given k-combination C is independent of the value of n (although n must of course be sufficiently large); in other words considering C as a subset of a larger set by increasing n will not change the number that represents C." User:Patulus — Preceding undated comment added 19:28, 12 December 2020 (UTC)

Proof

The following paper discusses the proof for existence and uniqueness of combinatorial representation of a natural number.

http://arxiv.org/abs/1601.05794 — Preceding unsigned comment added by 111.68.102.26 (talk) 05:37, 4 February 2016 (UTC)

Excel section

The 'National Lottery example in Excel' section seems written like a blog post, rather than an encyclopedia article. This is probably because of the use of second-person point of view.

Additionally, the section should not focus on Excel. I have no idea what to replace it with, but maybe just change it to pure mathematical formulae.

Thanks, AddingInstruments (talk) 09:01, 8 September 2017 (UTC)

I agree with this ... though I wont stress over it either ... given that the chart essentially just reproduces a variant of Pascal's triangle, I wonder if it might be better to trim it down and just mention that there is a connection between Pascal's triangle, combinatorics, and the lottery drawing problems. —Soap— 00:43, 7 April 2020 (UTC)

The Excel example uses a reverse lexicographic numbering, while the explanation above uses increasing lexicographic order. So the formalas don't match up with the theoretical explanations above. My suggestion is to remove it, given this problem, as well as the fact that it has too much excel specific material. Arif Zaman (talk) 09:33, 22 August 2020 (UTC)

Pascal's square

Like the original poster, I created something almost exactly identical to this when I was younger, and I called it Pascal's square. (The only difference I see is that my version had the bottom value added to the top value, so my square had no zeros.) Given that the positive numbers on our chart are the same, row for row, as those of Pascal's triangle, should there be some mention of a connection? We have no mention of Pascal's triangle or any other derivative of his work in this article ... though ironically enough, I just found out that there is a different mathematician named Pascal who made a small contribution to the work behind this algorithm.

Our chart at Combinatorial_number_system#National_Lottery_example_in_Excel is identical to File:Pascal_triangle_simplex_numbers.svg except that ours doesnt have a zero column and it is flipped right-to-left. The chart we have now might be worth flipping horizontally if nothing else .... it's quite confusing to have one axis that goes in the normal order while the other goes from 6 to 1. —Soap— 00:41, 7 April 2020 (UTC)

Notation in the code example

Notation x'01^a10^b in the code example is not commonly known. Seeing it in the comment not only doesn't improve the understanding, but on opposite confuses the reader. Please, consider something that can be understood by a not initiated user. Patulus (talk) 19:56, 12 December 2020 (UTC)

Wrong combination place calculation

The section explaining the combination place in the ordering (at least in the form that is presented) is wrong. The text reads:

This number can be computed from C = { c_k, ..., c₂, c₁ } with c_k > ... > c₂ > c₁ as follows. The total number of k-combinations strictly less than C then is

${\binom {c_{1}}{1}}+{\binom {c_{2}}{2}}+\cdots +{\binom {c_{k}}{k}},$

and this is the index (starting from 0) of C in the ordered list of k-combinations.

Let us see an example (imagine a reader trying to follow the logic) for n=5 and k=3. We generate all the combinations in lexicographic order: [[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4], [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]. Now, we want to find out the place of the combination [1, 2, 3]. We have that c_k > ... > c₂ > c₁; therefore, c₃= 3,c₂,= 2 c₁= 1 and the position:

${\binom {1}{1}}+{\binom {2}{2}}+{\binom {3}{3}}=1+1+1=3$.

But the position is 6 (indexing from 0). Neoglez (talk) 15:29, 25 May 2021 (UTC)

Enumerative coding family

A few remarks: encoding of combinations is at heart of data compression (source coding, entropy encoding), and approach from this Article was considered many times, starting probably with 1972 "An algorithm for source coding": https://ieeexplore.ieee.org/document/1054832 , a few years later cited e.g. by Rissanen and Pasco introducing arithmetic coding: https://scholar.google.pl/scholar?cites=874220900720290002&as_sdt=2005&sciodt=0,5&hl=en - they are quite similar: symbols choose between large ranges of coding values.

And enumerative coding is a larger family of methods directly enumerating combinatorial objects, like combinations here, permutations e.g. using Lehmer code or points on sphere e.g. in pyramid vector quantization. Recurrence to calculate the number of objects can be transformed into enumerative coding.--Jarek Duda (talk) 04:29, 25 May 2021 (UTC)

Merge proposal

Support the October proposal to merge Macaulay representation of an integer to here, for reason of overlap and context. That other article is also very short. Klbrain (talk) 15:34, 8 November 2023 (UTC)

  Y Merger complete. Klbrain (talk) 20:18, 20 January 2024 (UTC)