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

Binary string that contains all substrings of length k exactly once.

Here is the problem I'm working on (Satan's apple with bounded memory decision problem): Suppose I offer you slices of an apple, first $1/2$, then $1/4$, ... then $1/2^k$, etc. You want to eat as much ...
0
votes
0answers
8 views

Counting minimal cut sets in nonamenable graphs

Suppose that $G$ is a fixed infinite, bounded degree, countable, connected nonamenable graph, meaning that its Cheeger constant is positive. Let $x\in G$ be a fixed vertex. I need to show (for ...
0
votes
0answers
17 views

A Variant of the Set Cover Problem

Suppose we are given a set $\mathcal{S}$ of sets $S_1, S_2, \ldots, S_M$ each of size at most $B$. for some positive integer $p$, let $\{1,2,\ldots,p\} = \bigcup_i S_i$ Now, suppose we have a ...
0
votes
1answer
24 views

Intersecting Family 2

Prove that, if $k$ divides $n$ and $n\ge3k$, then any intersecting family of size $n-1\choose k-1$ of $k-$ subsets of the $n-$ set $X$ consists of all $k-$ sets containing some point of $X.$ I am ...
0
votes
1answer
34 views

Why do (the ranges of) these sequences intersect?

Let $\{(a_n,b_n)\}$, ($1\le n\le N$) be a finite sequence and $\{(s_n,t_n)\}$ ($n\ge 1$) be an infinite sequence, both in $(\{0\}\cup \mathbb{Z}^{+})^2$. We have $a_1=0$ and $b_N=0$. Also, either ...
2
votes
2answers
68 views

Richard Pavlicek's combinatorial problem

In the game of bridge, a standard deck is dealt to four players, 13 cards each. That gives a total of $\binom{52}{13,13,13,13}$ distinct deals. How many distinct deals can be dealt if all spot cards ...
0
votes
2answers
40 views

Find the Number of Lattice Paths

How many lattice paths are there from $(0, 0)$ to $(10, 10)$ that do not pass to the point $(5, 5)$ but do pass to $(3, 3)$? What I have so far: The number of lattice paths from $(0,0)$ to ...
0
votes
1answer
68 views

Proving $\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$

Prove the identity: $\displaystyle\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$ It looks a bit similar to the "no gets their own hat back" problem or inclusion exclusion ...
0
votes
4answers
121 views

Number of ways you can form pairs with a group of people when certain people cannot be paired with each other.

Let's say you have a group of eight people and you want to form them into pairs for group projects. There are $\frac{8!}{4!.2!}$ ways to do it. ($8!$ is the total number of ways $8$ people can be ...
0
votes
0answers
16 views

Counting permutations of length n without patterns

Count the number of permutations of length n that avoid patterns of high-low-mid. A pattern of hi-lo-mid is 3 integers in the pattern such that for $a_i$,$a_j$,$a_k$, we have i < j < k, $a_i$ > ...
0
votes
1answer
39 views

How many multisets of length $d$ of a set of $n+1$ elements?

The number of multisets of length $d$ of a set of cardinality $n+1$ is $${n+d}\choose{n}$$ This number is, among other things, the dimension of the vector space of homogeneous polynomials of degree ...
0
votes
2answers
34 views

Probability of tossing five coins and getting at least one head

here is my dilemma. I want to know the probability of getting at least one head in five coins being tossed one after the other. Could you help me get the logic of this as it involves both mutually ...
1
vote
1answer
47 views

The number of ways of dividing a number by three separate integers.

How many ways can I arrive at the number $45$ by exactly using $5$, $10$ and $20$. I can use each number as many times as necessary. (e.g $9×5$, $20+(5×5)$) this leads to the question, if the number ...
-1
votes
0answers
30 views

Snow White split 3 liters [duplicate]

Snow White split 3 liters of milk into the cup of the Seven Dwarfs. Before the meal, the Dwarfs play a game as follows: Dwarves are first divided all his cup of milk into the cup of the remaining six ...
3
votes
1answer
32 views

Combination of $k$ vertices from the $n$ vertices of $n$-sided regular polygon

Select $k$ vertices from the $n$ vertices of an $n$-sided regular polygon. For two of this kind of $k$-combination $A$ and $B$, they are treated as an identical one if $A$ can transform to $B$ by ...
5
votes
0answers
59 views

Combinatorial Interpretation of these two identities

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} ...
2
votes
2answers
45 views

Intersecting family

Let $X = \{1,...,7\} \ $ and let $B$ consist of the seven subsets $$\{\{1,2,3\}, \{1,4,5\}, \{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}\}.$$ Let $F$ be the set of all those subsets of $X$ ...
0
votes
1answer
24 views

