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
255 views

There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?

There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?
3
votes
1answer
233 views

Number of isomorphism types of functions f:[n]->[n]

Consider the set $F_n: = [n]^{[n]}$ of all functions $f:[n] \rightarrow [n]$, $[n] = \lbrace 1,2,...,n\rbrace$. It is well known that $|F_n| = n^n$. Edit: Let two functions $f, g$ in $F_n$ be of the ...
3
votes
1answer
165 views

What else can the elliptic integral count?

I just read this document - Jacobi's Four Square Theorem. It shows how to count the number of representations of a number as the sum of four squares. I can follow the proof but currently it just ...
2
votes
1answer
123 views

Simple Sequence Problem: Walk in the park

In a 365 day year, Joe, Greg & Dean visit the park multiple times for a walk. Joe visits every 3rd day Greg visits every 5th day Dean visits every 7th day All three visit the park on the first ...
1
vote
1answer
256 views

Counting eleven digit integers with the sum of the digits 2

Suppose n is an integer, such that the sum of the digits of n is 2, and $10^{10} \lt n \lt 10^{11} $. The number of different values for n is: Let me try to list them : ...
1
vote
1answer
85 views

What is the sum of half of the choices (weighted)?

I'd like to get the exact value of the following sum: $\sum_{i=0}^{\lceil \frac{k}{2} \rceil}{({k \choose i}\cdot i)}$ I'd also like to know the asymptotic limits of the function.
0
votes
3answers
301 views

A homework problem involving counting using a special case of inclusion/exclusion

In a survey of political preference, 78% of those asked were in favor of at-least one of the proposals: I, II and III. 50% of those asked favored proposal I, 30% favored proposal II, and 20% favored ...
5
votes
3answers
2k views

Find All Cycles (Faces) In a Graph

I have a graph $G$ with a list of edges $E$, all the edges can form cycles, as shown below: All the coordinates for the vertex $V$ are known. Wat is the algorithm to find all the faces $F$? For ...
5
votes
2answers
79 views

Measure different volumes based on specified capacities

Given three containers of specified volume, how many different volumes can you measure ? For example, suppose we have cans with capacities 2, 3, 4 litres. We can ...
23
votes
4answers
2k views

Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$

Let $\varphi(n)$ be Euler's totient function, the number of positive integers less than or equal to $n$ and relatively prime to $n$. Challenge: Prove $$\sum_{k=1}^n \left\lfloor \frac{n}{k} ...
1
vote
1answer
217 views

Finding a Pattern Between Latin Squares

I manually arranged two complete latin squares from ordered pairs of 4 and 6 like so: ...
2
votes
3answers
261 views

$2^{k} \mid {2k \choose 0} \cdot 3^{0} + {2k \choose 2} \cdot 3^{1} + \cdots + {2k \choose 2i} \cdot 3^{i} + \cdots + {2k \choose 2k} \cdot 3^{k}$

I have to prove this question: $$2^{k} \,\left|\, {2k \choose 0} \cdot 3^{0} + {2k \choose 2} \cdot 3^{1} + \cdots + {2k \choose 2i} \cdot 3^{i} + \cdots + {2k \choose 2k} \cdot 3^{k}\right.$$ What ...
2
votes
2answers
170 views

Making sense of combinatorics-based marketing hyperboles

Diablo 3 has 97 billion possible skill/trait builds. Per class. LessPop_MoreFizz, emphasis is mine. I used base two logarithm to claim "97 billion" configurations only are roughly 37 binary ...
3
votes
1answer
227 views

Combinatorics and Rolling Dice Similarity?

