For 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)

2
votes
1answer
46 views

Probability of sums with 6 dice [duplicate]

You roll six independent fair dice. What is the probability that their sum is divisible by 6? I don't really know where to start. Does the ordering of the dice matter? (1,2,2,2,2,3) vs (3,2,2,2,2,1)....
3
votes
2answers
191 views

Probability Combinatorial related; choosing couples

7 girs and 3 boys are divided to couples, order within a couple and between couples is not important, what is the probability that one of the couples contains 2 boys? i had this exercise in my ...
4
votes
1answer
43 views

Different combinations of 7 books distributed to 7 critics, twice

I'm having an exam on Discrete Mathematics II in my university, and I came up to this problem. A publishing firm has 7 books ready to publish. Each of them needs to be reviewed by 2 different ...
3
votes
0answers
92 views
+50

Maximal unit lengths in 3D with $n$ points.

Given $n$ points in 3D space (V), what is the maximal number of unit distance lengths (E) between those points? Here are a few possibilities. Some of them are chromatic spindles. ...
3
votes
4answers
48 views

Probability of a dice launched three times

A dice is launched three times. What is the probability to obtain three even numbers ? I've solved this problem calculating the number of total results: $$u=D'_{6,3}=6^3$$ and the number of ...
-1
votes
2answers
47 views

What is the probability of random walking ant to be at a position after some finite steps on an infinite grid? [on hold]

Is it even calculable? What if the grid is infinitely dimensional? Lets say that it is a simple random walk, and probability to move to any neighboring position is equal, but other types are also ...
1
vote
4answers
493 views

Ice Cream Combinatorics

An ice cream store offers 14 different flavors. Customers can purchase a single scoop or a double scoop ice cream. The double scoop portion DOES NOT allow two scoops of the same flavor. How many ...
1
vote
0answers
25 views

Area under staircase walk

If I create a random lattice path from $(0,0)$ to $(n,k)$, taking only north or east steps $(1,0)$ or $(0,1)$, with equal probability, the so called staircase walk, what are the moments of the area ...
2
votes
1answer
48 views

What is the Probability came from the same machine

Machine A produced 65 of the day’s output of Product X and machine B produced the other 55. If three products are selected with replacement at random from the day’s output, the probability that, My ...
2
votes
3answers
29 views

Number of orbits with Burnside's lemma

We color a equilateral triangle by coloring each edge with one of $k \geq 1$ colors. Find a formula for the number of orbits under the action of $D_6$, the dihedral group of $6$ elements, on the ...
3
votes
3answers
46 views
2
votes
1answer
35 views

Arrange 18 pips on a die with at least one 0 side to maximize the probability that 5 rolls sum to 13 or more.

You are arranging pips on a standard 6-sided dice. Rules: At least one side must be left blank at 0. The average roll must be 3 (so, you have 18 pips to distribute among five sides). You want to ...
14
votes
10answers
28k views

How many ways can seven people sit around a circular table?

How many ways seven people can sit around a circular table? For first, I thought it was $7!$ (the number of ways of sitting in seven chairs), but the answer is $(7-1)!$. I don't understand how ...
3
votes
1answer
68 views

Need help with Knuth's proof for Gray Codes

I am reading Knuth's "The Art of Computer Programming" Volume 4 Fascicle 2A. Needless to say I am pretty poor in Mathematics and I need help understanding some of the proofs. If anyone has any ...
2
votes
5answers
766 views

Number of positive integral solutions to $x+y+z+w=20$ with $x<y<z<w$ and $x,y,z,w\geq1\;?$

What is the number of positive unequal integral solution of the equation $x+y+z+w=20$, if $\,x<y<z<w\,$ and $\,x,y,z,w\ge1\;?$ How to solve this question?
3
votes
3answers
99 views

Number of positive unequal integer solutions of $x+y+z+w=20$

What is the number of positive different integer solutions of $x+y+z+w=20$, where $x,y,z,w$ are all different and positive? It would be nice if coding is not used. I am given the answer $552$.
3
votes
1answer
21 views

Seeking Additional Solutions for the Number of Network Links

The Problem Show that the number of possible links in a computer network of $n$ computers ($n \in Z \land n \geq 1$) is $\frac{n(n-1)}{2}$ in as many ways as you can. My Work Solution 1 Given $n$ ...
6
votes
3answers
88 views

Probability of choosing $n$ numbers from $\{1, \dots, 2n\}$ so that $n$ is 3rd in size

