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)

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
33 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
82 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
36 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
44 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
77 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
118 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 ...
0
votes
0answers
28 views

Calculating the sum of all pairs

You are given a set of integers. How do you calculate the absolute value sum of all possible pairs? So given {2, -3, 1} $S = |2-3| + |2+1| + |-3+1| = 6$ I realize that there's a pattern here but it ...
0
votes
1answer
21 views

Summation of all possible combinations

I need to get the summation of all triplets produced by (nCr) where r = 3. I've written a program that does this but it takes too long when n is very big.
-2
votes
0answers
51 views

Fastetst method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$

Is there any faster method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$? Lucas theorem is also turning out to be slow! $a,b\leq10^9$ and $m=10^6+3$.
-2
votes
2answers
24 views

How many four-digit numbers contain only the digits 1 and 2 and each of them at least once? [closed]

Question: How many four-digit numbers contain only the digits 1 and 2 and each of them at least once? I have tried to do this question by listing all the possible values and have come to answer of ...
0
votes
1answer
38 views

How to calculate $\binom{17}6 21$? [closed]

$\dbinom{17}{6}21$ I understand most of this, where you use $$C(n,r) = \dfrac{n!}{r! (n - r)!}$$ but I am not sure how to calculate with the $21$ and the $17$ choose $6$.
2
votes
1answer
70 views

Pairing Vertices by Edge Color

We have a graph $G$ with an even number of vertices. Every pair of vertices is connected by either a green or red edge. If every vertex is connected to at least one other vertex by a green edge, can ...
2
votes
3answers
87 views

Proving the infinite sum of $1/2^i$ without induction

Prove $$\sum_{i=1}^n \frac{i}{2^i} = 2-\frac{n+2}{2^n} $$ Pretty trivial to do with induction, but as a practice problem for solving recurrences we have to do this only by repeating $\sum_{i=1}^n ...
2
votes
1answer
57 views

Evaluate $\lim_{n\to\infty} \frac{\sum_{r=0}^n\binom{2n}{2r}3^r}{\sum_{r=0}^{n-1}\binom{2n}{2r+1}3^r}$.

Evaluate : $$\lim_{n\to\infty} \frac{\sum_{r=0}^n\binom{2n}{2r}3^r}{\sum_{r=0}^{n-1}\binom{2n}{2r+1}3^r}$$ The answer given is $\sqrt3$. Frankly, have no clue where to begin. I thought of putting ...
3
votes
3answers
57 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
1
vote
0answers
31 views

Interesting horserace counting problem

So for a horserace with no drawing horses there are n! Results. How many results will there be if the horses can draw?
0
votes
0answers
42 views

combinatorics,defects on disks

$k$ defects are randomly distributed amongst $n$ computer disks produced by a company AND any number of defects may be found on a disk and each defect is independent of the other defects Let $p(k,n)$ ...
1
vote
0answers
10 views

graph has no bridge iff a spanning subgraph of the graph is the support of a flow

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$. Let $\mathcal{O}$ be an orientation of the edges of $G$. ...
0
votes
1answer
27 views

Bound the number of different natural numbers that fit as a sum in $n$ as $n$ increases

Let me explain... I have $n$ integers, with $k$ different values where $k \leq n$. If I sum together the integers with same values I will get a set of different values frequencies. Now if I sum ...
4
votes
2answers
67 views

Sum of every row, column and diagonal is equal to 0. Is it possible that none of the numbers is eqaul to zero?

A square with 2015 rows and 2015 columns is filled with integers. The sum of every row is equal to zero, the sum of every column is equal to zero, and sum of the two main diagonals is equal to zero. ...
0
votes
2answers
24 views

Why does $\binom{n}{m}\frac{(n-1)!}{(m-1)!}$ count collections of m ordered lists of n elements?

I'm reading a book on combinatorial proofs and there is one identity there in proof of which it is written that $\binom{n}{m}\frac{(n-1)!}{(m-1)!}$ counts collections of m ordered lists whose disjoint ...
0
votes
1answer
55 views

Sum of Number of non-decreasing sequences [duplicate]

I know that the number of non-decreasing sequences of length $n$ and numbers in the sequence lying in the range $[l,r]$ is given by $$\binom{n+r-l}{n}$$ What is the formula to find the ...
0
votes
1answer
20 views

Edge intersections of paths

I am trying to read up on the nonrepetitive graph coloring problem. That's for context, my question can be answered without referring to the problem. I have a graph G, and I am interested in looking ...
0
votes
0answers
43 views

Is there a closed-form expression for the following sum?

Is there a closed-form expression for the following sum: $$\large\sum_{\{n_i\}} \frac{x_i^{n_i}}{\prod_i (i!)^{n_i} n_i!}$$ where the sum runs over all combinations of $\{ n_{i=0,\dots,k} \}$ such ...
2
votes
2answers
119 views

Number of subsets of length 7 [duplicate]

I have the following summation: $$\sum\limits_{k=7}^{n} {k-1\choose 6} $$ and apparently it counts the number of subsets of {1, 2, . . . , n} having size 7. Why is this?