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)

0
votes
5answers
40 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
37 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, ...
5
votes
4answers
115 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 ...
2
votes
0answers
24 views

The number of positive integer solutions to the equation $x_1+2x_2+…+nx_n=n^2.$

Let $n \ge 2, n \in \mathbb N$. $A_n$ denotes the number of positive integer solutions to the equation $$x_1+2x_2+...+nx_n=n^2.$$ Prove inequality $$\frac{n^n(n-1)^{n-1}}{2^{n-1}\left(n!\right)^...
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)...
5
votes
4answers
312 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 ...
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 ...
1
vote
2answers
44 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 ...
3
votes
2answers
96 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
45 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
36 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
18 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 ...
0
votes
1answer
15 views

Determining when two binary strings represent the same necklace or when one binary string is periodic

An equivalence relation on binary strings calls two strings equivalent if one can be obtained from the other by a cyclic permutation of the characters. Combinatorialists call the equivalence classes ...
0
votes
1answer
26 views

How would I calculate the total number of combinations [on hold]

Lets say I have 4 lines or rows lets call them Row 1 .. Row 4 Now the total number of ways to delete the rows are: Row 1 (leaving Row2, Row3, Row4) Row 2 (leaving Row1, Row3, Row4) Row 3 Row 4 ...
1
vote
2answers
49 views

Flipping coins Conditional Probability

Six identical-looking coins are in a box, of which five are unbiased, while the sixth comes up heads with probability 3/4 and tails with probability 1/4. Three coins are chosen from the box at random ...
2
votes
1answer
24 views

Generic method to distribute n distinct objects among r people such that each person gets at least one object

Is there any generic method to solve problems of the kind - "How many ways to distribute n distinct objects among r person(s) such that each person gets at least 1 object?". I am aware of 2 different ...
0
votes
2answers
21 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 ...
2
votes
2answers
1k views

counting simple, connected graphs

I've been thinking about this for a few days, but I haven't found a general solution yet. How many distinct simple, connected, undirected graphs are there of n labelled vertices? For example, there is ...
12
votes
1answer
166 views

Arrange Relatively Prime Numbers in a Circle

The question: In how many ways can you arrange the numbers $1$ to $8$ in a circle so that neighboring numbers are relatively prime? Can you generalize for $1$ to $n$? It's fairly easy to list ...
5
votes
5answers
602 views

Black and white beads on a circle

There are $n$ beads placed on a circle, $n\ge 3$. They are numbered in random order as viewed clockwise. Beads for which the number of the previous bead is less than the number of a next bead are ...
0
votes
0answers
30 views

Two variable recurrence relations with conditionals

Is it possible to obtain a generating function for the sequence described by the following recurrence? $$ f(n,m) = \begin{cases} f(n, \thinspace m-1) + f(n-m, \thinspace m-1), & \text{ if } n \...
1
vote
1answer
74 views

Closed form expression sum-product of binomials

Is it possible to find a closed form expression for $$\sum_{j=1}^a\sum_{i=1}^{b} {i+j-1\choose j} {i+j-1\choose i},$$ where $a \geq 1$, and $b \geq 1$ are integers. I couldn't apply any type of ...
6
votes
1answer
187 views

Combinatorics: Distributions with several constraints - potential generating sequences?

This seems to be a "stars and bars problem" - however I am unsure how to apply a constraint. Furthermore, I would like to understand how this would be done in both counting as well as generating ...
4
votes
3answers
696 views

No closed form for the partial sum of ${n\choose k}$ for $k \le K$?

In Concrete Mathematics, the authors state that there is no closed form for $$\sum_{k\le K}{n\choose k}.$$ This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the book)....
0
votes
2answers
26 views

Optimising my chances of drawing a specific card from a small deck.

I have a deck of 24 cards, 3 of which are aces. I want to figure out my chances of drawing at least one ace based on the number of cards I draw. I'm pretty sure if I draw one card my chance is 12.5% I'...
1
vote
0answers
30 views

Congruence numbers

