This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

3
votes
1answer
316 views

Does solving a Rubik's cube imply alignment?

Today, I got my hands on a Rubik's cube with text on it. It looks like this: Now, I would love to know whether solving the right cube will also always correctly align the text on the cube or ...
6
votes
2answers
102 views

Is this asymptotic equation correct?

Is this equation correct? $$ \frac {1 + \Theta(\frac 1 {2n})} {(1 + \Theta(1/n))^2} = 1 + O(1 / n) $$ I need this equation to prove that $$ \binom {2n} n = \frac {2 ^ {2n}} {\sqrt {\pi n}} (1 + ...
2
votes
1answer
368 views

How to get this upper bound of combinations?

How to prove: $$ \binom{n}{k} \leq \frac{n^n}{k^k \times {(n - k) ^ {(n - k)}}} $$ The question also gives a hint : "Use induction on k ≤ n/2 to prove inequality". I tried but the got stuck at this ...
3
votes
3answers
126 views

equivalent expressions don't look equivalent

Consider the proportion $\displaystyle\frac{a}b=\frac{c}d=\frac{e}f=\frac{g}h$. It is equivalent to $\displaystyle\frac{f}e=\frac{b}a=\frac{h}g=\frac{d}c$ in the sense that the fractions ...
2
votes
2answers
117 views

On understanding a combinatorial argument:

I am facing some problems in understanding this combinatorial argument: Number of ways of putting $19$ identical balls in $16$ non-overlapping triangles such that no triangle is empty and there ...
4
votes
1answer
352 views

Subset of natural numbers such that any natural number except 1 can be expressed as sum of two elements

Let $X$ be the set of natural numbers $k_i$, $k_i \geq 1$, with the property that at least one of the equations $p_i = $6$ k_i \pm 1$ gives the $i$-th prime number (disregarding $2$ and $3$), and ...
0
votes
1answer
131 views

Combinatorics for multi-index set, how many elements does $\{ X^j : |j|=3, j_l \neq 0\}$ have?

Let $j \in \mathbb{R}^n$ be a multi-index with $|j|=3$. Fix an index $l$, then there are how many $X^j$ with $j_l=0$?, more precise: I want to know what $ \text{#} \{ X^j : |j|=3, j_l \neq 0\}$ is. ...
1
vote
1answer
208 views

Count number of paths through a matrix

Please note: this is not homework. This is related to a previous question I have asked, Calculate number of sequences in frequency matrix. Please refer to this image: (also the image presented on ...
3
votes
2answers
113 views

Double sequence convergence

Let be $$S(m,k)$$ number of partitions of a $k$ element set into $m$ nonempty parts investigating with generating functions I get this very interesting equation$$\sum_{k=0}^ {\infty}\sum_{m=0}^ ...
2
votes
1answer
111 views

Analytical Reasoning Question III

I tried to solve the number problem below and would like to get input on the final solution I came up with. Thanks in advance! (a) If n is a multiple of 7, how many numbers there that are multiples ...
0
votes
3answers
739 views

Analytical Reasoning Question II

I have yet another analytical question that got me A five-digit number is formed using digits 1, 3, 5, 7 and 9 without repeating any one of them. What is the sum of all such possible numbers? ...
0
votes
1answer
441 views

How to list all combinations when they are grouped?

In a hypothetical game, 2 numbers of nine wins. If I want to increase my chances, I would use combinations of 3. There is 84 combinations of 9 numbers (1 to 9) 3 to 3, but only 12 combinations of 3 ...
2
votes
3answers
813 views

Analytical Reasoning Question I

I would appreciate it if someone could please help me understand what is being asked here and how to approach questions like the one below. At the college entrance exam, a candidate is admitted ...
1
vote
1answer
266 views

A “fast” way to compute number of pairs of positive integers $(a,b)$ with lcm $N$

I am looking for a fast/efficient method to compute the number of pairs of $(a,b)$ so that its LCM is a given integer, say $N$. For the problem I have in hand, $N=2^2 \times 503$ but I am very ...
6
votes
1answer
259 views

What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?

The question sounds simple: find the roots of the characteristic equation, take the one with the largest absolute value, and find its coefficient. Repeated roots do not substantially complicate ...
3
votes
4answers
278 views

Simple Counting Question

How many solutions to the equation $x_1 + x_2 + x_3 = 11$ for positive integers, are there?? Please explain your answer as much as possible.
2
votes
1answer
679 views

Question regarding dividing group of people into ordered pair

This is a very basic counting problem, however I couldn't recall my memory to understand the answer correctly. From "A First Course in Probability by Sheldon Ross", Example A football team ...
4
votes
3answers
615 views

The number of subsets of a set of cardinality $n$

Please help with this question. Show that for a finite set $A$ of cardinality $n$, the cardinality of P(A) is $2^n$, where $P(A)$ is the power set of $A$. Thank you in advance for any help that is ...
4
votes
2answers
279 views

A Combinatorial proof for the identity $\sum_i \sum_j \min(i,j) = \sum_k k^2$

I have to prove this (a combinatorally proof, counting a set in two different ways): $$\sum_{i=1}^n\sum_{j=1}^n\mathrm{min}(i,j)=\sum_{k=1}^nk^2 .$$ This is what I have done: take the set ...
4
votes
1answer
64 views

Value of $k$ satisfying this condition

In a pile you have 100 stones. A partition of the pile in $k$ piles is good if: 1) the small piles have different numbers of stones; 2) for any partition of one of the small piles in 2 smaller ...
0
votes
1answer
148 views

Is my argument wrong? (A combinatorial exercise)

How many ways are there to arrange $m$ distinct flags on a row of $r$ flagpoles? The order of the flags on the flagpoles (from top to bottom) matters. My argument is: I have $mr$ points and I have to ...
1
vote
1answer
82 views

A “fast” approach to compute $\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$ [duplicate]

Possible Duplicate: How to find a closed formula for the given summation I am looking for a fast/best approach to compute $$\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$$ For ...
2
votes
1answer
244 views

Optimizing a string to have the shortest possible unique substrings

I would like to construct a length $N$ string over a $k$-letter alphabet, $S$, such that any substring of $P$ sequential characters in $S$ is unique for as small a value of $P$ as possible. To ...
1
vote
3answers
455 views

Finding characteristic equation of problem and solve recurrence relation

I have a homework assignment to find the characteristic equation of the set which a(n) = the number of sequences of length n which can be build from ${1,2,3...8}$ but you can't have two even numbers ...
3
votes
1answer
176 views

Counting fractions with $n$ digits in the numerator and denominator

Playing around with fractions, I eventually had to consider the following question: Is there a formula for counting how many proper fractions in lowest terms with $n$ base-$b$ digits in both the ...
3
votes
3answers
79 views

How can I compute this expression?

I have to understand what is this expression $\sum_{A\subset[n]}\prod_{i\in A}1/i$ where $[n]=\{1,\ldots,n\}$. And then prove it. I was using a very complicated method to understand what this ...
8
votes
5answers
245 views

finding the coefficient of $x^{14}$ in the expression: $\frac{5x^2-x^4}{(1-x)^3}$

I have a homework question which requires me to find the coefficient of $x^{14}$ in the expression: $\dfrac{5x^2-x^4}{(1-x)^3}$ I have not figured out a way to do this (I believe this is because my ...
19
votes
3answers
439 views

Getting the name of combinatorial problems

I'll often find myself with some combinatorial problem that's obviously been studied before. For example, "Find the smallest set(s) of positive integers such that every integer from 1 to n is the sum ...
4
votes
1answer
334 views

Restricted Integer Compositions

Let $c_{k}(N;[a,b])$ denote the number of compositions of $N$ into $k$ parts, where each part is restricted to the interval $[a,b]$, i.e., $N = \sum_{i = 1}^{k} s_{i}$ with $a \leq s_{i} \leq b$. The ...
2
votes
1answer
112 views

Coming up with a generating function

I have a homework assignment which is to write a Generating Function of the following problem: "There are $n$ identical boxes , there are $3$ different rooms in which they can be put. Each room can ...
15
votes
3answers
623 views

Finding when $(a-n)(b-n)|(ab-n)$

Given $n$ and $k$, find the number of pairs of integers $(a, b)$ which satisfy the conditions $n < a < k, n < b < k$ and $(ab-n)$ is divisible by $(a-n)(b-n)$. Given: $0 ≤ n ≤ 100000, \ n ...
3
votes
3answers
667 views

What are the symmetries of the tetrahedron?

Suppose I like combinatorics, and want to count how many ways to paint the faces of a tetrahedron using a pallet of $x$ colors. I don't want to over count cases where I could just rotate one painted ...
4
votes
4answers
191 views

Combinatorics | Building a wall

Let $n$ be a positive integer. A child builds a wall along a line with $n$ identical cubes. He lays the first cube on the line and at each subsequent step, he lays the next cube either on the ground ...
11
votes
3answers
201 views

Calculating $\sum_{0\le k\le n/2} \binom{n-k}{k}$

I would like to evaluate: $$\sum_{0\le k\le n/2}\binom{n-k}{k}$$ Any idea?
3
votes
2answers
488 views

Distributing a cake cut with four vertical slices among three people

A round cake was cut with a knife $4$ times vertically in such a way that it is cut to maximum number of pieces.Find the number of ways of distributing these cakes among three people such that ...
3
votes
3answers
683 views

Truth table, clarification of $2^n$ row rule?

My question is about truth tables and specifically why there is $2^n$ rows for $n$ inputs in a truth table? I understand that there's a finite amount of states a variable can be in, here it's 2 - ...
2
votes
1answer
154 views

Bound for multi-index sum

I have difficulties in evaluating the multi-index notation in the following context: Let $x \in R^n$ and let $i$ be a multi-index, $i=(i_1, \dots, i_n)$. Now I want to know the bound of the sum ...
3
votes
2answers
164 views

What is a simple expression for $\sum\limits^m_{j=1}(m-j)2^{j-1}$ and a combinatorial interpretation of it?

$$f(m)=\sum^m_{j=1}(m-j)2^{j-1}$$ I've to understand what is a simple form of $f$ by computing some value of it, but I can't see a simple form of it, can anyone help me? I have also to give a ...
5
votes
2answers
145 views

How to count possible separations of N items into K clusters?

How many ways are to separate N same items into K clusters. For N=10, K=4 are there 9 ways: (7,1,1,1), (6,2,1,1), ...
5
votes
1answer
234 views

What's the difference between Ramsey theory and Extremal graph theory?

Wikipedia teaches us that problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?" It ...
0
votes
1answer
129 views

In how many ways can some or all of the $5$ distinct coins be put into $8$ pockets?

In how many ways can some or all of the $5$ distinct coins be put into $8$ pockets? Could this be modeled as the problem of "In how many ways N distinct items be put into r distint groups ...
3
votes
1answer
66 views

what's the most probable min interval in 100 balls in a circle?

I have $n=100$ balls, in which $h=3$ are red, 97 are blue. I randomly place the balls in a circle, then check the minimum interval of red balls (e.g., if 2 red balls are consecutive, then their ...
19
votes
2answers
727 views

Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem

In the recent question "What's the probability that a sequence of coin flips never has twice as many heads as tails?" I argue in my answer that the number of ways $S(n)$ to obtain twice as many heads ...
1
vote
1answer
60 views

How many ways does the following tasks can be accomplished?

There are seven tasks $(1,2,3,4,5,6,7)$ which have to done by seven people $(A,B,C,D,E,F$ and $G)$.Each person can do only one task. Task $1$ must be done by $A,B$ or $C$.Task $4$ and $5$ ...
7
votes
6answers
233 views

Finding the minimum number of students

There are $p$ committees in a class (where $p \ge 5$), each consisting of $q$ members (where $q \ge 6$).No two committees are allowed to have more than 1 student in common. What is the minimum and ...
2
votes
0answers
107 views

What does it mean if a sequence is indexed beyond its bounds?

I'm looking at a paper (On Base and Turyn Sequences by C. Koukouvinos, S. Kounias and K. Sotirakoglou) that describes an algorithm for finding specific sequences. Part of the algorithm involves ...
1
vote
1answer
198 views

Simple combinatorics - tiling shapes with dominoes

I remember a long time ago during my university entrance interview I was asked a deceptively simple combinatorics (or what I believe to be combinatorics) question. Imagine you had a rectangle of size ...
1
vote
1answer
419 views

Lucas' Theorem and Pascal's Triangle

I have a general question about Lucas' Theorem. Lucas' Theorem says the following: Theorem (Lucas' Theorem) Let $p$ be a prime number. Write $n$ and $k$ in base $p$: $n = a_0 + a_{1}+a_{2}p^{2} + ...
5
votes
2answers
510 views

Number of positive integral solutions for $ab + cd = a + b + c + d $ with $1 \le a \le b \le c \le d$

How many positive integral solutions exist for: $ab + cd = a + b + c + d $,where $1 \le a \le b \le c \le d$ ? I need some ideas for how to approach this problem.
5
votes
2answers
3k views

Finding the n-th lexicographic permutation of a string

I have an ordered set of symbols S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. I want to find the 1,000,000-th permutation in lexicographic order of S. It is a programming puzzle, but I wanted to figure out a ...