We uniformly randomly choose $n$ numbers out of $2n$ numbers from the group $\{1, \dots, 2n\}$ so that order matters and repetitions are allowed. What is the probability that $n$ is the $3^{\text{rd}}$...
0
votes
0answers
18 views

maximize a sum of unit fractions (without containing a subset of sum 1)

Let $ u \ge 2 $ be fixed. Then consider: $ S(u)=\max\left\lbrace \sum_{i=1}^{u+1} \frac{c_i}{t_i} \, \middle| \, 2 \le t_1 \le t_2-1 \le \ldots \le t_{u+1}-1, \, t_i \in \mathbb{N}, \, c_i \in \...
2
votes
2answers
613 views

Gram Determinant equals volume?

I have been trying to solve this problem of finding the 'n-volume' of a paralleletope spanned by m vectors, where clearly m =< n. In general, for computational purposes, what I have managed to do ...
0
votes
0answers
40 views

Counting GF($q=8$) matrices with a certain property

Let us denote by $\boldsymbol{v}_i$ the columns of an $m \times n$ GF($8$) matrix. The field elements are enumerated $\{0,1,2,...,q-1\}$. To define the arithmetic operations between field elements, we ...
0
votes
0answers
23 views

Symmetric brace algebras - unshuffle sequences

I'm studying brace algebras in this article: Symmetric Brace Algebras. In the following definition, what do the authors mean by "unshuffle sequences"? Definition 2. A symmetric brace algebra is a ...
8
votes
1answer
30 views

Selecting disjoint subsets with the same sum from a set of ten distinct two digit numbers

My question is the following: Is it possible to select two disjoint subsets whose members have the same sum from a set of ten distinct two-digit numbers (in the decimal system)? I guess the answer ...
0
votes
1answer
36 views

There are 4 nickle coins and 4 half nickle coins. How many different options are there for the sum of 5 coins.

I have this exercise in combinatorics: In a drawer there are 4 nickle coins and 4 half nickle coins, bob takes out from the drawer 5 nickles, how many different options are there for the sum of ...
-6
votes
0answers
26 views

Permutation, Arranging letters [on hold]

Please help me! I am in a hurry! The six letters of the word “MOTHER” are rearranged in all possible orders and the words so formed are listed in alphabetical order
1
vote
1answer
30 views

Proving an inequality about a set of combinations.

Suppose $A$ is a set of $r$ combinations of an $n$ set, with $\alpha \cap \beta \neq \phi$, whenever $\alpha, \beta \in A$. Show that $$|A| \leq \binom{n-1}{r-1}$$ if $r \leq \frac n2$. What does ...
0
votes
4answers
94 views

Number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is

The number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is $\bf{My\; Try}::$ Given $x_{1}\cdot x_{2}\cdot x_{3}\cdot x_{4}\cdot x_{5} = 2 \...
0
votes
2answers
32 views

Number of permittable numbers given following conditions.

What are total numbers belonging to $\mathbb Q$ (rational) between $2008$ and $2009$ such that after decimal point their digits occur in decreasing order? \begin{align} 1) &\ 9Pi;i\in [1,9], \\ 2)...
0
votes
0answers
22 views

Prove that if B(0) = 0, then A(B(x)) is a formal power series

I'm working through my Combinatorics textbook and am stuck on this proof. The textbook explains it pretty well, but I am having trouble with one of the steps. I was hoping I could get some help here ...
0
votes
1answer
26 views

Definition of $0^\underline{m}$ for $m\leq0$

Using the general definition of falling powers for negative exponents, I was able to derive $$0^{\underline{m}} = \frac{1}{(-m)!}, m\leq0$$ However, I can't reconcile this with the product formula $$0^...
5
votes
5answers
323 views

Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$ I ...
1
vote
2answers
23 views

Constructing Turan Graphs

A "Turan Graph " on $n$ vertices is graph on $n$ vertices without triangles and with exactely $\lfloor \frac{n^2}{4}\rfloor$ edges. How many are the Turan Graphs on $8$ vertices? There's an easy ...
1
vote
1answer
39 views

Simple problem in probability

You have 100 lightbulbs. Every lightbulb is either functioning or not. You test 20 of them, and all of the 20 are functioning. What is the probability that 10 of the 100 lightbulbs do not function? ...
1
vote
5answers
64 views

Arrange black and white balls so that each pair of white balls is separated by at least two black balls

I am trying to solve the following question: How many linear arrangements of $m$ white balls and $(n-m)$ black balls are possible such that each pair of white balls is separated by at least two ...
0
votes
1answer
24 views