Having read about Stirling numbers of the second kind I am curious. The article says it shows the number of equivalence relations on a set $n$ with $k$ equivalence classes which makes sense to me from ...
6
votes
0answers
36 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 (...
2
votes
1answer
46 views

Properties of transfer matrices and their traces

I'm having difficulties understanding some arguments in my statistical mechanics lecture and would like to make them more rigorous by proving some properties. For the Ising model on a lattice we ...
6
votes
3answers
672 views

Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$

I recently came across a question while studying for an exam. I haven't been able to solve it. We had to prove: $$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$ We had to use counting techniques. This was ...
3
votes
1answer
591 views

Dominos ($2 \times 1$ on $2 \times n$ and on $3 \times 2n$)

How many ways are there to tile dominos (with size $2 × 1$) on a grid of $2 × n$? How about on a grid of $3 × 2n$?
2
votes
1answer
58 views

a collection of 20 marbles from infinite pool of 2 color marbles with replacement.. [on hold]

I have an infinite supply of pink and blue marbles. Probability that any random draw will yield a pink marble is "p" and prob. of picking blue is 1-p. Let us assume p=0.4 if a numeric value helps. ...
1
vote
1answer
63 views

longest way to rearrange students before returning to original arrangement? [on hold]

This is Q24 from the 2012 Intermediate Australian Mathematics Competition: "A teacher has a class of twelve students. She thinks it would be a nice idea if they change desks every day, so she has ...
0
votes
2answers
19 views

Permutation of coefficient with coditions [on hold]

I have 6 coefficients, (V1,V2,H1,H2,D1,D2). Their permutation is 6! = 720. But I have a rule: V2 cannot lead V1, H2 cannot lead H1 and D2 cannot lead D1. For example: V2V1H1H2D1D2 is prohibit. ...
0
votes
0answers
35 views

How many strings of 12 lowercase letters with repetitions

Consider strings of 12 lowercase letters, such as aksdjmnuuyio. How many strings either are a repetition of 2 strings of 6, such as aksdjmaksdjm, or a repetition of three strings of 4, such as ...
9
votes
5answers
168 views

How many arrangements of the letters in the word CALIFORNIA have no consecutive letter the same?

First off, the correct answer is $$584,640 = {10!\over 2!2!}- \left[{9! \over 2!}+{9! \over 2!}\right] + 8!$$ which can be found using the inclusion-exclusion principle. My own approach is different ...
1
vote
1answer
63 views

Number of permutations with two elements in one cycle

Show, that for a set of permutations of a set $\{1,\dots,n\}$ $(n>0)$ the following statement is true. statement: The number of permutations where $1$ is in the same cycle with $k$, and the number ...
3
votes
1answer
27 views

Bell numbers and the Moments of expected number of fixed points

Let $X_N$ be the random variable corresponding to the number of fixed points (1-cycles) in a permutation chosen uniformly at random from $S_N$. Then, the $m^{\text{th}}$ moment, when $m < N$, is ...
0
votes
5answers
40 views

What is the probability of obtaining a hand with TWO PAIRS in a standard 5 card game of poker?

What is the intuition behind, 'What is the probability of obtaining a hand with TWO PAIRS in a standard 5 card game of poker?' I know the solution is, $$\frac{\binom{13}{2}\binom{4}{2}\binom{4}{2}...
0
votes
3answers
40 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
3answers
46 views

What is the probability of getting NO PAIRS in a $13$-card poker game?

What is the probability of getting NO PAIRS in a $13$-card poker game? Here is my attempt: The setup for the required poker hand would be: $$ABCDEFGHIJKLM$$ where $A, B, \ldots, M$ are distinct ...
0
votes
0answers
21 views

Is there a faster way of computing the probability of a sum $S$ when $n$ dice are rolled? [duplicate]

So far, I've only had to deal with $2$ dice or $3$ dice problems. For example, if the problem asks to find the probability that a sum of $8$ will be achieved from rolling $3$ dice, I just list all the ...
0
votes
0answers
18 views
1
vote
2answers
51 views

Scheduling a Round Robin tournament - 4-way games

I'm looking to schedule 16 players to play a round robin tournament with each other such that there are 4 players at each table. I'd like for each player to play with each other player exactly once ...
1
vote
1answer
46 views

Notation for probability: $C_n^r$, $P_n^r$, $A_n^r$?

I was told that $C^{n}_{k}$ refers to combinations or choose k elements from n elements, $\bar{C^{n}_{k}}$ refers to combinations with repetitions (i.e. $C^{n+k-1}_{k}$), and $P^{n}_{k}$ refers to ...
1
vote
1answer
99 views

Let $S$ be a set of $2009$ positive integer numbers.

Let $S$ be a set of $2009$ positive integer numbers. $S$ has the property that for any distinct $a, b, c\in S$ if $gcd(a, b)>1$, then at least $gcd(a, c)$ or $gcd(b, c)$ is also greater than $1$. ...
0
votes
2answers
46 views

Prove that a graph has a cycle of length no more than $14$

A graph contains $2016$ vertices, its chromatic number is $5$, prove that this graph has a cycle of length $\leq 14$. Where do I start?