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
1answer
21 views

Does a sum of squares become smaller as the number of terms increases?

I am interested in the following question: Let $,kn$ be a positive integeres. Assume $\sum_{i=1}^{k} L_i=\sum_{i=1}^{k+1} \tilde L_i=n$, where $L_i,\tilde L_i$ are positive integers. Is it true ...
3
votes
1answer
215 views

Number of ways in which papers can be arranged so that mathematics papers do not come together?

$11$ papers are set for an examination in which two are of mathematics. Number of ways in which papers can be arranged so that mathematics papers do not come together? There are $11!$ ways in total. ...
8
votes
4answers
933 views

Why does it have to be an integer?

Let $k$ and $n$ be integers greater than 1. Then $(kn)!$ is not necessarily divisible by A. $(n!)^k$ B. $(k!)^n$ C. $n!\cdot k!$ D. $2^{kn}$ I believe option D is correct ...
2
votes
1answer
28 views

Calculating the number of elements of a given order in a group of permutations.

Let $S$ denote the group of all those permutations of the English alphabet that fix the letters T, E, N, D, U, L, K, A, and R. Other letters may or may not be fixed. Show that $S$ has elements ...
2
votes
1answer
27 views

Existence of a $d$-regular graph such that $|N_G(x) \cap N_G(y)| = \lambda$.