Approaches to combining analysis with combinatorics and number theory?

I hope this questions fits the site. I am interested in various methods of combining analysis with combinatorics and number theory. What I mean by this is that (at least to me) at first I wouldn't ...
3
votes
1answer
44 views

$\binom{n}{k}$ is a “binomial coefficient;” $n \; P \; k$ is a “__________.”

If I want to search for information concerning $\binom{n}{k}$, I can't Google that symbol directly, nor can I search for something like "n C k" and get anything relevant, but because the term "...
14
votes
1answer
413 views

How many $n$-element subsets $A$ of $\{1,2,3,\cdots,2n\}$ with specified sum are there?

Question: Let $ n$ be an postive integer number.and let $A=\{x_{1},x_{2},\cdots,x_{n}\}$, How many $ n$-element subsets $ A$ of $ \{1,2,\dots,2n\}$ are there,such $$x_{1}+x_{2}+\cdots+x_{n}=\dfrac{...
7
votes
1answer
49 views

Numbers on a circle: how many arc sums can be positive?

There are $n$ real numbers, $a_1,\dots,a_n$, arranged on a circle. Given a fixed integer $k<n$, let $S_i$ be the sum of the $k$ adjacent numbers starting at $a_i$ and counting clockwise, like this (...
1
vote
2answers
51 views

There are 10 boxes, 15 balls; 10 red, 5 blue. Each is randomly placed in a box in an independent manner. What's E[X=the number of empty boxes?]

There are 10 boxes, 15 balls; 10 red, 5 blue. Each is randomly placed in a box in an independent manner. The red balls are placed in boxes 1-10, blue balls are placed in 1-6. What is the expected ...
0
votes
3answers
51 views

Counting non-negative integral solutions

I'm reading this passage and wondering why Number of ways in which k identical balls can be distributed into n distinct boxes = $$\binom {k+n-1}{n-1}$$ could someone explain it to me please?
0
votes
1answer
52 views

How to approximate the Langford numbers with probability?

A Langford pairing, also called a Langford sequence is a permutation of the multi set {$1,1,2,2, \dots, n,n$} in such a way that there are exactly $k$ elements in between every $k$. Interestingly, ...
7
votes
4answers
165 views

Why does $(128)!$ equal the product of these binomial coefficients $128! = \binom{128}{64}\binom{64}{32}^2 \dots \binom21^{64}$?

I'm working through some combinatorics practice sets and found the following problem that I can't make heads or tails of. It asks to prove the following: $$128! = \binom{128}{64}\binom{64}{32}^2\...
0
votes
1answer
41 views

Monotone subsequence in a random permutation

I wish to compute the probability of having a log(n) length consecutive monotone subsequence in a random permutation of {1,...,n} (log with base 2). I'm trying to show it's $\leq1/n$, does it make ...
0
votes
1answer
60 views

Probability for a random permutation

Given a set of $N$ elements and a uniformly distributed random number generator, which always generates values between $0$ and $N-1$. Then the probability to get a random permutation (without re-draws)...
8
votes
4answers
1k views

How many different dice exist? That is, how many ways can you make distinct dice that cannot be rotated to show they are the same?

Dice are cubes with pips (small dots) on their sides, representing numbers 1 through 6. Two dice are considered the same if they can be rotated and placed in such a way that they present matching ...
3
votes
2answers
106 views

Find all solutions to $2 x + 3 y + 4 z = 10$

I do not have a background in math, and am wondering what type of question this is. I looked combinatorics optimization, and the knapsack problem, but found the vocabulary too dense. The problem: ...
1
vote
3answers
51 views

Combinations of 5 integers from 1 to 100 such that differences between the sorted integers of each combination is at least 5 but not more than 10?

For example , I am trying to count combinations like [1,6,14,21,27] because the minimum difference between two sequential integers in the combination is 5 and the maximum distance is 8, but I don't ...
2
votes
1answer
45 views

Binary matrices and probability

Square numerical matrix in which each cell is written or the number $0$ or the number $1$ is called binary. Let $T_n -$ the set of all binary matrix $m\times m, m=2,3,...,n$. Find the probability ...
0
votes
0answers
20 views

Number of nodes satisfying a certain property on a binary tree

Fix a large integer $M$ and construct a binary tree as follows. Assign the root node by the integer $0$. If a node is assigned the integer $n$ and $n \leq M - 2$, then $n$ has two children and ...