Define a function $F(A, B, C)$ as the number of ways you can roll $B$ $C$-sided dice to sum up to $A$, counting different orderings (rolling a $2$, $2$, and $3$ with three dice is different from ...
4
votes
1answer
393 views

Balancing a Latin Square

I'm searching for an algorithm that forms a balanced (or quasi-complete) latin square, in which every element is a horizontal neighbor to every other element exactly twice, and a vertical neighbor to ...
3
votes
1answer
246 views

How to Form a Row-Complete Latin Square

This is one of the descriptions I've seen online: For any even $n$, say $n = 2m$, a row complete Latin square of order $n$ can be formed by writing down $$0, 1, 2m - 1, 2, 2m - 2, 3,\ldots, m + 1, ...
5
votes
2answers
202 views

Construction of an infinite set such that any two number from the set are relatively prime

This question is taken from a contest in India. Prove that we can construct an infinite set of positive integers of the form $2^{n}-3$, where $n \in \mathbb{N}$, such that any two numbers from the ...
4
votes
2answers
335 views

Number of integer solutions in [0,10]

How many solutions does the following equation have? $$k+l+m+n=30,$$ where $k,l,m,n\in\mathbb{Z},0\leq k,l,m,n\leq 10.$ Edit: this is an exercise in the inclusion-exclusion principle.
3
votes
3answers
599 views

Problems on combinatorics

The following comes from questions comes from a recent combinatorics paper I attended : 1.27 people are to travel by a bus which can carry 12 inside and 15 outside. In how many ways can the party be ...
1
vote
1answer
91 views

Does the term Row-Complete have any synonyms?

I'm wondering if there is other terminology that describes row-completeness, outside the context of a latin square, or if row-complete is actually a general term.
7
votes
2answers
539 views

Accuracy of approximation to inclusion-exclusion formula in prime sieve

This thing came up in a combinatorics course I am taking. Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of ...
3
votes
2answers
1k views

Dealing with grouping problem in combinatorics

I am trying to solve some problems based on this formula,but am facing some issues in determine whether or not consider ordering as important. For Example: In how many ways 15 different books can be ...
5
votes
3answers
754 views

Grouping items into groups

This is a chug-plug formula given in my book : 1.The number of ways in which mn different items can be divided equally int m groups, each containing n objects and the order of the groups is not ...
6
votes
2answers
539 views

Find an infinite set of positive integers such that the sum of any two distinct elements has an even number of distinct prime factors

I have attempting to solve this using the infinite ramsey theorem, with colouring based on whether the sum of two vertices has an even or odd number of distinct prime factors. This is leading to an ...
14
votes
2answers
525 views

What is the probability that every pair of students studies together at some point?

A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 ...
2
votes
1answer
177 views

How long to choose n out of 2n numbers?

Choose numbers from 1 to 2n uniformly at random. How many numbers must be chosen, on average, before at least n have been picked? This is similar to the coupon-collector problem, but looking for ...
4
votes
3answers
248 views

Probability Distribution with different probabilities

Suppose there are 9 events, that have a probability of 10%, 20%, 30%, ..., 90% of being a success. How would I find the probability of exactly n number of these events succeeding? For n = 1, I'm ...
3
votes
3answers
243 views

basic combinatorics question

Each person from a group of 3 people can choose his dish from a menu of 5 options. Knowing that each person eats only 1 dish what are the number of different orders the waiter can ask the chef?
3
votes
2answers
1k views

Probability of picking an item r times out of n attempts

Trying to remember my high school formulas, and coming up dry. Say I have two choices: A and B. P(A) = 0.25; P(B) = 0.75 There are no conditional probabilities or anything. Each choice is ...
3
votes
3answers
133 views

Number of classes of k-digit strings when digit order and identity doesn't matter

Suppose we look at $k$-digit strings with digits between $1$ and $n$. How many distinct classes of strings are there when digit identity and order doesn't matter? More formally, what is the number of ...
0
votes
1answer
222 views

Three question on Permutation and combination

1.How many number of three digit even numbers than can be formed out of the digits 0 to 9 ? The question seems confusing since there is no mention of whether repetition is allowed or not ?! since if ...
4
votes
3answers
737 views

Sum of squares of in-degrees vs out-degrees in a Tournament Graph

This problem was asked in a test, couple of years ago. Looked interesting! In a chess tournament, each pair of players plays exactly one game. No game is drawn. Suppose the $i^{th}$ player wins ...
3
votes
3answers
418 views

How to slice the cheese

I encounter a problem recently stated as below: How many pieces of cheese we can obtain from a single thick piece by making five straight slices?(we can't move the cheese when slicing)If we wanna ...
5
votes
1answer
601 views

sign reversing involution proof of a combinatorial identity

This from an exercise in Aigner's book where one has to evaluate $\sum_{k\ge 0} (-1)^k \binom{n}{k}^2$ using sign reversing involutions. When $n$ is odd, the problem is trivial : let $[n] = ...
3
votes
3answers
108 views

Finding n-th position of occurence of a number in an infinite series of numbers

Let's call $S$ the (infinite) string that is made by concatenating the consecutive positive integers (starting from 1) written down in base 10. Thus, $S = ...
4
votes
1answer
200 views

Limit involving the totient function and combination

Do you think the following limits are correct? $\displaystyle\lim_{d\to\infty}\frac{\sum\limits_{k=1}^{d} {\varphi(N) \choose k} {d-1 \choose k-1}}{\varphi(N)^d}=0$ ...
2
votes
2answers
2k views

How do I determine the possible number of combinations of two ordered sets?

I'm not quite sure what the mathematical term for what I'm asking is, so let me just describe what I'm trying to figure out. Let's say that I have two ordered sets of numbers {1, 2} and {3, 4}. I'm ...
2
votes
1answer
1k views

Different ways to write a number given digit constraints

Originally I was just going to ask the problem on my practice math contest, which is asking how many ways there are to write a nine-digit number containing each digit 1-9 so that the first digit is ...
5
votes
1answer
209 views

Partitioning sets such that the sum of 2 elements is Prime

Given an $n >0$ is it possible to partition the set $\mathcal{P} = \{1,2, \cdots, 2n\}$ into $n$ pairs $(a_{i},b_{i})$ such that $a_{i} + b_{i}$ is a prime?
6
votes
2answers
980 views

Calculate how many ways can you paint the corners of a Pentagon

I'm studiying for an exam I have on combinatorics next week and I'm stuck with the solution to this question: Imagine you have a pentagon and you want to color the corners of the pentagon so that no ...
1
vote
2answers
522 views

What number of positive integers satisfying the given inequality?

What number of positive integers satisfying the given inequality : C(n + 1,n – 2) – C(n + 1,n – 1) <= 100 What I did so far : ...
9
votes
1answer
635 views

Bell numbers and moments of the Poisson distribution

Using generating functions one can see that the $n^{th}$ Bell number, i.e., the number of all possible partitions of a set of $n$ elements, is equal to $E(X^n)$ where $X$ is a Poisson random variable ...
1
vote
2answers
443 views

Minimizing Gender Regularity in a linear arrangement of boys and girls

Let us consider that there are G girl students and B boy students in a class, we need to arrange them in a single row, but arrangement of students should be in order to minimize the gender ...
1
vote
3answers
602 views

Number of ways to stack N cubes

I'm trying to figure out how many ways are there to stack N cubes on top of each other. Once you get a particular stack of 4 cubes let's say, the order of the cubes doesn't matter, just which sides ...
6
votes
1answer
1k views

Good resources (book or otherwise) to learn/study basic Combinatorics

I'm currently studying basic Combinatorics for a college course and my professor is awful (and that is being generous). Therefore I'm looking for good resources to learn basic Combinatorics so that I ...
9
votes
2answers
395 views

Can this sum be simplified: $ \sum_{k=0}^{n-1} { n -1 \choose k } (-2)^{k} (2n - k)! $?

Can this expression be further simplified : $ \sum_{k=0}^{n-1} { n -1 \choose k } (-2)^{k} (2n - k)! $? This is the coefficient of $x^{2n}$ in the formal power series expansion of $(1-2x)^{n-1} \times ...
7
votes
2answers
605 views

Calculate combinations of characters

My first post here...not really a math expert, but certainly enjoy the challenge. I working writing a random string generator and would like to know how to calculate how many possible combinations ...
6
votes
2answers
314 views

A question related to the card game “Set”

The card game Set lead to the following question. Lets call a subset $A$ of $(\mathbb{Z}/3)^n$ dependent, if there is $\{x,y,z\}\subset A$ with $x+y+z=0$. (So unlike the case of linear dependence we ...
2
votes
1answer
212 views

When does an orthomorphism of the cyclic group exist?

I thought I would post (as a puzzle) one of my favourite results in combinatorics. I actually use variants of this result in research quite often. It's not impossible that someone will post an ...
1
vote
1answer
233 views

Moments on number of occurrences of substring

Let $S$ be a string of length $n$. Each character of $S$ has probability $p$ of being 'A' and probability $1-p=q$ of being 'B'. $R$ is the number of occurrences of the substring 'AB' in $S$. I'd like ...