What are the permutations of 6 different variables with multiple values?

Apologies if this is better explained in another question; perhaps I'd better get up to speed with mathematics terminology so I may find it... There are the following 6 options for searching on a ...
0
votes
1answer
52 views

How many ways to arrange books on a bookshelf?

In how many ways can $n$ distinct books be arranged on $k$ distinct bookshelves if at least one shelf is to be empty? Well, I tried writing out the possible number of ways for the cases that $n=1$ ...
3
votes
1answer
59 views

Working with finitely presented groups in GAP

This is more of a question specifically about how GAP handles calculations with finitely presented groups rather than about group theory. I have several finite group presentations that I would like ...
1
vote
2answers
34 views

Simplification of powers

I think this is a really simple question, but for some reason my brain can't get round it. I am proving a combinatorial result by probabilistic method and the last step has got me really confused. ...
0
votes
2answers
22 views

Find a recurrence relation and initial values for W(n), the number of words of length n from alphabet {a,b,c} with no adjacent a's.

Find a recurrence relation and initial values for W(n), the number of words of length n from alphabet {a,b,c} with no adjacent a's. This is a problem from How to Count: An Introduction to ...
3
votes
4answers
236 views

Writing numbers as a sum of 2s and 3s

Is there a way to count the number of ways a positive integer N, can be written as a sum of twos and threes? Are there any patterns? Re-arranging the twos and threes are distinct..(makes sense right?? ...
1
vote
0answers
34 views

Inviting 4 friends out of 8 for a week such that each friend visits at least once

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once. Let's number the friends for brevity, 1 to 8. This is like asking how ...
2
votes
0answers
84 views

Combinatorics - Contest Problem. Seeking a mathematical enhancement of my solution.

A group of friends, numbered 1, 2, 3, . . . , 16, take turns picking random numbers. Person 1 picks a number uniformly (at random) in [0, 1], then person 2 picks a number uniformly (at random) in [0, ...
5
votes
1answer
53 views

Solve $x + y + t \le 10$ [duplicate]

For nonnegative integers, $x, y, t$ solve, $$x + y + t \le 10$$ This includes then: $x + y + t = 0$, ..., $x + y + t = 10$. $x + y + t = 0$ has $1$ solution $= \binom{2}{2}$. $x + y + t = 1$ ...
1
vote
2answers
38 views

maths permutation help

An experiment consists of randomly rearranging the 9 letters of the word TARANTULA, where all possible orders of the 9 letters are equally likely. Find the probability of each of the following events: ...
1
vote
0answers
38 views

Linear Algebra and Graph theory

I haven't done any linear algebra for a long time and currently reading about linear algebra in graph theory and had a few queries. So i'm looking at the definition of a vertex space. Firstly let ...
2
votes
0answers
31 views

For any given value x, are there uncountably many (countably infinite) binary sequences (ones and zeroes) whose limiting relative frequency is x

I have the following question, and given few proofs (provided by friends, professors, and my myself) which seem to work, I suspect the answer is yes: But I am still not completely sure. The question ...
0
votes
2answers
24 views

Number of ways to ride from one city to another

I stucked with some combinatorial problem: There are 3 highroads between city A and city B. Highroads are intersected with 4 countryroads. What is the number of ways to make a tour from A to B, if we ...
0
votes
1answer
57 views

How many natural numbers less than $10^{2015}$ have their digits in non-decreasing order?

I am having pretty hard time with combinatorics. Could someone explain me step-by-step how to get to solution? Note: digits are observed from left to right.
0
votes
1answer
27 views

Permutations and group acts

How many ordered pairs of permutations $(\pi , \sigma )$ in $S_n$ such that $\pi \circ \sigma =\sigma \circ \pi $. I think i need consider group acts on itself by conjugation $\pi (\sigma )=\pi \circ ...
0
votes
1answer
42 views

Proof of sum-free set in $\mathbb{Z}_p$

Consider $a \in \mathbb{Z}_p \backslash\{0\}$ and define $aS=\{as | s \in S \}$. I want to show that $S$ sum-free over $\mathbb{Z}_p \iff aS$ sum-free over $\mathbb{Z}_p$, and then I want to show that ...
0
votes
2answers
43 views

How to systematically count the number of integer isosceles triangles?

How to count number of isosceles triangles with integer sides where all are less than $a,a\in\mathbb R$(say 9999). Yes I know the triangle inequality. Let two sides be $x$ and remaining be $y$. Then ...
0
votes
0answers
37 views

Graph Coloring and Complete Graph

If a graph is k-colorable, then does it imply that it must have a k-complete graph as it's subgraph? For example if a graph has chromatic no = 5, then is this sufficient to imply that it must have K5 ...
1
vote
1answer
59 views

If every row in a square grid corresponds to a column, then every column corresponds to a row.

I am looking for a proof of the following: A square grid is filled out with symbols from some alphabet, with one symbol in each square of the grid. Each row of the grid is the same as some column ...
0
votes
0answers
49 views

combinatorics - pigeonhole principle - 2

I've advanced a little with this question but I'm not sure that I'm in the right direction. For any set $X$ with $n$ positive numbers, $n>5$, prove the existiance of subset $Y \subset X$ so that ...
0
votes
2answers
27 views

What is the number of people that leave the meeting?

In a business meeting, each person shakes hands with each other person, with the exception of Mr. L. Since Mr. L arrives after some people have left, he shakes hands only with those present. If the ...
1
vote
1answer
40 views

Relationship between Factorial and Binomial coefficients

Over at this link, there is a claim that $(2n)! = n!n! {{2n} \choose {n}}$ - see Tom Boardman's answer, the second one down. I'm wondering why this is the case and if anyone can provide a proof. Is ...
1
vote
1answer
15 views

Multiplying and factoring in Formal Power Series

I'm working with some formal power series in my homework. Somewhere in the middle of my hw problem I reach a point where I would really like to factor, but I'm not sure if I can. Suppose $F_k$ ...
1
vote
2answers
31 views

When do we need combination factor?

Say I want to draw 4 balls from a big ball pool, with 3 kinds of colors: red 50%, white 30%, black 20%. Now, I draw 1 ball of each time for 4 times, each time with replacement(or the pool is big ...
0
votes
0answers
45 views

how would i simplify this into an identity?

$$ B_{n,k}^{f\ln(g)} = B_{n,k}\left(\frac{d}{dx}[f(x)\ln(g(x))], \frac{d^2}{dx^2}[f(x) \ln(g(x)), \cdots, \frac{d^{n-k+1}}{dx^{n-k+1}}[f(x) \ln(g(x))]\right) $$ We know that: $$ B_{n,k}^{f\ln(g)} = ...
1
vote
1answer
27 views

Why can I not include unused cards into a second binomial coefficient?

In trying to count the number of 13-card hands where there is at least one ace and no J, Q, K, we can see one way is $$ \sum_{k=1}^4 \binom{4}{k}\binom{36}{13-k} = 9722433280. $$ However, I cannot ...
4
votes
2answers
54 views

Segments on a family of parallel lines

Let $\{l_i:i\in I\}$ be a family of parallel lines on the plane $\mathbb{R}^2$. Suppose for each $i\in I$ there is a closed segment $s_i\subset l_i$. Moreover, for each triple $i_1,i_2,i_3$ there ...
0
votes
2answers
78 views

In the card game “Projective Set”: Compute the probability that $n$ cards contain a set

In the game of Projective Set, it turns out that any seven cards contain a projective set. For fewer than 7 cards, how can we determine the probability that one or more sets exist (in terms of the ...
0
votes
0answers
33 views

How many boolean formulas are there over n variables?

Suppose our alphabet is $x_1, \ldots, x_n$, $\wedge, \vee$. How many legal boolean formulas can we have? I know it's more than $2^n$ since $$(x_1 \vee x_2) \wedge x_3 \ne x_1 \vee (x_2 \wedge x_3),$$ ...
3
votes
3answers
120 views

Find the number of ways to form 15 teams out of 15 men and 15 women.

In how many ways can 15 teams be formed, each consisting of a man and a woman, from 15 men and 15 women. This looks like the same problem as finding the number of bijective functions from a set $A$ ...
5
votes
1answer
63 views

Expected Value of the Maximum Number of Heads in n Flips

How would one go about finding the expected value of the maximum number of consecutive heads when flipping a coin $n$ times? For small $n$, it seems easy to brute-force it (i.e. when $n = 3$, the ...
4
votes
1answer
100 views

In the card came “Projective Set”, show that 7 cards do always contain a set. [duplicate]

In the game of Projective Set, it turns out that any seven cards contain a projective set. How can one prove this? And for fewer than 7 cards, how can we determine the probability that one or more ...
-1
votes
0answers
26 views

Modular Multiplicative Inverse of a Number

Modular Multiplicative Inverse for a prime M A^(M-1) % M = 1 From Fermat's Little Theorem Hence, A * A^(M-2) % M = 1 Or in other words, A^-1 % M = A^(M-2) % M ...