Consider a $d$-regular graph $G = (V, E)$ of order $n$ such that $|N_G(x) \cap N_G(y)| = \lambda$ for all distinct $x, y \in V$. By double counting we have a necessary condition $\lambda (n - 1) = d(d ...
0
votes
0answers
46 views

Find the number of ways to select six distinct integers from the set $\{1,2,\dotsc,49\}$ such that no two consecutive integers are selected. [closed]

Find the number of ways to select six distinct integers from the set $\{1,2,\dotsc,49\}$ such that no two consecutive integers are selected.
1
vote
1answer
60 views

Tennis league - minimum number of games

In a tennis league, consisting of 32 players, each player played with each other at least twice and at maximum Q times. Knowing that each of them participated in a different number of games, can you ...
1
vote
0answers
32 views

Is there a combinatorial identity for the following sum?

Let $a,b,c$ be integers. Is there by any chance a neat combinatorial identity for the following sum? $$ \sum_{j=0}^c{a + jb \choose j}. $$ Thanks!
0
votes
1answer
18 views

Does every partition of n correspond to some permutation of [1,2, … n]?

It is known that every permutation can be decomposed into disjoint cycles. The cycle type gives the length of each cycle. The sum of cycles length is n. I am wondering whether every partition of n ...
1
vote
3answers
27 views

How many ways can you pick out 15 candies total to throw unordered into a bag and take home

A store sells 8 kinds of candy. How many ways can you pick out 15 candies total to throw unordered into a bag and take home. here 15 candies.. so we choose 8 from out of 15 is ..=$^{15}C_8$ is i am ...
0
votes
0answers
27 views

How many 4-permutations on {1.. 9} are there? [closed]

Please if you could explain how to solve this problem. How many 4-permutations on {1.. 9} are there?
0
votes
2answers
31 views

Probability that digits 1,2 and 3 will appear in a decimal m digits, how do I tweak my thinking to be correct?

So I first thought to approach this as the complement of an inclusion exclusion problem, $P(A_{1}\cap A_{2}\cap A_{3})=1-P(A_{1}\cup A_{2}\cup A_{3})$ Where $A_{i}$ is the event that digit i appears ...
1
vote
2answers
56 views

What is the probability to fill rows of a cinema hall?

This is the problem I'm trying to solve, but I'm not sure I'm on the correct path! would appreciate your feedback guidence and help. So the problem is: there're 3 rows in a cinema hall. the first one ...
1
vote
1answer
37 views

Vandermonde's Convolution special case.

I am not able to show this case of Vandermonde's Convolution without using induction. Can someone help me? $$ \binom{n}{m} = \sum_{k=0}^{m} \binom{n-p}{m-k} \binom{p}{k}. $$ I thank now.
0
votes
1answer
21 views

r-combination from n objects where objects can be indistinguishable or distinguishable

How to solve this kind of combinatorial problem. You are given n objects and you have to find out r-combination from it. As example there are 4 objects.. 1 2 2 3..you have to find out how many ...
4
votes
4answers
286 views

Sum of sum of binomial coefficients

I know there is no simple way to solve the sum: $$\sum_{k=0}^{j}{{n}\choose{k}}$$ But what about the equation: $$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$ Are there any simplifications or ...
-4
votes
2answers
64 views

How many $4$-sequences on $\{1, \ldots, 9\}$ are there? [closed]

How many $4$-sequences on $\{1, \ldots, 9\}$ are there? Please explain how to solve this problem as I am lost, as the text book does not explain that well.
3
votes
2answers
45 views

Combination of elements in a ring and selecting non adjacents

Ok, suppose we have a clock, with the usual design of numbers ordered from 1 to 12 (so 1 and 12 are adjacents). The question is what is the number of possible combinations of four non adjacent ...
0
votes
0answers
23 views

isomorphic permutation groups with same cycle index [closed]

Is there two nonidentical isomorphic permutation groups with same cycle index? (Two permutation groups A and B on sets X and Y, respectively, are said to be identical, if there is a function 1-1 map ...
3
votes
3answers
84 views

How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times?

How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times? The solution is supposed to be derived using Inclusion-Exclusion. Here is my attempt at a ...
14
votes
3answers
172 views

How many values does the expression $1 \pm 2 \pm 3 \pm \cdots \pm n$ take?

How many different values does the expression $1 \pm 2 \pm 3 \pm \cdots \pm n$ take? I was wondering about this problem and didn't think it was immediately obvious. The answer can't be $2^{n-1}$ ...
0
votes
1answer
21 views

How many n-digit numbers with strictly increasing digits do exist?$(n<10)$

How many n-digit numbers with strictly increasing digits do exist?$(n<10)$ We mean numbers like: $13458$,these numbers do not have $0$ as a digit.How can we count them?? I used trees to distinguish ...
1
vote
0answers
27 views

Success runs in dependent trials

There are 260 business days in a year. We have 54 employees. Each employee is required to bring donuts twice a year on different days. Each employee chooses the two days at random, independently of ...
0
votes
1answer
21 views

Drawing exactly $r$ red, $g$ yellow and $b$ blue balls out of an urn

In an urn, let there be $U \in \mathbb{N}$ balls. Of these balls, $R$ are red, $G$ are yellow and $B$ are blue, and there are no other colors than these in the urn. (So, $R + G + B = U$.) Now, without ...
2
votes
1answer
31 views

Enumerating the primitive recursive functions without repetition

According to this paper (and this one), it is possible to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. I am ...
0
votes
1answer
21 views

permutations of n objects

Does the number of permutations of $n$ objects, $r$ alike of one kind and $n−r$ alike of another kind, always equal the combinations of n different objects taken $r$ at a time? Explain. I know ...
0
votes
0answers
27 views

Measure of Connectivity on a Chessboard

I'm programming a boardgame...game. The basic idea of it is there are two players (call them $X$ and $Y$) that are trying to trying to build a wall connecting the North and South, and East and West ...
0
votes
0answers
31 views

Multivariable recurrence: Solving $c(n,k) = c(n-1,k) + c(n-1,k-1) = \binom{n}{k}$ by algebraic methods.

Let $(c_{n,k})_{n,k=0}^{\infty}$ be defined by $c(0,0)=1$, $\:\:c(0,k)=0 \:\: \forall \: k > 0$ $$c(n,k) = c(n-1,k) + c(n-1,k-1) \:\:\: \forall \: n \geq 1$$ I can show that the ...
0
votes
2answers
32 views

How to count the number of x in a rows in a larger set.

For example, I have 4 in a row like so: xxxx I can see that it has 2 xxx in it and 3 xx. ...
1
vote
1answer
30 views

Proof by strong induction combinatorics problem

$1(1!) + 2(2!) + 3(3!) + \dots + n(n!) = (n+1)! - 1$ How do we prove this by strong induction? I know how to do it with weak induction, but how would strong induction work with this problem?
0
votes
2answers
35 views

Find $n$ such that the congruence $x^n\equiv 2\mod 13$ has a solution for $x$.

Find $n$ such that the congruence $x^n\equiv 2\mod 13$ has a solution for $x$. I am not getting any idea how to start this problem. Please give some hits
0
votes
1answer
15 views

Arrangements of crew in two sides of a boat - permutations and combinations

A boat crew consist of 8 men, 3 of whom can row only on one side and 2 only on the other. The number of ways in which the crew can be arranged is This is a problem my math teacher has given ...
5
votes
3answers
40 views

Game is winnable if and only if $n \neq k$

Integers $n$ and $k$ are given, with $n \ge k \ge 2$. You play the following game against an evil wizard. The wizard has $2n$ cards; for each $i = 1, \ldots, n$, there are two cards labelled $i$. ...
2
votes
0answers
38 views

$(k^2)! \cdot \prod_{j = 0}^{k = 1} {{j!}\over{(j + k)!}}$ integer for $k \in \mathbb{N}$

How do I see that for any positive integer $k$,$$(k^2)! \cdot \prod_{j = 0}^{k = 1} {{j!}\over{(j + k)!}}$$is an integer?
2
votes
1answer
54 views

How many more edges can be added to a graph while keeping it acyclic?

If I have a connected, directed graph with $n$ vertices and $m$ edges, is there some sort of formula that describes how many more edges can be added to the graph while keeping it acyclic?
0
votes
0answers
31 views

proof of number of sub arrays of an array of size $N$ using combinatorics

What is the proof that number of sub arrays of an array of size $N$ is $$\frac{N(N+1)}{2}$$
0
votes
0answers
17 views

Can you identify this stochastic process?

So I run into this problem the other day and I cannot even think of the keywords I need to use to look it up. For the discrete random variable $X$ we have: $P_{\Delta X(t)} = F\big(X(t-1), ...
-1
votes
1answer
41 views

How do I find all n values for which the equation $\phi (n) = 8$ holds? [duplicate]

I've heard all kinds of different ways to solve this problem, yet haven't been able to apply them specifically to the number 8 (Worked fine for 6 for example). I'd love to see a well-explained ...
7
votes
2answers
549 views

Number of ways of visiting N places

A tourist wants to visit $N$ cities, each numbered from $1$ to $N$, but he wants to visit them in a weird order. A weird order is such in which no city numbered $i$ is the $i$-th to visit in his ...
5
votes
2answers
164 views

How many integers from 43523 to 93107 contain at least one digit 7

How many integers from $43523$ to $93107$ contain the digit $7$ at least once? I know that if we had $43000$ to $93000$, we would subtract integers that do not contain digit $7$ from the total ...
1
vote
0answers
25 views

Number of ways to get from a point to another one in the plane

I was trying to solve the following problem related to "counting cases": Consider the point $(0,0)$ in the plane and another point $(m,n)$ with $m,n>0$ integers. Suppose you want to get from the ...
1
vote
0answers
23 views

Real world uses or interesting facts about/for Associahedron or Permutohedron

I'm doing a small research project into these but their Wiki page and other pages I've looked at just detail what they are, and their properties. Does anyone know of any real world applications or ...
1
vote
0answers
28 views

The Divisors of $s(2s+1)$ and Primes $n$, $4n+1$, and $6n+1$

This question is somewhat related to this one. Most of this is by way of a computer search: claim: If $s$ is any positive integer I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be the divisor ...
2
votes
1answer
19 views

For each of the following restrictions, find the smallest size n for strings over $\{a, b, c\}$ that can be used as codes for $27$ people.

For each of the following restrictions, find the smallest size $n$ for strings over $\{a, b, c\}$ that can be used as codes for $27$ people. a. There are $k$ $a$’s, $l$ $b$’s, and $m$ $c$’s and $k + ...
0
votes
3answers
73 views

How many distinct ways can the number be written as product of $3$ factors?

How many distinct ways can the number $126$ be written as a product of $3$ positive integer factors? I found that the prime factors are $126=2\times3\times3\times7$. But how to get number of ...
1
vote
1answer
24 views

What is the probability Amy wins a lottery prize for correctly choosing 5, not six, numbers…

Here is the full question: What is the probability that Amy wins a lottery prize for correctly choosing 5, not six, numbers out of six integers chosen at random from the integers between 1 and 40 ...
2
votes
1answer
21 views

Half primes in the set

Let S be 30 element subset of {1,2,....2015} such that every pair of elements in S are relatively prime. Prove that at least half of the elements in S are prime numbers
0
votes
0answers
34 views

Combinatorial Nullstellenatz riddle

I've been unable to solve the last problem here: http://www.mit.edu/~evanchen/handouts/BMC_Combo_Null/BMC_Combo_Null.pdf Let $n ≥ 2$ be even and let $v_1, v_2, . . . , v_k ∈ \{±1\}^n$ be vectors of ...
0
votes
0answers
11 views

Number of nodes (or vertices) with degree at most average degree + some constant [closed]

I'm struggling with a problem of graph theory. In any graph I'm trying to compute how many nodes have degree at most average degree + 1 (or some constant independent of the graph). Obviously there ...
3
votes
2answers
42 views

What is probability that out of the first half on N objects, none will be matched with their own label?

The problem: We have N (even) objects ordered $o_1 ... o_N$ , each having their own label. The labels are reassigned to the objects randomly. What is the probability that that neither of the first ...